On Controlled P Systems

• Autorzy: Krithivasan K. , Păun G. , Ramanujan A.

Identyfikatory

DOI

10.3233/FI-2014-1025

• Języki publikacji: EN

Abstrakty

EN

We introduce and briefly investigate P systems with controlled computations. First, P systems with label restricted transitions are considered (in each step, all rules used have either the same label, or, possibly, the empty label, λ), then P systems with the computations controlled by languages (as in context-free controlled grammars). The relationships between the families of sets of numbers computed by the various classes of controlled P systems are investigated, also comparing them with length sets of languages in Chomsky and Lindenmayer hierarchies (characterizations of the length sets of ET0L and of recursively enumerable languages are obtained in this framework). A series of open problems and research topics are formulated.

Słowa kluczowe

EN

membrane computing; P systems; control word; Chomsky language; Lindenmayer language

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 3-4
• Strony: 451--464
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Krithivasan K.

• Department of Computer Science and Engineering, Indian Institute of Technology, Madras, Chennai-36, India

autor

Păun G.

• Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700 Bucureşti, Romania

autor

Ramanujan A.

• Department of Computer Science and Engineering, Indian Institute of Technology, Madras, Chennai-36, India

Bibliografia

• [1] A. Alhazov, R. Freund, H. Heikenwälder, M. Oswald, Y. Rogozhin, S. Verlan: Sequential P systems with regular control. Membrane Computing International Conference. CMC 2012, Budapest, Hungary. Invited and Selected Papers (E.Csuhaj-Varju,M. Gheorghe, G. Vaszyl, eds.), Springer, LNCS 7762, 2013, in press.
• [2] J. Dassow, Gh. Păun: Regulated Rewriting in Formal Language Theory. Springer, Berlin, 1989.
• [3] Gh. Păun: Computing with membranes. J. Comput. Syst. Sci., 61 (2000), 108–143 (see also TUCS Report 208, November 1998, www.tucs.fi).
• [4] Gh. Păun, M.J. Pérez-Jiménez: Languages and P systems: Recent developments, Computer Sci. J. of Moldova, 20, 2 (59), 2012, 112–132.
• [5] Gh. Păun, G. Rozenberg, A. Salomaa, eds.: The Oxford Handbook of Membrane Computing. Oxford University Press, 2010.
• [6] A. Ramanujan, K. Krithivasan: Control words of spiking neural P systems. Romanian J. of Information Science and Technology, to appear.
• [7] A. Ramanujan, K. Krithivasan: Control words of transition P systems. Paper in preparation, 2012.
• [8] G. Rozenberg, A. Salomaa: The Mathematical Theory of L Systems. Academic Press, New York, 1980.
• [9] G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages. 3 volumes, Springer, Berlin, 1998.
• [10] The P Systems Website: http://ppage.psystems.eu.