P Colonies Processing Strings

• Autorzy: Cienciala L. , Ciencialová L. , Csuhaj-Varjú E.

Identyfikatory

DOI

10.3233/FI-2014-1090

• Języki publikacji: EN

Abstrakty

EN

In this paper we introduce and study P colonies where the environment is given as a string. These constructs, called automaton-like P colonies or APCol systems, behave like automata: during functioning, the agents change their own states and process the symbols of the string. We show that the family of ε-free languages accepted by jumping finite automata is properly included in the family of languages accepted by APCol systems with one agent and any ε-free recursively enumerable language can be obtained as a projection of a language accepted by an automaton-like P colony with two agents.

Słowa kluczowe

EN

P colony; automata; jumping finite automata; recursively enumerable language

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 1/2
• Strony: 51--65
• Opis fizyczny: Bibliogr. 17 poz., tab.

Twórcy

autor

Cienciala L.

• Institute of Computer Science and Research, Institute of the IT4 Innovations Centre of Excellence Silesian, University in Opava, Czech Republic

autor

Ciencialová L.

• Institute of Computer Science and Research, Institute of the IT4 Innovations Centre of Excellence Silesian University in Opava, Czech Republic

autor

Csuhaj-Varjú E.

• Department of Algorithms and Their Applications, Faculty of Informatics, Eötvös Loránd University, Budapest, Hungary

Bibliografia

• [1] L. Ciencialová, L. Cienciala, Variation on the theme: P colonies. In: Proc. 1st Intern. Workshop on Formal Models. (D. Kolär, A. Meduna, eds.), Ostrava, 2006, 27–34.
• [2] L. Ciencialová, E. Csuhaj-Varjú, A. Kelemenová, Gy. Vaszil, Variants of P colonies with very simple cell structure. International Journal of Computers, Communication and Control 4(3) (2009), 224–233.
• [3] L. Ciencala, L. Ciencialová, E. Csuhaj-Varjú, Gy. Vaszil, PCol Automata: Recognizing strings with P colonies. In: Proc. BWMC 2010, Sevilla, 2010, Ed. by M. A. Martnez-del-Amor et al. Fnix Editora, Sevilla, 2010, 65-76.
• [4] L. Cienciala, L. Ciencialová, A. Kelemenová, Homogeneous P colonies. Computing and Informatics 27 (2008), 481–496.
• [5] L. Cienciala, L. Ciencialová, A. Kelemenová, On the number of agents in P colonies. In: Membrane Computing. 8th International Workshop, WMC 2007. Thessaloniki, Greece, June 25-28, 2007. Revised Selected and Invited Papers. (G. Eleftherakis et. al, eds.), LNCS 4860, Springer-Verlag, Berlin-Heidelberg, 2007, 193–208.
• [6] E. Csuhaj-Varjú, J. Kelemen, A. Kelemenová, Gh. Păun, Gy. Vaszil, Computing with cells in environment: P colonies. Journal of Multi-Valued Logic and Soft Computing 12 (2006), 201–215.
• [7] E. Csuhaj-Varjú, M. Margenstern, Gy. Vaszil, P colonies with a bounded number of cells and programs. In: Membrane Computing. 7th International Worskhop, WMC 2006, Leiden, The Netherlands, July 17-21, 2006. Revised, Selected and Invited Papers. (H-J. Hoogeboom et. al, eds), LNCS 4361, Springer-Verlag, Berlin-Heidelberg, (2007), 352–366.
• [8] P. C. Fischer, Turing machines with restricted memory access. Information and Control, 9, 1966, 364–379.
• [9] R. Freund, M. Oswald, P colonies working in the maximally parallel and in the sequential mode. Pre-Proc. In: 1st Intern. Workshop on Theory and Application of P Systems. (G. Ciobanu, Gh. Păun, eds.), Timisoara, Romania, 2005, 49–56.
• [10] R. Freund, M. Oswald, P colonies and prescribed teams. International Journal of Computer Mathematics 83 (2006), 569–592.
• [11] J. E., Hopcroft, J. D., Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, Mass., 1979.
• [12] J. Kelemen, A. Kelemenova, A grammar-theoretic treatment of multi-agent systems. Cybernetics and Systems 23 (1992), 621–633.
• [13] J. Kelemen, A. Kelemenova, Gh. Paun, Preview of P colonies: A biochemically inspired computing model. In: Workshop and Tutorial Proceedings. Ninth International Conference on the Simulation and Synthesis of Living Systems (Alife IX). (M. Bedau et al., eds.), Boston Mass., 2004, 82–86.
• [14] A. Kelemenova, P Colonies. Chapter 23.1, In: [17], Oxford University Press, 2010, 584–593.
• [15] A. Meduna, P. Zemek, Jumping finite automata. Int. J. Found. Comput. Sci. 23, 2012, 1555–1578.
• [16] M. Minsky, Computation – Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967.
• [17] The Oxford Handbook of Membrane Computing. (Gh. Păun, G. Rozenberg, A. Salomaa, eds.) Oxford University Press, 2010.