Affiliations: Institute of Computer Science and Research Institute of the IT4Innovations Centre of Excellence, Silesian University in Opava, Czech Republic. [email protected]; [email protected] | Department of Algorithms and Their Applications, Faculty of Informatics, Eötvös Loránd University, Budapest, Hungary. [email protected]
Note: [] This work was partially supported by the European Regional Development Fund in the IT4Innovations Centre of Excellence project (CZ.1.05/1.1.00/02.0070), by SGS/6/2014 and by project OPVK no. CZ.1.07/2.2.00/28.0014. Address for correspondence: Institute of Computer Science and Research Institute of the IT4Innovations Centre of Excellence, Silesian University in Opava, Czech Republic.
Note: [] This work was partially supported by the European Regional Development Fund in the IT4Innovations Centre of Excellence project (CZ.1.05/1.1.00/02.0070), by SGS/24/2013 and by project OPVK no. CZ.1.07/2.2.00/28.0014.
Note: [] This work was partially supported by the Hungarian Scientific Research Fund, “OTKA”, project K75952.
Abstract: 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.
Keywords: P colony, automata, jumping finite automata, recursively enumerable language
