On a Class of P Automata as a Machine Model for Languages over Infinite Alphabets

On a Class of P Automata as a Machine Model for Languages over Infinite Alphabets ? Gy¨orgy Vaszil Computer and Automation Research Institute Hungarian Academy of Sciences Kende utca 13-17, 1111 Budapest, Hungary E-mail: [email protected] Summary. We show how P automata having a finite description and working with a finite object-alphabet can be used to describe languages over countably infinite alphabets. We propose to relate the language classes characterized by different types of P automata to some of the existing characterizations of language classes over infinite alphabets, and give an upper bound for the class of languages accepted by the class of one of the most straightforward and least complicated variants of these types of P automata. 1 Introduction Membrane systems, or P systems are distributed computing models inspired by the functioning of the living cell. Their main components are membrane structures consisting of membranes hierarchically embedded in the outermost skin membrane. Each membrane encloses a region containing a multiset of objects and possibly other membranes. Each region has an associated set of operators working on the objects contained by the region. These operators can be of different types, they can change the objects present in the regions or they can provide the possibility of transferring the objects from one region to another one. The system might also have additional capabilities such as, for example, a dynamically changing membrane structure, or special constraints (like context conditions or priority relations) added to the sets of operators. The evolution of the objects inside the membrane structure from an initial configuration to a somehow specified end configuration corresponds to a computation having a result which is derived from some properties of the specific end configuration. Several variants of the basic notion have been introduced and studied proving the power of the framework, see the monograph [11] for a summary of notions and results of the area. As the reader might notice, this machinery has relatively strong capabilities, so it might seem reasonable to ?Research supported in part by the Hungarian Scientific Research Fund “OTKA” grants T042529 and F037567. 318 Gy. Vaszil look for as simple P system variants as possible, as for example systems using communication rules only. For more details on these variants, see [8], [10]. Besides their simplicity, the introduction of P automata in [2] was motivated by the idea of using P systems as language acceptors. The objects in a P automaton may move through the membranes from region to region, but they may not be modified during the functioning of the systems, and furthermore, the “words” accepted by a P automaton correspond to the sequences of multisets containing the objects entering from the environment in each step of the evolution of the system. To characterize formal languages, the strings of multisets read by the P automaton have to be mapped to strings of symbols of an alphabet. If this mapping uses erasing, that is, some possible input multisets are mapped to the empty symbol, ε, then the characterization of recursively enumerable languages can be obtained. This was already established in [2] stating that for any recursively enumerable language, there is a P automaton accepting the image of the language under a certain mapping. Similar results were also obtained in [4], [5], for P automata with different features and different mappings to obtain the recursively enumerable language. If the correspondence between the input multisets and the alphabet symbols is established by a mapping which is non-erasing and “simple”, that is, each possible input multiset is mapped to a symbol of a finite alphabet in some computationally “easy” way (except the empty multiset which is still mapped to ε), then the situation is different as shown in [3]. In the case of sequential rule application, the number of possible input multisets is finite, so the correspondence between the input multisets and the alphabet symbols is natural. P automata with these types of mappings and sequential application of symport/antiport rules characterize a subclass of the languages accepted by Turing machines reading the input tape one-way and using logarithmic space on the work-tape. (The interested reader is referred to [3] for the exact definitions and challenging open problems concerning this computational complexity class.) If the symport/antiport rules are applied in the maximal parallel manner, then the number of potential inputs is infinite, thus, the infinite set of possible inputs has to be mapped to a finite alphabet. In this case (if the mapping is non-erasing and “simple”, as above) the characterization of the class of context-sensitive languages is obtained. Because of the infinite number of potential input multisets, it is rather natural to consider a P automaton with parallel rule application as a machine working with strings of symbols over infinite alphabets. The only thing necessary to obtain such a model is to define a mapping establishing the correspondence between the input multisets and the symbols of the infinite alphabet. In the following we begin the exploration of this idea. First we introduce the model, then present two examples which also give a hint towards the relationship of the language classes described by P automata and those proposed in [9] and [6]. Finally we present a theorem on the limits of one of the “easiest” infinite alphabet language class described by P automata. P Automata for Languages over Infinite Alphabets 319 2 Preliminaries and Definitions We first recall the notions and the notations we use. The reader is assumed to be familiar with the basics of formal language theory, for details see [12]. Let Σbe a not necessarily finite, but countable set of symbols called alphabet. Let Σ∗be the set of all words over Σ, that is, the set of finite strings of symbols from Σ, and let Σ+=Σ∗− {ε}where εdenotes the empty word. Let Ube a set - the universe - of objects, and let Ndenote the set of natural numbers. A multiset is a pair M= (V, f),where V⊆Uand f:U→Nis a mapping which assigns to each object a∈Vits multiplicity, if a6∈ Vthen f(a) = 0. The support of M= (V, f) is the set supp(M) = {a∈V|f(a)≥1}. If supp(M) is a finite set, then Mis called a finite multiset. The set of all finite multisets over the set Vis denoted by V◦. The number of objects in a finite multiset M= (V, f),the cardinality of M, is defined by card(M) = Pa∈Vf(a).We say that a∈M= (V, f) if a∈supp(M). M1= (V1, f1)⊆M2= (V2, f2) if supp(M1)⊆supp(M2) and for all a∈V1, f1(a)≤f2(a). The union of two multisets is defined as (M1∪M2) = (V1∪V2, f0) where for all a∈V1∪V2,f0(a) = f1(a)+f2(a), the difference is defined for M2⊆M1 as (M1−M2) = (V1−V2, f00) where f00(a) = f1(a)−f2(a) for all a∈V1−V2, and the intersection of two multisets is (M1∩M2) = (V1∩V2, f000) where for a∈V1∩V2, f000(a) = min(f1(a), f2(a)), min(x, y) denoting the minimum of x, y ∈N. We say that Mis empty, denoted by ², if its support is empty, supp(M) = ∅. A multiset Mover the finite set of objects Vcan be represented as a string w over the alphabet Vwith |w|a=f(a) where a∈Vand where |w|adenotes the number of occurrences of the symbol ain the string w, and with εrepresenting the empty multiset ². In the following we sometimes identify the finite multiset of objects M= (V, f) with the word wover Vrepresenting M, thus we write w∈V◦, or sometimes we enumerate the not necessarily distinct elements a1, . . . , anof a multiset as M={{a1, . . . , an}}, by using double brackets to distinguish from the usual set notation. A P system is a structure of hierarchically embedded membranes, each having a label and enclosing a region containing a multiset of objects and possibly other membranes. The out-most membrane which is unique and usually labelled with 1, is called the skin membrane. The membrane structure is denoted by a sequence of matching parentheses where the matching pairs have the same label as the membranes they represent. If x∈ {[i,]i|1≤i≤n}∗is such a string of matching parentheses of length 2n, denoting a structure where membrane icontains membrane j, then x=x1[ix2[jx3]jx4]ix5for some xk∈ {[l,]l|1≤l≤n, l 6=i, j}∗,1≤k≤5. If membrane icontains membrane j, and there is no other membrane, k, such that kcontains jand icontains k(x2and x4above are strings of matching parentheses themselves), then we say that membrane iis the parent membrane of j. The evolution of the contents of the regions of a P system is described by rules associated to the regions. Applying the rules synchronously in each region, the system performs a computation by passing from one configuration to another one. 320 Gy. Vaszil In the following we concentrate on communication rules called symport or antiport rules. A symport rule is of the form (x, in) or (x, out), x ∈V◦. If such a rule is present in a region i, then the objects of the multiset xmust enter from the parent region or must leave to the parent region, respectively. An antiport rule is of the form (x, in;y, out), x, y ∈V◦, in this case, objects of xenter from the parent region and in the same step, objects of yleave to the parent region. All types of these rules might be equipped with a promoter or inhibitor multiset, denoted as (x, in)|Z,(x, out)|Z, or (x, in;y, out)|Z, x, y ∈V◦, Z ∈ {z, ¬z|z∈V◦}, in which case they can only be applied if region icontains the objects of multiset z, or if Z=¬z, then region imust not contain the elements of z. (For more on symport/antiport see [10], for the use of promoters see [8].) Now we recall the formal definition of a P automaton. Definition 1 AP automaton is a construct Γ= (V, µ, (w1, P1, F1), . . . , (wn, Pn, Fn)) where n≥1 is the number of membranes, Vis a finite set of objects, µis a membrane structure of nmembranes with membrane 1 being the skin membrane, and for all i, 1≤i≤n, •wi∈V◦is the initial contents (state) of region i, that is, it is the finite multiset of all objects contained by region i, •Piis a finite set of communication rules associated to membrane i, they can be symport rules or antiport rules, with or without promoters or inhibitors, as above, and •Fi⊆V◦is a finite set of finite multisets over Vcalled the set of final states of region i. If Fi=∅, then all the states of membrane iare considered to be final. To simplify the notations we denote symport and antiport rules with or without promoters/inhibitors as (x, in;y, out)|Z,x, y ∈V◦, Z ∈ {z, ¬z|z∈V◦}where we also allow x, y, z to be the empty string. If y=εor x=ε, then the notation above denotes the symport rule (x, in)|Zor (y, out)|Z, respectively, if Z=ε, then the rules above are without promoters or inhibitors. The n-tuple of finite multisets of objects present in the nregions of the P automaton Γdescribes a configuration of Γ, the n-tuple (w1, . . . , wn)∈(V◦)nis the initial configuration. The application of the rules can take place in a sequential, or in a maximally parallel manner. Here we only consider parallel rule application, but we keep the subscript “par” in order to emphasize that maximal parallel application is just one of the different possibilities. Definition 2 The transition mapping of a P automaton is a partial mapping δpar :V◦×(V◦)n→2(V◦)n. These mappings are defined implicitly by the rules of the rule sets Pi,1≤i≤n. For a configuration (u1, . . . , un), (u0 1, . . . , u0 n)∈δpar(u, (u1, . . . , un)) holds, that is, while reading the input u∈V◦the automaton may enter the new configuration (u0 1, . . . , u0 n)∈(V◦)n, if there exist rules as follows. P Automata for Languages over Infinite Alphabets 321 •For all i, 1≤i≤n, there is a multiset of rules Ri={{ri,1, . . . , ri,mi}}, where ri,j = (xi,j, in;yi,j, out)|Zi,j ∈Piwith z⊆uifor Zi,j =z∈V◦, and z∩ui=² for Zi,j =¬z, z ∈V◦,1≤j≤mi, satisfying the conditions below, where xi, yi denote the multisets S1≤j≤mixi,j and S1≤j≤miyi,j, respectively. Furthermore, there is no rule occurrence r∈Pj, for any j, 1≤j≤n, such that if r∈P1 then r6= (x, in)|Z, but the rule multisets R0 iwith R0 i=Rifor i6=jand R0 j={{r}} ∪ Rj, also satisfy the conditions. The conditions are given as 1. x1=u, and 2. Sparent(j)=ixj∪yi⊆ui,1≤i≤n, and then the new configuration is obtained by u0 i=ui∪xi−yi∪[ parent(j)=i yj−[ parent(j)=i xj,1≤i≤n. The definition of the transition given above differs from the one presented [3]. The difference comes from the use of symport rules of the form (x, in)|Zin the region of the skin membrane. In [3] (and other previous work on P automata), the environment is considered to have an infinite supply of objects in every step of the computation, so the maximal parallel use of a symport rule of the above form would result in the import of the objects of xin an infinite number of copies, thus, the use of these types of rules is simply not allowed. Here, for the sake of being as general as possible, we allow the use of rules of type (x, in)|Zin the skin membrane, and say that the use of any number of these rules is considered to be maximally parallel. We define the sequence of multisets of objects accepted by the P automaton as the sequence of input multisets which appear in the environment and are consumed by the skin membrane in each computational step while the system reaches a final state, a configuration where for all jwith Fj6=∅, the contents uj∈V◦of membrane jis “final”, i.e., uj∈Fj. Definition 3 Let us extend δpar to ¯ δpar, a function mapping (V◦)∗, the sequences of finite multisets over V, and (V◦)n, the configurations of Γ, to new configurations. We define ¯ δpar as 1. ¯ δpar(v, (u1, . . . , un)) = δpar(v, (u1, . . . , un)), v, ui∈V◦, 1 ≤i≤n, and 2. ¯ δpar((v1). . . (vs+1),(u1, . . . , un)) = Sδpar(vs+1,(u0 1, . . . , u0 n)) for all (u0 1, . . . , u0 n)∈¯ δpar((v1). . . (vs),(u1, . . . , un)), vj, ui, u0 i∈V◦, 1≤i≤n, 1≤j≤s+ 1. Note that we use brackets in the multiset sequence (v1). . . (vs+1)∈(V◦)∗in order to distinguish it from the multiset v1∪...∪vs+1 ∈V◦. Definition 4 Let Γbe a P automaton as above with initial configuration (w1, . . . , wn), let Σbe an alphabet, and let f:V◦−→ Σ∪ {ε}be a mapping with f(x) = εif and only if x=². 322 Gy. Vaszil The language accepted by Γis defined as L(Γ, f) = {f(v1). . . f(vs)∈Σ∗|(u1, . . . , un)∈¯ δpar((v1). . . (vs),(w1, . . . , wn)) with uj∈Fjfor all jwith Fj6=∅,1≤j≤n, 1≤s}. Obviously, the choice of the mapping fis essential. It has to be “easily” computable because the power of the P automaton should be provided by the underlying membrane system and not by fitself. The notion of “easiness”, however, greatly depends on the context we are working in, so we do not give it a general specification here. 3 Examples Before continuing the study of our model, we recall two previous attempts to define the generalization of the notion of “regular languages” to the case of infinite alphabets. The language class denoted here as L(REG∞ 1) is characterized in [9] through an encoding of the words over the infinite alphabet Σ={a1, a2, . . .}to words over the binary alphabet {0,1}defined as γ(ai) = 0i−11 for each i≥1. For a language L⊆Σ∗, the property of L∈ L(REG∞ 1) holds if γ(L) = {γ(w)| w∈L} ⊆ {0,1}∗is a regular language. The class of L(REG∞ 1) has several nice properties, but also strong limitations, for example, the simple language L1= {aia1ai|i≥1} 6∈ L(REG∞ 1). A different language class, denoted here as L(REG∞ 2), is proposed in [6] by generalizing the notion of finite automata to so called finite memory automata which process inputs over infinite alphabets. Without going into the details, a finite memory automaton is a finite automaton equipped with a finite number of registers which are used for storing certain symbols of the input word in some well defined way during the computation. To be able to give a finite description of the machine, the transitions are based on the finitely many possible states of the internal control and the equality or non-equality of the input with the contents of one or more of the finitely many registers. The class of L(REG∞ 2) also has its limitations, for example, L2={a2i|i≥1} 6∈ L(REG∞ 2). Note also that L2∈ L(REG∞ 1) and L1∈ L(REG∞ 2), thus, L(REG∞ 1) and L(REG∞ 2) are incomparable. Now we give two examples of P automata by showing how L1and L2can be accepted. Example 1 Let Γ1= ({a, #,$,@},[1[2]2]1,(w1, P1, F1),(w2, P2, F2)) with w1={{#}}, P1={(a, in)|#,(a, in; $, out),(a, in;a, out)|@}, F1=∅,and w2={{$,@}}, P Automata for Languages over Infinite Alphabets 323 P2={(#, in; $, out),(a, in; @, out)|#,(a, out)}, F2={ {{#}} }. In the first step, an arbitrary number of asymbols, say k, is imported into the system and the symbol # in region 1 is exchanged to the symbol $ from region 2. In the second step, one asymbol from the environment is exchanged to the symbol $, and one asymbol and the @ symbol is exchanged between region 1 and 2. Now the number of asymbols in region 1 is k, so using the rule (a, in;a, out)|@, the same number, k, of asymbols are imported to the system from the environment while one asymbol is sent out of the second region, thus, the system reaches a final state. If for x∈V◦and Σ={a1, a2, . . .}we have f(x) = acard(x), then L(Γ1, f) = L1={aia1ai|i≥1}. Example 2 Let Γ2= ({a, #},[1[2]2]1,(w1, P1, F1),(w2, P2, F2)) with w1={{#}}, P1={(a, in)|#}, F1={{²}},and w2=², P2={(#, in),(aa, in)|#}, F2=∅. This system inputs an arbitrary number of asymbols from the environment in the first computational step while also moving the symbol # to region 2. After the first step, no more input from the environment is possible, but using the rules (aa, in)|#the system moves an even number of asymbols from the first region to the second. If there is nothing left in the first region, thus, if the number of a symbols input in the first step was even, the system enters the final state. If for x∈V◦and Σ={a1, a2, . . .}we again have f(x) = acard(x), then L(Γ2, f) = L2={a2i|i≥1}. Before we abandon this line of investigation, at least for the present paper, we mention that similar approaches to the ones described above also exist for the definition of the class of context-free languages over infinite alphabets, see [9] and [1]. To establish the precise relationship of the language classes described by P automata and these infinite alphabet analogues of regular and context-free languages would certainly be an interesting and fruitful research topic (not to mention the comparison with the other – not too many – classes of infinite alphabet languages which can be found in the literature). 4 A Preliminary Result For now, we would like to present a theorem providing an upper bound to the power of those P automata which use mappings between the input multisets and 324 Gy. Vaszil the infinite alphabet that are similar to those of the previous examples, namely, if Σis an infinite alphabet with Σ={a1, a2, . . .}, then let Fbe the class of mappings f:V◦−→ Σ∪ {ε}defined as f(M) = ajwhere j=card(M), and furthermore, if f−1(ai) = M, then M= ({a}, g) for a fixed element a∈Vand g(a) = j, thus, the possible input multisets consist of different number of occurrences of a single object. Now let us denote by L(PA, card) the class of languages L(Γ, f) over Σfor some P automata Γand mapping f∈F, and let also the value of the integer expressed by the binary string x∈ {1}{0,1}∗be denoted by val(x). We present the following theorem mainly for the purpose of demonstrating a type of the results which can be expected in this framework and to invite the reader to continue this chain of thoughts by trying to relax one or more of the very strict conditions of the statement. Theorem 1. If L∈ L(PA, card)then γ(L)∈ L(CS3)where γ:Σ∗→ {0,1,$}∗ defined by γ(ai) = x$with x∈ {1}{0,1}∗, val(x) = ifor all ai∈Σand L(CS3)denotes the class of context-sensitive languages over the three letter alphabet {0,1,$}. Proof. Let Γbe a P automaton and let L=L(Γ, f) for some f∈Fas above. Consider now a Turing machine having one read only input tape and n2work-tapes where nis the number of membranes of the P automaton. The input alphabet is {0,1,$}, the work-tape alphabet is {0,1}. What this Turing machine does, is keeping track of the configurations of Γby writing (in binary notation) the number of objects in each membrane on the first nwork-tapes and simulating the configuration changes using the rest of the tapes for keeping track of intermediate results. Without entering any details of the construction (which is very similar to the proof of Theorem 1 in [3]) we intend to convince the reader that this is not only possible, but it is possible using a workspace which is a linear function of the length of the input. The rules and the position of the finite number of input symbols can be encoded in the finite control and all the additional information necessary to record the configurations of Γis stored on the first nwork-tapes. The Turing machine first writes the number of symbols leaving from each membrane to all of the others using the rest of the work-tapes making sure that the simulated rule application is maximally parallel, and also checking whether the number of objects given by the next binary sequence of the input word can be read from the environment. Then it updates the values corresponding to the configuration of Γ stored on the first nwork-tapes. Since the number of work-tapes is fixed, and the numbers which need to be written on the individual tapes are bounded by the sum of the values of binary sequences of the input, not to mention the simple computation of fand f−1, this whole process can be realized in linear space. 2 P Automata for Languages over Infinite Alphabets 325 5 Conclusion We have proposed the idea of using P automata for the description and classification of languages over infinite alphabets which is a so far unexplored area with a whole lot of research topics yet to be studied. For easier orientation we would like to stress two important problems which deserve to be the first among the questions that need to be investigated. First, it would be necessary to try to relate the model to existing characterizations of languages over infinite alphabets, some of which are mentioned in the earlier sections. Secondly, to investigate the role of the choice of f, the mapping between the input multisets and the infinite alphabet would be of great importance. It would be necessary to find mappings which are easily computed but complicated enough in order to not suppress the power of the underlying membrane framework (as it is probably suppressed by members of the class Fof Theorem 1). References 1. E.H.Y. Cheng, M. Kaminski: Context-free languages over infinite alphabets. Acta Informatica, 35 (1998), 245–267. 2. E. Csuhaj-Varj´u, Gy. Vaszil: P Automata. In Pre-Proceedings of the Workshop on Membrane Computing WMC-CdeA 2002 (Gh. P˘aun, C. Zandron, eds.), Curtea de Arge¸s, Romania, August 19-23, 2002. Pub. No. 1 of MolCoNet-IST-2001-32008 (2002) 177–192, and also in Membrane Computing, (Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron, eds.), LNCS 2597, Springer-Verlag, Berlin, 2003, 219–233. 3. E. Csuhaj-Varj´u, O.H. Ibarra, Gy. Vaszil: On the computational complexity of P automata. In Preliminary Proceedings of DNA 10, Tenth International Meeting on DNA Computing (C. Ferretti, G. Mauri, C. Zandron, eds.), June 7-10, 2004, University of Milano-Bicocca, 2004, 97–106. 4. R. Freund, C. Mart´ın-Vide, A. ObtuÃlowicz, Gh. P˘aun: On three classes of automatalike P systems. In Developments in Language Theory. 7th International Conference, DLT 2003, Szeged, Hungary, July 2003 (Z. ´ Esik, Z. F¨ul¨op, eds.), LNCS 2710, Springer-Verlag, Berlin, 2003, 292–303. 5. R. Freund, M. Oswald: A short note on analysing P systems. Bulletin of the EATCS, 78 (October 2002), 231–236. 6. M. Kaminski, N. Francez: Finite-memory automata. Theoretical Computer Science, 134, (1994), 329–363. 7. M. Madhu, K. Krithivasan: On a class of P automata. Intern. J. Computer Math., 80, 9 (2003), 1111–1120. 8. C. Mart´ın-Vide, A. P˘aun, Gh. P˘aun: On the power of P systems with symport rules. Journal of Universal Computer Science, 8, 2, (2002), 317–331. 9. F. Otto: Classes of regular and context-free languages over countably infinite alphabets. Discrete Applied Mathematics, 12, (1985), 41–56. 10. A. P˘aun, Gh. P˘aun: The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3, (2002), 295–306. 11. Gh. P˘aun: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002. 12. G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages. Springer-Verlag, Berlin, 1997.