×

Minimizing evolution communication P systems and automata. (English) Zbl 1085.68047

Summary: Evolution-communication P systems are a variant of P systems allowing both rewriting rules and symport/antiport rules, thus having separated the rewriting and the communication. The purpose of this paper is to solve an open problem stated by M. Cavaliere [Lect. Notes Comput. Sci. 2597, 134–145 (2003; Zbl 1023.68035)], namely generating the family of Turing computable sets of vectors of natural numbers instead of the family of Turing computable sets of natural numbers. The same construction also reduces the 3-membrane non-cooperative case and the 2-membrane 1-catalyst case to the 2-membrane non-cooperative case. Also, EC P automata are introduced and it is proved that 2-membrane EC P automata with a promoter can accept all recursively enumerable languages. Finally, a definition of an extended system is given, and its universality is proved using the rules of more restricted types.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Citations:

Zbl 1023.68035
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cavaliere, M., ”Evolution-Communication P Systems,” inMembrane Computing (Păun, G., Rozenberg, G., Salomaa, A. and Zandron, C. eds.),LNCS, 2597, pp. 134–145, Springer-Verlag, Berlin, 2003.
[2] Csuhaj-Varjuú, E. and Vaszil, G., ”P Automata or Purely Communicating Accepting P Systems,” inMembrane Computing (Păun, G., Rozenberg, G., Salomaa, A. and Zandron, C., eds.),LNCS, 2597, pp. 219–233, Springer-Verlag, Berlin, 2003. · Zbl 1023.68039
[3] Dassow, J. and Păun, G., ”Regulated Rewriting in Formal Language Theory,” Springer-Verlag, Berlin, Heidelberg, 1989.
[4] Freund, R., Martín-Vide, C., Obtulowicz, A. and Păun, G., ”On Three Classes of Automata-Like P Systems,”Developments in Language Theory, Szeged, Hungary, 2003. · Zbl 1037.68059
[5] Freund, R. and Oswald, M., ”A Short Note on Analysing P Systems with Antiport Rules,”Bulletin of the EATCS, 78, pp. 231–236, Oct. 2002. · Zbl 1169.68411
[6] Păun, G.,Membrane Computing. An Introduction, Springer-Verlag, Berlin, Heidelberg, 2002.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.