Grammars, automata, and distributed P systems - Buño, Kelvin Cui
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.