P Colonies Processing Strings

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.