Grammar Systems versus Membrane Computing: The Case of CD Grammar Systems

• Autorzy: Csuhaj-Varjú E. , Paun G. , Vaszil G.
• Języki publikacji: EN

Abstrakty

EN

In this paper we discuss some relationships between grammar systems and P systems (membrane systems), two areas of computer science dealing with distributed computing models, but with different motivations and different types of basic ingredients. We extend one of the most important communication protocols of cooperating distributed (CD) grammar systems, the so-called t-derivation mode, to P systems with string-objects: if no rule can be applied to a string in a region of a P system, then the string is moved to a neighbouring region, depending on the communication mode either in exactly one direction (in or out) or in both directions. We describe the computational power of the obtained classes of P systems in comparison with families of languages generated by grammars in the Chomsky hierarchy or with CD grammar systems and formulate several problems for future research.

Słowa kluczowe

EN

cooperating distributed grammar systems; P systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 3
• Strony: 271--292
• Opis fizyczny: bibliogr. 8 poz., tab., wykr.

Twórcy

autor

Csuhaj-Varjú E.

autor

Paun G.

autor

Vaszil G.

• Computer and Automation Research Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111 Budapest, Hungary,

Bibliografia

• [1] Csuhaj-Varjú, E., Dassow, J., Kelemen, J., Pǎun, Gh.: Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994.
• [2] Dang, Z., Ibarra, O. H.: On P systems operating in sequential mode, in: Descriptional Complexity of Formal Systems, Pre-proceedings of a workshop, London, Canada, 26-28 July, 2004 (L. Ilie, D. Wotschke, Eds.), Report No. 619 of Dept. of Computer Science, The University of Western Ontario, London, Ontario, 2004, 164-177.
• [3] Dassow, J., , Gh.: Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin, 1989.
• [4] Ibarra, O. H., Yen, H.-C., Dang, Z.: The power of maximal parallelism in P systems, in: Developments in Language Theory: 8th International Conference, DLT 2004. Auckland, New Zealand, December 13-17. Proceedings (C. S. Calude, E. Calude, M. J. Dinneen, Eds.), volume 3340 of Lecture Notes in Computer Science, Springer-Verlag, Berlin-Heidelberg, 2004, 212-224.
• [5] Pǎun, Gh.: Computing with membranes, Journal of Computer and System Sciences, 61(1), 2000, 108-143, (and Turku Center for Computer Science-TUCS Report 208, November 1998, www.tucs.fi).
• [6] Pǎun, Gh.: Membrane Computing: An Introduction, Springer-Verlag, Berlin, 2002.
• [7] Rozenberg, G., Salomaa, A.: The Mathematical Theory of L Systems, Academic Press, New York, 1980.
• [8] Rozenberg, G., Salomaa, A., Eds.: Handbook of Formal Languages (3 volumes), Springer-Verlag, Berlin, 1997.