On Three Classes of Automata-Like P Systems
- 299 Downloads
We investigate the three classes of accepting P systems considered so far, namely the P automata of Csuhaj-Varjú, Vaszil , their variant introduced by Madhu, Krithivasan , and the related machinery of Freund, Oswald . All three variants of automata-like P systems are based on symport/antiport rules. For slight variants of the first two classes we prove that any recursively enumerable language can be recognized by systems with only two membranes (this considerably improves the result from , where systems with seven membranes were proved to be universal). We also introduce the initial mode of accepting strings (the strings are introduced into the system, symbol by symbol, at the beginning of a computation), and we briefly investigate this mode for the three classes of automata, especially for languages over a one-letter alphabet. Some open problems are formulated, too.
KeywordsMathematical Linguistics Initial Mode Terminal Symbol Register Machine Membrane Computing
Unable to display preview. Download preview PDF.
- 7.Freund, R., Păun, Gh.: On the Number of Non-terminal Symbols in Graph-controlled, Programmed and Matrix Grammars. In: Margenstern, M., Rogozhin, Y. (eds.): Proc. Conf. Universal Machines and Computations, Chişinău, 2001. LNCS, Vol. 2055. Springer-Verlag, Berlin Heidelberg New York (2001) 214–225CrossRefGoogle Scholar
- 8.Freund, R., Sosík, P.: P Systems without Priorities Are Computationally Universal. In: Rozenberg, G., Salomaa, A., Zandron, C. (eds.): Membrane Computing 2002. LNCS, Vol. 2597. Springer-Verlag, Berlin Heidelberg New York (2003)  400–409Google Scholar
- 10.Madhu, M., Krithivasan, K.: On a Class of P Automata, manuscript (2002)Google Scholar