Towards P Colonies Processing Strings

Abstract

In this paper we introduce and study P colonies where the environment is given as a string. These variants of P colonies, called Automaton-like P systems or APCol systems, behave like automata: during functioning, the agents change their own states and process the symbols of the string. After introducing the concept of APCol systems, we examine their computational power. It is shown that the family of languages accepted by jumping nite automata is properly included in the family of languages accepted by APCol systems with one agent, and it is proved that any recursively enumerable language can be obtained as a projection of a language accepted by an Automaton-like P colony with two agents.