A Note on a New Class of APCol Systems

A Note on a New Class of APCol Systems Lucie Ciencialov´a1, Erzs´ebet Csuhaj-Varj´u2, and Gy¨orgy Vaszil3 1Institute of Computer Science, Silesian University in Opava, Czech Republic [email protected] 2Faculty of Informatics, E¨otv¨os Lor´and University, Budapest, Hungary [email protected] 3Faculty of Informatics, University of Debrecen, Hungary [email protected] Summary. We introduce a new acceptance mode for APCol systems (Automaton-like P colonies), variants of P colonies where the environment of the agents is given by a string and during functioning the agents change their own states and process the string similarly to automata. In case of the standard variant, the string is accepted if it can be reduced to the empty word. In this paper, we define APCol systems where the agents verify their environment, a model resembling multihead finite automata. In this case, a string of length nis accepted if during every halting computation the length of the environmental string in the configurations does not change and in the course of the computation every agent applies a rule to a symbol on position iof some of the environmental strings for every i, 1 ≤i≤nat least once. We show that these verifying APCol systems simulate one-way multihead finite automata. 1 Introduction Automaton-like P colonies (APCol systems, for short), introduced in [1], are variants of of P colonies (introduced in [9]) - very simple membrane systems inspired by colonies of formal grammars. The interested reader is referred to [12] for detailed information on P systems (membrane systems) and to [10] and [5] for more information to grammar systems theory; for more details on P colonies consult [8] and [4]. An APCol system consists of a finite number of agents - finite collections of objects in a cell - and a shared environment. The agents have programs consisting of rules. These rules are of two types: they may change the objects of the agents and they can be used for interacting with the joint shared environment of the agents. While in the case of standard P colonies the environment is a multiset of objects, in case of APCol systems it is represented by a string. The number of objects inside each agent is set by definition and it is usually a very small number: 1, 2 or 3. The environmental string is processed by the agents and it is used as an indirect communication channel for the agents as well, since through the string, the agents 60 L. Ciencialov´a, E. Csuhaj-Varj´u, G. Vaszil are able to affect the behaviour of another agent. The reader may easily observe that APCol systems resembling automata as well, the current configuration of the system (the objects inside the agents) and the current environmental string correspond to the current state of an automaton and the currently processed input string. The agents may perform rewriting, communication or checking rules [9]. A rewriting rule a→ballows the agent to rewrite (evolve) one object ato object b. Both objects are placed inside the agent. Communication rule c↔dmakes possible to exchange object cplaced inside the agent with object din the string. A checking rule is formed from two rules r1, r2of type rewriting or communication. It sets a kind of priority between the two rules r1and r2. The agent tries to apply the first rule and if it cannot be performed, then the agent performs the second rule. The rules are combined into programs in such a way that all objects inside the agent are affected by execution of the rules. Thus, the number of rules in the program is the same as the number of objects inside the agent. The computation in APCol systems starts with the an input string, representing the initial state of the environment, and with each agents having only symbols einside. A computational step means a maximally parallel action of the active agents, i.e., agents that can apply their rules. Every symbol can be object of the action of only one agent. 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. This mode of computation is called accepting. APCol systems can also be used not only for accepting but generating strings. For more detailed information on APCol systems we refer to [2, 3]. In this paper, we define a new variant of APCol systems, a model resembling multihead finite automata, where the agents verify their environment. In this case, a string of length nis accepted if during every halting computation the length of the environmental string in the configurations does not change and in the course of the computation every agent applies a rule to a symbol on position iof some of the environmental strings for every i, 1 ≤i≤nat least once. We show that these verifying APCol systems simulate one-way multihead finite automata. 2 Preliminaries and Basic Notions Throughout the paper we assume the reader to be familiar with the basics of the formal language theory and membrane computing [13, 12]. 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. For a string x∈Σ∗,x[i] denotes the symbol at ith position of x, i.e., if x=x1. . . xn,xi∈Σ, then x[i] = xi. For every string x∈Σ∗,x[0] = ε. For every string x∈Σ∗,perm(x) denotes the set of all permutations of xand pref(x) denotes the set of prefixes of x. A Note on a New Class of APCol Systems 61 A multiset of objects Mis a pair M= (O, f), where Ois an arbitrary (not necessarily finite) set of objects and fis a mapping f:O→N;fassigns to each object in Oits multiplicity in M. Any multiset of objects Mwith the set of objects O={x1, . . . xn}can be represented as a string wover alphabet Owith |w|xi=f(xi); 1 ≤i≤n. Obviously, all words obtained from wby permuting the letters can also represent the same multiset M, and εrepresents the empty multiset. 2.1 One-way Multihead Finite Automata We recall some basic notions concerning multi-head finite automata based on [7]. A non-deterministic one-way k-head finite automaton (a 1NFA(k), for short) is a construct M= (Q, Σ, k, δ, ▷, ◁, q0, F), where Qis the finite set of states, Σis the set of input symbols, k≥1 is the number of heads, ▷ /∈Σand ◁ /∈Σare the left and the right endmarkers, respectively, q0∈Qis the initial state, F⊆Qis the set of accepting states, and δis the partial transition function which maps Q×(Σ∪ {▷, ◁})kinto subsets of Q× {0,1}k, where 1 means that the head moves one tape cell to the right and 0 means that it remains at the same position. We note that the heads can never move to the left of the left endmarker and to the right of the right endmarker. A configuration of a 1NFA(k)M= (Q, Σ, k, δ, ▷, ◁, q0, F) is a triplet c= (w, q, p),where w∈Σ∗is the input, q∈Qis the current state, and p= (p1, . . . , pk)∈ {0,1, . . . , |w|+ 1}kgives the head positions. If a position piis 0, then head iis scanning the symbol ▷, if 1 ≤pi≤ |w|,then head iscans the pith letter of w, and if pi=|w|+ 1, then the ith head is scanning the symbol ◁. The initial configuration for an input w∈Σ∗is (w, q0,(1, . . . , 1)), that is, a 1NFA(k) starts processing a nonempty input word with all of its heads positioned on the first symbol of w. In the course of the computation, Mperforms direct changes of its configurations. Let w=a1. . . an, be the input, a0=▷, an+1 =◁. For two configurations, c1= (w, q, (p1, . . . , pk)) and c2= (w, q′,(p′ 1, . . . , p′ k)), we say that c2directly follows c1,denoted by c1⊢c2, if (q′,(d1, . . . , dk)) ∈δ(q, (ap1, . . . , apk)) and p′ i=pi+di, 1≤i≤k. The reflexive transitive closure of ⊢is denoted by ⊢∗. Note that due to the restriction of the transition function, the heads cannot move beyond the endmarkers. The language L(M) accepted by a 1NFA(k)M= (Q, Σ, k, δ, ▷, ◁, q0, F) is the set of words wsuch that there is a computation which starts with ▷w◁ on the input tape and ends when Mreaches an accepting state, i.e., L(M) = {w∈Σ∗|(w, q0,(1, . . . , 1)) ⊢∗(w, qf,(p1, . . . , pk)), qf∈F}. The class of languages accepted by 1NFA(k), for k≥1,is denoted by L(1NFA(k)) According to the definition of a 1NFA(k)M= (Q, Σ, k, δ, ▷, ◁, q0, F), the heads do not need to move away from the scanned tape cell after reading the input 62 L. Ciencialov´a, E. Csuhaj-Varj´u, G. Vaszil symbol. For technical reasons, we use a modified but equally powerful version of this definition in such a way that the automaton reads the input symbols only in the case when the head moves away from the tape cell containing the symbol. Otherwise, it “scans” the empty word ε, that is, the symbol does not have any role in the determination of the next configuration of the machine. For details and the proof of the equivalence the reader is referred to [6]. Thus, we can simplify the notation for the elements of the transition relation of one-way k-head finite automata, since we can assume that if (q′,(d1, . . . , dk)) ∈ δ(q, a1, . . . , ak), then dj= 0 if and only if aj=ε, 1 ≤j≤k. As (d1, . . . , dk)∈ {0,1}k, we can simply denote the above transition as q′∈δ(q, a1, . . . , ak): If aj=ε for some j, 1≤j≤k, then the jth reading head is moved to the right, otherwise, if aj=εit remains in its current position. 2.2 APCol Systems In the following we recall the notion of an APCol system (an automaton-like P colony) where the environment of the agents is given in the form of a string [1]. As standard P colonies, agents of the APCol systems contain objects, each of them is an element of a finite alphabet. Every agent is associated with a set of programs, every program consists of two rules that can be one of the following two types. The first one, called an evolution rule, is of the form a→b. This means that object ainside of the agent is rewritten to object b. The second type, called a communication rule, is of the form c↔d. When this rule is applied, object c inside the agent and a symbol din the string representing the environment (the input string) are exchanged. If c=e, then the agent erases dfrom the input string and if d=e, symbol cis inserted into the string. The computation in APCol systems starts with an input string, representing the environment, and with each agent having only symbols einside. A computational step means a maximally parallel action of the active agents, i.e., agents that can apply their rules. Every symbol can be object of the action of only one agent. 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. An APCol system, for 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, A Note on a New Class of APCol Systems 63 ·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 APCol system. 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 ⟨a↔b;c↔d⟩, a substring bd of the input string is replaced by string ac. Notice that although the order of rules in the programs is usually irrelevant, here it is significant, since it expresses context-dependence. If the program is of the form ⟨c↔d;a↔b⟩, then a substring db of the input string is replaced by string ca. Thus, the agent is allowed to act only at one position of the string in the one step of the computation and the result of its action 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: • ⟨a↔b;c↔e⟩-bin the string is replaced by ac, • ⟨c↔e;a↔b⟩-bin the string is replaced by ca, • ⟨a↔e;c↔e⟩-ac is inserted in a non-deterministically chosen place in the string, • ⟨e↔b;e↔d⟩-bd is erased from the string, • ⟨e↔d;e↔b⟩-db is erased from the string, • ⟨e↔e;e↔d⟩;⟨e↔e;c↔d⟩, . . . - these programs can be replaced by programs of type ⟨e→e;c↔d⟩. At the beginning of the work of the APCol system (at the beginning of the computation), the environment is given by a string ωof objects which are different from e. This string represents the initial state of the environment. Consequently, an initial configuration of the APCol system 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 APCol system Πis given by (w;w1, . . . , wn), where |wi|= 2,1≤i≤n,wirepresents all the objects inside the ith agent and w∈(O− {e})∗ is the string to be processed. At each step of the computation every agent attempts to find one of its programs to use. If the number of applicable programs is higher than one, then 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 APCol system 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 APCol system has no applicable program. The result of computation depends on the mode in which the APCol system works. In the case of accepting mode a computation is called accepting if and only 64 L. Ciencialov´a, E. Csuhaj-Varj´u, G. Vaszil if at least one agent is in final state and the string to be processed is ε. Hence, the string ωis accepted by the APCol system Π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∈Fi for 1 ≤i≤n. In [1] it was shown that the family of languages accepted by jumping finite automata (introduced in [11]) is properly included in the family of languages accepted by APCol systems with one agent, and it was proved that any recursively enumerable language can be obtained as a projection of a language accepted by an APCol system with two agents. 3 Verifying APCol Systems In this section we introduce a new variant of acceptance for APCol systems, motivated by the behaviour of multihead finite automata. In case of standard APCol systems acceptance means identifying and erasing symbols of the current environmental string. In case of verifying APCol systems, the agents only indicate that they ”visit” a certain position in the current environmental string, i.e., rewrite the symbol at that position to some symbol but not to the empty word. A string is verified if the computation process is halting and for every i, 1 ≤i≤nsupposed that the length of the input string is n-, each agent rewrites a symbol at position iin some of the environmental strings occurring in the computation process. This means that the agents ”visit” each position (of the input string or that of its descendant), i.e., they verify that the environment. To perform a transition, the APCol systems work with the maximally parallel mode. Definition 1. Let Π= (O, e, A1, . . . , An),n≥1, be and APCol system working with the maximally parallel mode. We say that Πverifies input string ωif the following conditions hold. •There exists a halting computation cin Πwhere c= (ω;ω1, . . . , ωn) =⇒(ω(1);ω(1) 1, . . . , ω(1) n)=⇒. . . (ω(s);w(s) 1, . . . , w(s) n), s≥1, such that |ω|=|ω(j)|for 1≤j≤s. •Computation csatisfies the following property. Let ω(0) =ω. For every agent Ak,1≤k≤nand for every i,1≤i≤mwhere |ω|=m, there exists j, 1≤j≤ssuch that the symbol at the ith position of ω(j−1) is letter band Ak applies a rule a↔bto this position of ω(j−1). Computation cis called a verification or a verifying computation. The set of all words that can be verified by Πis called the language verified by Π. We call a word, resp. a language strongly verified if every computation of the word, resp. of every word in the language is verifying. In the following we show that verifying APCol systems simulate one-way multihead finite automata. A Note on a New Class of APCol Systems 65 Theorem 1. Let M= (Q, Σ, n, δ, ▷, ◁, q0, F),n≥1, be an n-head finite automaton. Then we can construct an APCol system Πwith n+ 2 agents such that any word wthat can be accepted by Mcan strongly be verified by Π. Proof. To prove the statement, we construct an APCol system Π= (O, e, Aini, A1, . . . , An, Afin) such that each agent Aj, 1 ≤j≤nsimulates the work of the jth reading head of Mand only that. Agent Aini serves for initializing the simulation and agent Afin checks whether the agents visited every position in the environmental string. The verifying process in Πcorresponds to an accepting process in M: if a symbol awas scanned by reading heads {i1, . . . , ir} ⊆ {1, . . . , n}, then this fact will be indicated by a symbol a(x)in the environmental string of Π, where x∈perm(i1. . . ır); i1, . . . , irare the numbers of reading heads that scanned symbol a. Every computation step in Mis simulated by a sequence of computation steps performed by agents A1, . . . An. The input word for Πis of the form ▷w. To help the easier reading, we will present only the agents together with their programs. Πhas agent Aini for initializing the simulation and also for assisting the checking whether every position has been visited or not. It has the following programs: (1) ⟨e→q0,1, e →e⟩, (2) ⟨q0,1↔▷, e →e⟩, (3) ⟨e→e, ¯a(x)→a′(x)⟩, where q0is the initial state and x∈perm(1 . . . n), a ∈Σ. Programs (1) and (2) are for initializing the simulation, programs of type (3) are for checking whether or not all positions have been visited. Every agent Ajsimulates the work of the reading head j, 1 ≤j≤n. For every transition relation s∈δ(q, a1, . . . , an) of M, where a1, . . . , an∈Σ∪ {ε}, agent Aj,1≤j≤n−1 has the following programs. (We recall that if aj=εfor some j, 1≤j≤k, then the jth reading head is moved to the right, otherwise, if aj=εit remains in its current position.) (0) ⟨e→▷j, e →▷′ j⟩, (1) ⟨▷′ j↔sj, e →e⟩, (1a)⟨▷′ j↔sj, ▷j↔e⟩, (1b)⟨▷′ 1↔q1, e →e⟩, (1c)⟨▷′ 1↔q1, ▷1↔e⟩, 66 L. Ciencialov´a, E. Csuhaj-Varj´u, G. Vaszil (2) ⟨sj→s′ j, e →a(xj) j⟩, (2a)⟨sj→s′ j, e →a(x) j⟩, (2b)⟨q1→s′ j, e →a(xj) j⟩, (2c)⟨q1→s′ j, e →a(x) j⟩, (3) ⟨axj j↔▷j, s′ j↔a(x) j⟩, (3a)⟨s′ j↔▷j, ax j↔a(x) j⟩, (4) ⟨▷j↔s′ j, a(x) j→sj+1⟩, (4a)⟨▷j↔s′ j, a(xj) j→sj+1⟩, (5) ⟨sj+1 ↔▷′ j, s′ j→e⟩, where x∈pref(perm(1 . . . n)), |x|j= 0, if aj=εand x∈pref(perm(1 . . . n)) and |x|j= 1 if aj=ε. Furthermore, y∈pref(perm(1 . . . n)) and |y|j= 1. For j=nand s= (q′, p1, . . . , pn), agent Ajhas the same programs (0)-(3a), and programs (4),(4a) and (5) are changed as follows: (5) ⟨▷n→p′ 1, e →e⟩, (6) ⟨p′ 1↔▷n, e →e⟩, We present a brief explanation of the programs. The first program, (0) is used for initialization. it generates two symbols of ▷jthe first to mark the position of reading head and the second to exchange for symbol of the simulated transition. The simulation of the move of the jth reading head starts with program (1). If it is simulation of the first step and the first head, then program (1c) is used. For the first use of other heads the program (1a) is used. The program (1b) is executed when the system simulates not the first step of computation. The input string has the form qjα, where qis the state in transition relation s∈δ(q, a1, . . . , an), its subscript jrefers to the jth reading head, and α∈Σ∗such that |α|=|w| (wis the input word). Then qjis changed for ▷jin the environmental string, implying that no action of some other agent can be performed. Meantime, Aj changes sjfor s′ jand makes a guess whether symbol ajis to be scanned or the reading head will remain at the same position. This is done by introducing a(xj) j or a(x) j, programs (2) or (2a). Superscript xj refers to that letter ajhas not been scanned by reading head j(xis the sequence of the number of reading heads that already scanned this symbol). When agent A1does the same thing (uses one of programs (2b), (2c)), it also nondeterministically chooses transition sfrom the possible transitions δ(q, a1, . . . , an) for given q∈Qand arbitrary sequence of symbols a1, . . . , an. After then, programs (3) or (3a) perform the corresponding action, namely change ▷ja(x) jto a(xj) js′ jor leave the two letters unchanged. (Notice that the order of rules in this type of programs is important). In the first case we simulate that the jth reading head scanned aj, in the second case it remained at the same position. Note that if the reading head is in the position of cell with A Note on a New Class of APCol Systems 67 symbol a, the symbol ais not marked as read in this moment. The symbol ais read when head is leaving the cell with this symbol. After then, by programs (4), (5), agent Ajwill return to state (▷′ j, e) and the simulation of the move of the next reading head in transition sstarts, i.e., the environmental string will have sj+1 as first letter. If j=n, then the first letter in the environmental string is changed to q′ 1, meaning that Mentered state q′and the simulation of the first reading head starts. The computation is successful if it is halting and all positions have been visited by each agents. This is checked by agent Afin and then Ainit. The programs of Afin are as follows. (0) ⟨e→e, e →h⟩, (1) ⟨e↔qf,1, e →h⟩, (2) ⟨h↔c(z), e →e⟩, (3) ⟨c(x)→¯c(x), e →e⟩, (4) ⟨¯c(x)↔h, e →e⟩, (5) ⟨c(y)↔#, e →e⟩, (6) ⟨h↔▷j, e →e⟩, (7) ⟨▷j→e, e ↔h⟩, (8) ⟨#→#, e →e, ⟩, where 1 ≤j≤n,c∈Σ,z=pref(perm(1 . . . n)), x=perm(1 . . . n), and y=perm(1 . . . n). Agent Afin nondeterministically consumes all symbols in the environmental string. It checks if each of them has been visited by every agent. This is done by introducing symbol hin the environmental string. Then, programs of the form (3) and (4), indicates that the symbol was visited by all agents. If there is a symbol which does not satisfy this property (program (5)), then symbol # is introduced which implies that the system will never stop (program (8)). Suppose that this is not the case, then after a while Afin will not be able to perform any of its programs. It is easy to see that Afin visited all letters in the environmental word. To complete the proof, Ainit has to visit all symbols as well. This is done by its programs of type (3). Since Afin visited all symbols, Ainit will do that too, thus, the computation halts. The reader my observe that the agents simulate the transitions of Mand that no agent can work simultaneously. Furthermore, programs of different agents cannot interfere. Thus, the language accepted by Mcan be verified by Π. Furthermore, every accepting computation of a word in Πis a verifying computation, thus Πstrongly verifies the language accepted by Π. 4 Conclusions In this paper we demonstrated a further connection between APCol systems and automata, as we proved that verifying APCol systems simulate one-way multihead finite automata. The new concept, the verifying computation opens further research directions: describing two-way multihead finite automata, jumping multihead finite automata in terms of APCol systems. We plan investigations in these topics in the future.