Modelling Grammar Systems by Tissue P Systems Working in the Sequential Mode

• Autorzy: Freund R. , Oswald M.
• Języki publikacji: EN

Abstrakty

EN

We consider tissue P systems where rules are applied when moving through a channel from one cell to another one. In a very general manner (i.e., working on arbitrary objects as strings, arrays, graphs, etc.), these tissue P systems equipped with the sequential derivation mode allow for the representation of hybrid co-operating grammar systems using the classic basic derivation modes *,t and ? k,=k, ^(3) k, for k ^(3) 1, as well as the internally hybrid modes ( ^(3) kU` ? l), for k,l Î \mathbbN , k ? l, and (tU` ? k) , ( tU` = k) , (tU` ^(3) k) , for k ^(3) 1. Moreover, we also show how these tissue P systems working in the sequential mode allow for the simulation of random context grammars, too.

Słowa kluczowe

EN

grammar system; tissue P system; derivation modes

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 3
• Strony: 305--323
• Opis fizyczny: bibliogr. 31 poz., rys.

Twórcy

autor

Freund R.

autor

Oswald M.

• Faculty of Informatics, Vienna University of technology, Favoritenstr. 9, 1040 Wien, Austria,

Bibliografia

• [1] Bordihn, H., Holzer,M.: On a hierarchy of languages generated by cooperating distributed grammar systems, Inform. Process. Lett. 69(2), 1999, 59-62.
• [2] Csuhaj-Varjú, E., Dassow, J.: On cooperating/distributed grammar systems, J. Inf. Process. Cybern. EIK 26(1/2), 1990, 49-63.
• [3] Dassow, J., Freund, R., Pǎun, Gh.: Cooperating array grammar systems, Int. Journ. of Pattern Recognition and Artificial Intelligence 9(6), 1995, 1-25.
• [4] Csuhaj-Varjú, E., Dassow, J., Kelemen, J., Pǎun, Gh.: Grammar Systems: A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994.
• [5] Dassow, J.: On cooperating distributed grammar systems with competence based start and stop conditions, Prel. Proceedings of Grammar Systems Week 2004 (E. Csuhaj-Varjú, Gy. Vaszil, Eds.), MTA SZTAKI, Budapest, 2004, 146-151.
• [6] Dassow, J., Pǎun, Gh.: Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin, 1989.
• [7] Fernau, H., Freund, R.: Bounded parallelism in array grammars used for character recognition, Proceedings of Structural and Syntactical Pattern Recognition SSPR'96 (P. Perner, P. Wang, A. Rosenfeld, Eds.), LNCS 1121, Springer, Berlin, 1996, 40-49.
• [8] Fernau, H., Freund, R.: Accepting array grammars with control mechanisms, New Trends in Formal Languages (Gh. Pǎun, A. Salomaa, Eds.), LNCS 1218, Springer, Berlin, 1997, 95-118.
• [9] Fernau, H., Freund, R., Holzer, M.: External versus internal hybridization for cooperating distributed grammar systems, Technical Report TR 185-2/FR-1/96, Technische Universität Wien, Austria, 1996.
• [10] Fernau, H., Freund, R., Holzer, M.: Character recognition with k-head finite array automata, Proceedings of Structural and Syntactical Pattern Recognition SSPR'98 (A. Amin et al. Eds.), LNCS 1451, Springer, Berlin, 1998, 282-291.
• [11] Fernau, H., Freund, R., Holzer, M.: Regulated array grammars of finite index, in: Grammatical Models of Multi-Agent Systems (Gh. Pǎun, A. Salomaa, Eds.), Gordon and Breach, London,1999, 157-181 (Part I) and 284-296 (Part II).
• [12] Fernau, H., Freund, R., Holzer, M.: Hybrid modes in cooperating distributed grammar systems: internal versus external hybridization, Theoretical Computer Science 259, 2001, 405-426.
• [13] Fernau, H., Freund, R., Holzer, M.: Hybrid modes in cooperating distributed grammar systems: combining the t-mode with the modes _ k and = k, Theoretical Computer Science 299, 2003, 633-662.
• [14] Fernau, H., Freund, R., Holzer, M.: Bounding resources in cooperating distributed grammar systems, Proc. of the 3rd Int. Conf. Developments in Language Theory (S. Bozapalidis, Ed.), Aristotle University of Thessaloniki, 1997, 261-272.
• [15] Fernau, H., Holzer, M.: Accepting multi-agent systems II, Acta Cybernetica 12, 1996, 361-379.
• [16] Freund, R.: Control mechanisms on #-context-free array grammars, in: Mathematical Aspects of Natural and Formal Languages (Gh. Pǎun, Ed.), World Scientific Publ., Singapore, 1994, 97-137.
• [17] Freund, R., Pǎun, Gh., Pérez Jiménez, M. J.: Tissue-like P systems with channel states, in: [27], 2004, 206-223.
• [18] Freund, R.: Asynchronous P systems and P systems working in the sequential mode, in: Membrane Computing. International Workshop WMC5 (G. Mauri, Gh. Pǎun, M. J. Pérez Jiménez, G. Rozenberg, A. Salomaa, Eds.), LNCS 3365, Springer, Berlin, 2005 , 36-62.
• [19] Freund, R.: P systems working in the sequential mode on arrays and strings, Int. J. of Foundations of Computer Science 16 (4), 2005, 663-682.
• [20] Meersman, R., Rozenberg, G.: Cooperating grammar systems, Proceedings of Mathematical Foundations of Computer Science MFCS'78, LNCS 64, Springer, Berlin, 1978, 364-374.
• [21] Mitrana, V.: Hybrid cooperating/distributed grammar systems, Computers and Artificial Intelligence 12(1), 1993, 83-88.
• [22] Nilsson, N. J.: Principles of Artificial Intelligence, Springer, Berlin, 1982.
• [23] Pǎun, Gh.: On the generative capacity of hybrid CD grammar systems, J. Inf. Process. Cybern. EIK 30(4), 1994, 231-244.
• [24] Pǎun, Gh.: Computing with membranes, Journal of Computer and System Sciences 61(1), 2000, 108-143, and TUCS Research Report 208, 1998 (http://www.tucs.fi).
• [25] Pǎun, Gh.: Membrane Computing: an Introduction. Springer, Berlin, 2002.
• [26] Pǎun, Gh.: Grammar systems vs. membrane computing: a preliminary approach, Prel. Proc. of Grammar Systems Week 2004 (E. Csuhaj-Varjú, Gy. Vaszil, Eds.), MTA Sztaki, Budapest, 2004, 225-245.
• [27] Pǎun, Gh., Riscos Nu˜nez, A., Romero Jiménez, A., Sancho Caparrini, F., Eds.: Second Brainstorming Week on Membrane Computing, Univ. of Sevilla Tech. Report 01/2004, Sevilla, Spain, Feb. 2-7, 2004.
• [28] The P Systems Web Page: http://psystems.disco.unimib.it/
• [29] Rosenfeld, A.: Picture Languages, Academic Press, Reading, MA, 1979.
• [30] Salomaa, A., Rozenberg, G., Eds.: Handbook of Formal Languages. Springer, Berlin, 1997.
• [31] Wang, P. S.-P., Ed.: Array Grammars, Patterns and Recognizers,World Scientific Series in Computer Science 18, World Scientific Publ., Singapore, 1989.