Towards P Colonies Processing Strings

Towards P Colonies Processing Strings Ludˇek Cienciala1, Lucie Ciencialov´a1, Erzs´ebet Csuhaj-Varj´u2 1Institute of Computer Science and Research Institute of the IT4Innovations Centre of Excellence, Silesian University in Opava, Czech Republic {ludek.cienciala, lucie.ciencialova,}@fpf.slu.cz 2Faculty of Informatics, E¨otv¨os Lor´and University, Budapest, Hungary [email protected] Summary. 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 finite 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. 1 Introduction P colonies were introduced in [13] as formal models of a computing device combining properties of membrane systems and distributed systems of formal grammars called colonies. The concept was inspired by the structure and functioning of a community of living organisms in a shared environment (for more information consult [14]). In the basic model, the cells or agents are represented by a finite collection of objects and rules for processing these objects. The agents are restricted in their capabilities, i.e., only a limited number of objects, say, kobjects, are allowed to be inside any cell during the functioning of the system. These objects represent the current state of the agents, in other terms the current contents of the cells. The rules of the cells are either of the form a→b, specifying that an internal object a is transformed into an internal object b, or of the form c↔d, specifying that an internal object cis exchanged by an object din the environment. After applying these rules in parallel, the state of the agent will consist of objects b, d. Each agent is associated with a set of programs composed of such rules. 104 L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u The agents of a P colony perform a computation by synchronously applying their programs to the objects representing the state of the agents and objects in the environment. At the beginning of the computation, executed by a given P colony of capacity k, i.e., where any agent has at most ksymbols inside, the environment contains arbitrarily many copies of a distinguished symbol e, called the environmental symbol (and no more symbols); furthermore, each cell contains kcopies of e. When a halting configuration is reached, that is, when no more rules can be applied, the result of the computation is read as the number of certain types of objects in the environment. P colonies have been extensively examined during the years. For example, it was shown that these systems are computationally complete computing devices even with very restricted size parameters and with other (syntactic or functioning) restrictions [1, 2, 4, 5, 6, 7, 9, 10]. According to the the basic model, the impact of the environment on the behavior of the P colony is indirect. To describe the situation when the behavior of the components of the P colony is influenced by direct impulses coming from the environment step-by-step, the model was augmented with a string put on an input tape to be processed by the P colony [3]. These strings corresponds to the impulse sequence coming from the environment. In addition to their rewriting rules and the rules for communicating with the environment, the agents have so-called tape rules which are used for reading the next symbol on the input tape. This is done by changing one of the objects of the current state of the agents to the object corresponding to the current input symbol on the tape. The symbol is said to be read if at least one agent applied its corresponding tape rule. The model, called a P colony automaton or a PCol automaton, combines properties of standard finite automata and standard P colonies. The P colony automaton starts working with a string on its input tape (the input string) and with initial multisets of objects in its cells. The input string is accepted if it is read by the system and the P colony is in an accepting configuration (in an accepting state). It was shown that P colony automata are able to describe the class of recursively enumerable languages, taking various working mode into account. In this paper we make one step further in combining properties of P colonies and automata. While in the case of PCol automata the behaviour of the system is influenced both by the string to be processed and the environment consisting of multisets of symbols, in the case of Automaton-like P colonies or APCol systems, for short, introduced in this article, the whole environment is a string. The interaction between the agents in the P colony and the environment is realized by exchanging symbols between the objects of the agents and the environment (communication rules), and the states of the agents may change both via communication and evolution; the latter one is an application of a rewriting rule to an object. The distinguished symbol, e(in the previous models the environmental symbol) have a special role: whenever it is introduced in the string by communication, the corresponding input symbol is erased. Towards P Colonies Processing Strings 105 The computation in APCol systems starts with an input string, representing the environment, and with each agents having only symbols ein its state. Every computational step means a maximally parallel action of the active agents: an agent is active if it is able to perform at least one of its programs, and the joint action of the agents is maximally parallel if no more active agent can be added to the synchronously acting agents. The computation ends if the input string is reduced to the empty word, there are no more applicable programs in the system, and meantime at least one of the agents is in so-called final state. After defining the model, we examined the computational power of APCol systems. We proved that the family of languages accepted by jumping finite automata is properly included in the family of languages accepted by APCol systems with one agent and it was shown that any recursively enumerable language can be obtained as a projection of a language accepted by an Automaton-like P colony with two agents. We also provided several examples to demonstrate the behaviour of an APCol system. 2 Definitions Throughout the paper we assume the reader to be familiar with the basics of the formal language theory and membrane computing. For further details we refer to [11] and [17]. For an alphabet Σ, the set of all words over Σ(including the empty word, ε), is denoted by Σ∗. We denote the length of a word w∈Σ∗by |w|and the number of occurrences of the symbol a∈Σin wby |w|a. A multiset of objects Mis a pair M= (V, f), where Vis an arbitrary (not necessarily finite) set of objects and fis a mapping f:V→N;fassigns to each object in Vits multiplicity in M. The set of all multisets with the set of objects V is denoted by V◦. The set V0is called the support of Mand denoted by supp(M). The cardinality of M, denoted by |M|, is defined by |M|=Pa∈Vf(a). Any multiset of objects Mwith the set of objects V0={a1,...an}can be represented as a string wover alphabet V0with |w|ai=f(ai); 1 ≤i≤n. Obviously, all words obtained from wby permuting the letters can also represent the same multiset M, and εrepresents the empty multiset. In the following we introduce the concept of an Automaton-like P colony (an APCol system, for short) where the environment of the agents is given in the form of a string. As in the case of standard P colonies, agents of the APCol systems contain objects, each being an element of a finite alphabet. With every agent, a set of programs is associated. There are two types of rules in the programs. The first one, called an evolution rule, is of the form a→b. It means that object ainside of the agent is rewritten (evolved) to the object b. The second type of rules, called a communication rule, is in the form c↔d. When this rule is performed, the object cinside the agent and a symbol din the string are exchanged, so, we can say that 106 L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u the agent rewrites symbol dto symbol cin the input string. If c=e, then the agent erases dfrom the input string and if d=e, symbol cis inserted into the string. An Automaton-like P colony works successfully, if it is able to reduce the given string to ε, i.e., to enter a configuration where at least one agent is in accepting state and the processed string is the empty word. Definition 1. An Automaton-like P colony (an APCol system, for short) is a construct Π= (O, e, A1, . . . , An), where •Ois an alphabet; its elements are called the objects, •e∈O, called the basic object, •Ai,1≤i≤n, are agents. Each agent is a triplet Ai= (ωi, Pi, Fi), where –ωiis a multiset over O, describing the initial state (content) of the agent, |ωi|= 2, –Pi={pi,1, . . . , pi,ki}is a finite set of programs associated with the agent, where each program is a pair of rules. Each rule is in one of the following forms: ·a→b, where a, b ∈O, called an evolution rule, ·c↔d, where c, d ∈O, called a communication rule, –Fi⊆O∗is a finite set of final states (contents) of agent Ai. In the following we explain the work of an Automaton-like P colony; to help the easier reading we provide only the necessary formal details. During the work of the APCol system, the agents perform programs. Since both rules in a program can be communication rules, an agent can work with two objects in the string in one step of the computation. In the case of program ha↔b;c↔di, a substring bd of the input string is replaced by string ac. If the program is of the form hc↔d;a↔bi, then a substring db of the input string is replaced by string ca. This means that the agent can act only in one place in the one step of the computation and what happens to the string depends both on the order of the rules in the program and on the interacting objects. In particular, we have the following types of programs with two communication rules: • ha↔b;c↔ei-bin the string is replaced by ac, • hc↔e;a↔bi-bin the string is replaced by ca, • ha↔e;c↔ei-ac is inserted in a non-deterministically chosen place in the string, • he↔b;e↔di-bd is erased from the string, • he↔d;e↔bi-db is erased from the string, • he↔e;e↔di;he↔e;c↔di, . . . - these programs can be replaced by programs of type he→e;c↔di. At the beginning of the work of the APCol system (at the beginning of the computation), there is an input string placed in the environment, more precisely, the environment is given by a string ωof objects which are different from e. Towards P Colonies Processing Strings 107 This string represents the initial state of the environment. Consequently, an initial configuration of the Automaton-like P colony is an (n+1)-tuple c= (ω;ω1, . . . , ωn) where wis the initial state of the environment and the other ncomponents are multisets of strings of objects, given in the form of strings, the initial states the of agents. A configuration of an Automaton-like P colony Πis given by (w;w1, . . . , wn), where |wi|= 2,1≤i≤n,wirepresents all the objects placed inside the i-th agent and w∈(O− {e})∗is the string to be processed. At each step of the (parallel) computation every agent attempts to find one of its programs to use. If the number of applicable programs is higher than one, the agent non-deterministically chooses one of them. At one step of computation, the maximal possible number of agents have to be active, i.e., have to perform a program. By applying programs, the Automaton-like P colony passes from one configuration to another configuration. A sequence of configurations started from the initial configuration is called a computation. A configuration is halting if the AP- Col system has no applicable program. A computation is called accepting if and only if at least one agent is in final state and the string to be processed is ε. Hence, the string wis accepted by the Automaton-like P colony Πif there exists a computation by Πsuch that it starts in the initial configuration (ω;ω1, . . . , ωn) and the computation ends by halting in the configuration (ε;w1, . . . , wn), where at least one of wi∈Fifor 1 ≤i≤n. 3 Computational power of Automaton-like P colonies The behaviour of Automaton-like P colonies is similar to the functioning of jumping finite automata. The jumping finite automaton is a quintuple M= (Q, Σ, δ, q0, F) where the meaning of Q, Σ, δ, q0and Fis the same as in the case of traditional finite automaton with ε-steps (the set of states, the input alphabet, the transition function, the initial state, and the set of final states). The dissimilarity of the two computing devices is in the way of performing a computational step. The computation starts in a random cell of the input tape. After reading the input symbol in the cell and changing the state of the automaton, the reading head is allowed to jump to some random location on the tape. If the symbol is read, then it is erased from the tape. The notion of a jumping finite automaton was introduced in [15], we refer to this seminal article for the precise details. Although non-trivial languages can be recognized by jumping finite automata, the following languages cannot be accepted by them: L1={ab}, L2={anbn| n≥0}, L3={anbncn|n≥0}. But, jumping finite automata accept L4= {ab, ba}, L5={w∈ {a, b}∗| |w|a=|w|b}, L6={w∈ {a, b, c}∗| |w|a=|w|b= |w|c}. It is shown that the family of languages accepted by jumping finite automata is included in the family of context-sensitive languages. 108 L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u Theorem 1. For every jumping finite automaton M= (q, Σ, δ, q0, F)we can construct an Automaton-like P colony Π= (O, e, A)such that L(M) = L(Π)holds. Proof. Let M= (q, Σ, δ, q0, F) be a jumping finite automaton. We construct an Automaton-like P colony Πwith one agent Awhich simulates every computation of Mand only that. The simulation is as follows: •The current state of Mis stored as object inside the agent of Π, i.e., it corresponds to a state of the agent. •One step of computation of M(except of ε-step) is simulated by two computation steps of Π. In the first step, the agent changes the object corresponding to the state of Mand replaces the symbol on the tape by object eerases the symbol has been read from the input string. In the second step, the agent prepares itself for the simulation of the next step of computation of M- it rewrites the consumed symbol from the tape to e. Formally, we construct the Automaton-like P colony Π= (A, e, B) as follows: 1. O=Q∪Σ∪ {e}; 2. A= (q0e, P1,{qfe|qf∈F}); 3. P1={ hq→q0, e ↔aifor every q, q0∈Q, a ∈Σsuch that q0∈δ(q, a) hq0→q0, a →eifor every q0∈Q, a ∈Σ hq→q0, e →eifor every q, q0∈Qsuch that q0∈δ(q, ε) } The Automaton-like P colony starts processing an input string win initial configuration (q0e;w) that corresponds to the initial configuration of jumping finite automaton M(q0, w). If Mis in the configuration (q, uav), q ∈Q, u, v ∈Σ∗, a ∈Σand it performs computational step reaching state q0such that q0∈δ(q, a), then it enters configuration (q0, uv). If the APCol system Πis in the corresponding configuration (qe;uav), then the agent has an applicable program hq→q0, e ↔ai. After executing this program, Πenters configuration (q0a;uv) and in the next step the program hq0→q0, a →eimust be performed. The configuration of Πis (q0e, uv) that corresponds to configuration of M. Then the APCol system Πis prepared to simulate the next step of computation of jumping finite automaton M. If the automaton Mis in the configuration (q, u), q ∈Q, u ∈Σ∗and it performs computational step reaching state q0such that q0∈δ(q, ε), then it enters configuration (q0, u). If the APCol system Πis in the corresponding configuration (qe;u), then the agent has applicable program hq→q0, e →ei. After execution of this program the system is in the configuration (q0;u). This configuration corresponds to configuration of the jumping finite automaton M. The automaton Maccepts input string wiff it passes from the initial configuration (q0, w) to one of final configuration (qf, ε). This computation corresponds to computation in Πthat starts in the initial configuration (q0e;w) and ends in one of final configurations (qfe;ε). The computation of Πis halting if and only Towards P Colonies Processing Strings 109 if the computation in Mis halting, too. Hence the Automaton-like P colony Π accepts string wif only if jumping finite automaton Maccepts w.ut Now we show that Automaton-like P colonies are able to accept languages that jumping finite automata cannot. Example 1. Let Π1= ({a, b, p}, e, A) be an Automaton-like P colony with one agent A= (ee, P, {pp}). Let the programs of the agent be the following: 1. he↔a;e↔bi 2. ha→p;b→pi Let (ee, w), w ∈ {a, b}∗be the initial configuration of Π1. There is only one applicable program in this configuration, namely, program 1. This program is applicable only if ab is substring of w. Let w=u·ab·v, u, v ∈ {a, b}∗. After the first step of the computation the configuration of Π1is (ab, uv). In this configuration the second program ha→p;b→piis applicable and the APCol system enters configuration (pp, uv). Because of presence of two copies of object pin the state of the agent, there is no applicable program in the APCol system and the computation halts. The language accepted by Π1is L(Π1) = {ab}. Example 2. Let Π2= ({a, b, q}, e, B) be an Automaton-like P colony with one agent B= (ee, P, {qe}). The programs of the agent are following: 1. he↔a;e↔bi 2. ha→q;b→ei 3. hq→q;e↔ai 4. hq→q;e↔bi 5. hq→q;a→ei 6. hq→q;b→ei Let (ee, w), w ∈ {a, b}∗be the initial configuration of Π2. There is only one applicable program in this configuration, program 1. This program is applicable only if ab is substring of w. Let w=u·ab·v, u, v ∈ {a, b}∗. After the first step of the computation the configuration of Π2is (ab, uv). In this configuration the second program ha→q;b→eiis applicable and the APCol system enters configuration (qe, uv). Because of presence of one copy of object qinside the agent, it uses program 3 (or 4) and, consequently, program 5 (or 6). By use of these programs, the agent erases every object aand bfrom the string. The language accepted by Π2is L(Π2) = {u·ab·v|u, v ∈ {a, b}∗}. By the following example, we present a very simple Automaton-like P colony with only one agent with two programs that accepts the context-free language L={anbn|n≥0}. Example 3. Let Π3= ({a, b}, e, B) be an Automaton-like P colony with one agent A= (ee, P, {ee}). The programs of the agent are the following: 1. he↔a;e↔bi 110 L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u 2. ha→e;b→ei Let (ee, w), w ∈ {a, b}∗be the initial configuration of Π. There is only one applicable program in this configuration, program 1. This program is applicable only if ab is substring of w. Let w=u·ab ·v, u, v ∈ {a, b}∗. After the first step of the computation the configuration of the APCol system is (ab, uv). In this configuration the second program ha→e;b→eiis applicable and Π3enters configuration (ee, uv). This means that in two step of computation agent erases substring ab from a string. The computation ends when no substring ab occurs in the input string, thus any accepted word must be of the form anbn, n ≥0. An interesting question is if we can construct an Automaton-like P colony which accepts the language L={anbncn|n≥0}. Example 4. Let Π4= ({a, b, B}, e, A1, A2,{((ee),(bB))}) be an Automaton-like P colony with two agents A1= (eB, P1,{ee}) and A2= (bB, P2,{bB}). The programs of the agents are the following: Set of programs P1: 1. he↔a;B↔bi 2. ha→e;b→Bi 3. ha→e;b→ei 4. he↔B;e↔ci 5. hB→e;c→ei 6. he↔a;e→Fi 7. he↔b;e→Fi Set of programs P2: A. hb↔B;B↔bi It can be shown that L(Π4) = {anbncn|n≥0}. Instead of the formal proof, we provide the sketch of the main idea. Π4functions as follows: 1. the first agent is an ”eraser” - it erases substrings from the input string - it replaces string ab by Band erases substring Bc. 2. The second agent moves object Bover that part of the input string which contains objects b. 3. The computation is accepting if every object from the input string is erased and the state of the first agent consists of only objects e. We show an example of an accepting computation of Π4over the string w= aaabbbccc. Towards P Colonies Processing Strings 111 step string agent A1agent A1 of computation content applicable programs content applicable programs 0. aaabbbccc eB 1. Bb 1. aaBbbccc ab 2., 3. Bb A. 2. aabBbccc eB 1. Bb A. 3. aBbBccc ab 2., 3. Bb A. 4. abBBccc eB 1. Bb 5. BBBccc ab 2., 3. Bb 6. BBBccc ee 4. Bb 7. BBcc Bc 5. Bb 8. BBcc ee 4. Bb 9Bc Bc 5. Bb 10. Bc ee 4. Bb 11. ε Bc 5. Bb 12. ε ee Bb The next example is a non-accepting computation over the string w= aaabbbccc on the next table. step string agent A1agent A1 of computation content applicable programs content applicable programs 0. aaabbbccc eB 1. Bb 1. aaBbbccc ab 2., 3. Bb A. 2. aabBbccc eB 1. Bb A. 3. aBbBccc ab 2., 3. Bb A. 4. abBBccc ee 6., 7. Bb 5. bBBccc Fe Bb The Automaton-like P colony processes the string u=aabcbc in the following computations. step string agent A1agent A1 of computation content applicable programs content applicable programs 0. aabcbc eB 1. Bb 1. aBcbc ab 2., 3. Bb A. 2. aBcbc eB Bb 118 L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u 15. A. Meduna, P. Zemek, Jumping Finite Automata. Int. J. Found. Comput. Sci. 23, 2012, pp. 1555–1578. 16. M. Minsky, Computation – Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967. 17. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.,The Oxford Handbook of Membrane Computing. Oxford University Press, 2010.