00000ctm a22000003i 4500 UP-99796217612562367 Buklod 20230215105418.0 m |o d | ta 170809s xx d r |||| u| (iLib)UPD-00343311404 DENGII rda eng LG 996 2017 C65 J83 Juayong, Richelle Ann B. author. Communication complexity in P systems with energy Richelle Ann Borcelis Juayong ; Henry N. Adorna, dissertation adviser. Quezon City College of Engineering, University of the Philippines Diliman 2017. xiii, 118 leaves 28 cm text rdacontent unmediated rdamedia volume rdacarrier Thesis (Ph.D. Computer Science)--University of the Philippines Diliman May 2017. F - no patentable invention or creation, not for personal publication and no confidential information. Yes - available to the general public. Membrane computing is a field of computer science that gets inspiration from the architecture and functioning of living cells to devise new ways of computing. Cell features as in a hierarchically arranged set of membranes are incorporated in a computing model. In this model, each region bounded by a membrane may contain a multiset of objects that follows a set of rules for evolution and communication across membranes. Similar to living cells, these membranes act as processors that compute simultaneously while at the same time, cooperating with each other and computing as a single unit. The resulting devices, called P systems, perform in a parallel and distributed nature. In the interest of initiating communication complexity researches in these devices, several models were introduced in literature. One such model is called Evolution-Communication P system with Energy (ECPe system). ECPe system has two main and distinct type of rules: evolution and communication. A form of payment called energy is earned through use of evolution rules and given off upon use of a communication rule. Dynamical measures, such as considering the number of communication steps (ComN), communication rules (ComR) and total energy used for communication (ComW), were proposed for ECPe system. In this study, several aspects of computation and communication in an ECPe system are investigated. First, the computing power of ECPe systems having bounded and unbounded communication is analyzed. We address a previous conjecture that states that only semilinear sets can be generated with bounded ComX , X E {N,R, vV}. Our result on bounded ComW seems to support such conjecture while the conjecture is not true for bounded ComN and ComR. Dynamic communication resources of some hard problems solved using ECPe systems and a related variant called Evolution-Communication P systems are explored. We develop non-confluent solutions for the Vertex Cover Problem and 3-Satisfiability Problem. In our solutions, ComN is constant, ComR is linear to the input size and ComW is either linear or quadratic with respect to the input size. Also, solutions in ECP sy8tems have lesser resources as compared to solutions in ECPe systems. Finally, simulation relations between ECPe systems and a basic variant called Transition P system are provided. We have shown that for every non-cooperative TP system, we can construct an ECPe system that, (i) generates the same language, and (ii) each halting computation that takes T steps in the TP system can be simulated in at most 3T + 1steps in its corresponding ECPe system. We also look at TP systems where an object that triggers a cooperative rule also triggers a non-cooperative rule. In this way, the presence of a rule trigger always implies that a rule will be applied. In our constructed ECPe systems, a transition in the TP system is simulated by a k-step computation where k is a factor of the cardinality of the alphabet in the original system. Also, the maximum energy needed for communication rules are dependent on the number of copies of a trigger in a cooperative rule. Natural computation. Molecular computers. Computable functions. Computational complexity. Evolution-communication P systems with energy (ECPe systems). Adorna, Henry N. adviser. Thesis FI UP UPD DENG-II LG 996 2017 C65 J83 Thesis