TY  - THES
T1  - Grammars, automata, and distributed P systems
A1  - Buño, Kelvin Cui
LA  - English
UL  - https://ds.mainlib.upd.edu.ph/Record/UP-99796217610382297
AB  - In this research, we investigate the computing powers of grammar systems, automata systems, and distributed P systems that employ a common computation strategy of synchronized derivation or transition through a form of control. In particular, we focus on Multigenerative Grammar Systems and Distributed P Systems. We first construct an automata system called Multirecognizing Automata System that is based on the computing strategy of Multigenerative Grammar Systems. We prove that this automata system is able to characterize the Recursively Enumerable class of languages. Next, we focus on the parallelizability of dP Automata. We show in this work that there exists a class of language that is parallelizable by dP Automata with an arbitrary number of components without suffering parallel slowdown. Finally, we present a variant of distributed P systems that uses synchronization and control of rewriting evolution rules, called Controlled Rewriting dP Systems. We prove that Controlled Rewriting dP Systems is able to characterize the Recursively Enumerable class of languages as well. we then provide a comparison of computational power, communication cost, and parallelizability of Controlled dP Systems and dP Automata.
OP  - 84
CN  - LG 995 2011 C65 B86
KW  - Machine theory.
KW  - Computational complexity.
KW  - Multirecognizing Automata System.
KW  - Multigenerative Grammar Systems.
KW  - Membrane computing.
KW  - Distributed P systems.
KW  - Cooperative Distributed Grammar Systems.
KW  - Pushdown automata (PDA).
KW  - Controlled Rewriting dP Systems.
ER  -