Matrix Languages, Register Machines, Vector Addition Systems

Matrix Languages, Register Machines, Vector Addition Systems Rudolf Freund1, Oscar H. Ibarra2, Gheorghe P˘aun3, Hsu-Chen Yen4 1Faculty of Informatics, Vienna University of Technology Favoritenstr. 9–11, A–1040 Vienna, Austria E-mail: [email protected] 2Department of Computer Science, University of California Santa Barbara, CA 93106, USA E-mail: [email protected] 3Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania, and Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: [email protected] 4Dept. of Electrical Engineering, National Taiwan University Taipei, Taiwan 106, ROC E-mail: [email protected] Summary. We give a direct and simple proof of the equality of Parikh images of languages generated by matrix grammars with appearance checking with the sets of vectors generated by register machines. As a particular case, we get the equality of the Parikh images of languages generated by matrix grammars without appearance checking with the sets of vectors generated by partially blind register machines. Then, we consider pure matrix grammars (i.e., grammars which do not distinguish terminal and nonterminal symbols), and prove the inclusion of the family of Parikh images of languages generated by such grammars (without appearance checking) in the family of sets of vectors generated by blind register machines, as well as the inclusion of reachability sets of vector addition systems in the family of Parikh images of pure matrix languages. For pure matrix grammars with a certain restriction on the form of matrices, also the converse of the latter inclusion is obtained. Thus, in view of the result from [9], we obtain the semilinearity of languages generated by pure matrix grammars (without appearance checking) with alphabets with at most five letters, with the considered restrictions on the form of matrices. A pure matrix grammar with five symbols, but without restrictions on the form of matrices, is produced which generates a non-semilinear language. 156 R. Freund, O.H. Ibarra, Gh. P˘aun, H.-C. Yen 1 Introduction For representing recursively enumerable sets of (vectors of) natural numbers since long time various models can be found in the literature, and many results are folklore. On the other hand, it seems to us that a direct proof of the equivalence of different models sometimes is missing or at least not present as a folklore result. Just recently, new motivations came from the area of membrane computing, where in various papers different models were used to establish the computational power of the specific models of P systems under consideration; in many cases, register machines (or counter automata) and matrix grammars with appearance checking were frequently used (see [12]). Most recently, some new results on P systems working in the sequential mode were elaborated, e.g., see [3], [5], and [6], thereby establishing connections to vector addition systems, matrix grammars without appearance checking, and partially blind counter automata, respectively. Interpreting some results proved in [5] and [6] in a suitable way, it turns out that via specific equivalent models of (tissue) P systems with antiport rules working in the sequential mode the equivalence in the generative power of two old (non-universal) models of computation was (re-)established, i.e., the Parikh sets of languages generated by matrix grammars without appearance checking coincide with the sets of vectors of natural numbers generated (or accepted) by partially blind counter automata (or partially blind register machines, respectively). In view of this quite astonishing coincidence, we are going to give a direct construction of a register machine simulating a matrix grammar and vice versa in Section 3; moreover, as an immediate consequence of these constructions we get a direct simulation of a partially blind register machine by a matrix grammar without appearance checking and vice versa. In Section 4 we investigate the relation of vector addition systems and vector replacement systems with pure matrix grammars and blind register machines. 2 Prerequisites By Nand Zwe denote the set of natural numbers (non-negative integers) and the set of integers, respectively. We refer to [14], [15], and [17] for the general elements of formal language theory we use here. We only specify that, for a string x∈V∗ and a symbol a∈V, by |x|we denote the length of xand by |x|athe number of occurrences of the symbol ain the string x. For w∈V∗with V={a1, . . . , an}, by ΨV(w) we denote the Parikh vector of w, i.e., ΨV(w)=(|w|a1,...,|w|an); this is extended to languages in a natural way. For a family FL of languages, by NFL we denote the family of length sets of language from F L and by P sF L the family of Parikh sets of vectors associated with languages in F L. By CF and RE we denote the families of context-free and of recursively enumerable languages, respectively. Thus, NRE and P sRE are the families of sets of natural numbers and of sets of vectors of natural numbers, respectively, which can be computed by Turing machines. Matrix Languages, Register Machines, Vector Addition Systems 157 Amatrix grammar (with appearance checking) is a construct G= (N, T, S, M, F ) where Nand Tare disjoint alphabets of nonterminal and terminal symbols, S∈N is the start symbol, Mis a finite set of sequences of the form (A1→x1, . . . , An→ xn), n≥1, of context-free productions over N∪T(with Ai∈N, xi∈(N∪T)∗, in all cases), and Fis a subset of the set of productions occurring in the matrices in M. For w, z ∈(N∪T)∗we write w=⇒zif there are a matrix (A1→x1, . . . , An→xn) in Mand strings wi∈(N∪T)∗,1≤i≤n+ 1, such that w=w1, z=wn+1,and, for all 1 ≤i≤n, either (1) wi=w0 iAiw00 i, wi+1 =w0 ixiw00 i, for some w0 i, w00 i∈(N∪T)∗, or (2) wi=wi+1, Aidoes not appear in wi, and the rule Ai→xiappears in F. The productions of a matrix are applied in the given order, possibly skipping those in Fif they cannot be applied – therefore we say that these productions are applied in the appearance checking mode. (Note that this directly corresponds to the checking for zero in subtract instructions of register machines.) The language generated by Gis defined by L(G) = {w∈T∗|S=⇒∗w}, where =⇒∗is the reflexive and transitive closure of the relation =⇒. The family of languages of this form is denoted by MATac. If the set Fis empty, then the grammar is said to be without appearance checking; the corresponding family of languages is denoted by MAT. Already at the end of sixties, directly or through the equivalence with programmed grammars of [13], it was proved that CF ⊂MAT ⊂MATac =RE, but the problem was formulated whether or not there are one-letter languages in the family MAT which are not regular. The problem was solved only in 1994, in [8], confirming a conjecture from [15] that such languages are regular (this situation resembles the case of one-letter context-free languages, which are also regular). In our proof given in the next section we will use a well-known normal form for matrix grammars: a matrix grammar G= (N, T, S, M, F ) is said to be in the binary normal form if N=N1∪N2∪ {S, #}, with these three sets mutually disjoint, and the matrices in Mare in one of the following forms: 1. (S→XA),with X∈N1, A ∈N2, 2. (X→Y, A →x),with X, Y ∈N1, A ∈N2, x ∈(N2∪T)∗,|x| ≤ 2, 3. (X→Y, A →#),with X, Y ∈N1, A ∈N2, 4. (X→λ, A →x), with X∈N1, A ∈N2,and x∈T∗,|x| ≤ 2. Moreover, there is only one matrix of type 1 (that is why we usually write it in the form (S→X0A0), in order to fix the symbols X, A present in it), and Fconsists exactly of all rules A→# appearing in matrices of type 3; # is a trap-symbol, because once introduced, it is never removed. A matrix of type 4 is used only once, in the last step of a derivation. For each matrix grammar there is an equivalent matrix grammar in the binary normal form. Details can be found in [4] and in [15]. The result holds true both for 158 R. Freund, O.H. Ibarra, Gh. P˘aun, H.-C. Yen grammars with appearance checking and without appearance checking – in this latter case we no longer have matrices of type 3. In fact, in the next section we shall use a slightly modified version of this binary normal form called f-binary normal form in [5], i.e., instead of the final matrices of type 4 there is only one single final matrix of the form (f→λ), for some special symbol f∈N1. In general, a grammar is called pure if it does not distinguish between terminal and nonterminal symbols. Thus, a pure matrix grammar (without appearance checking) is a triple G= (V, w, M), where Vis an alphabet, w∈V∗is the axiom (starting string), and Mis a finite set of matrices of the form (a1→u1, . . . , an→ un), where n≥1 and ai∈V, ui∈V∗for all 1 ≤i≤n. The language generated by Gis L(G) = {z∈V∗|w=⇒∗z}, with the derivation relation =⇒defined as in a non-pure matrix grammar. The family of languages of this form is denoted by pMAT . It is known (e.g., see [4]) that pMAT is incomparable with CF and that pMAT ⊂MAT. We now introduce register machines, in the generative (non-deterministic) version. Informally speaking, such a device consists of a specified number of counters which can hold any natural number, and which are handled according to a program consisting of labelled instructions. A counter can be increased or decreased by 1 – the decreasing being possible only if the counter holds a number greater than or equal to 1 (we say that it is non-empty) – and it can be checked whether it is empty. Formally, a (non-deterministic) register machine is a device R= (m, B, l0, lh, P) where m≥1 is the number of counters, Bis the (finite) set of instruction labels, l0is the initial label, lhis the halting label, and Pis the finite set of instructions labelled (hence uniquely identified) by elements from B(Pis also called the program of the machine). The labelled instructions are of the following forms: –l1: (ADD(r), l2, l3), 1 ≤r≤m(add 1 to counter rand non-deterministically go to one of the instructions with labels l2, l3), –l1: (SUB(r), l2, l3), 1 ≤r≤m(if counter ris not empty, then subtract 1 from it and go to the instruction with label l2, otherwise go to the instruction with label l3), –lh:HALT (the halt instruction, which can only have the label lh). A register machine generates a k-dimensional vector of natural numbers in the following way: we distinguish kcounters as output counters (without loss of generality, these can be the first kcounters), and we start computing with all mcounters being empty, from the instruction labelled by l0; if the computation reaches the instruction lh:HALT (we say that it halts), with all counters k+1, . . . , m being empty, then the values of counters 1,2, . . . , k form the vector generated by this computation. The set of all vectors from Nkgenerated in this way by Ris Matrix Languages, Register Machines, Vector Addition Systems 159 denoted by P s(R). If we want to generate only numbers (1-dimensional vectors), then we have the result of a computation in counter 1, and the set of numbers computed by Rin this way is denoted by N(R). By NRM and PsRM we denote the families of sets of natural numbers and of sets of vectors of natural numbers, respectively, generated by register machines. It is known (e.g., see [11], [17]) that P sRE =P sRM and NRE =NRM (actually, three counters suffice in order to generate any set from the family NRE, but this detail is not of special interest for what follows). In the case when a register machine cannot check whether a counter is empty we say that it is partially blind: the counters are increased and decreased by one as usual, but if the machine tries to subtract from an empty counter, then the computation aborts without producing any result (that is to say that the subtract instructions are of the form l1: (SUB(r), l2, abort)). Note that there is an implicit test for zero, at the end of a (successful) computation, where all counters k+ 1, . . . , mshould be empty, that is why we say that the device is partially blind. It is known (e.g., see [7]) that partially blind register machines (counter automata) are strictly less powerful than general register machines (hence than Turing machines). By NP BRM and P sP BRM we denote the families of sets of natural numbers and of sets of vectors of natural numbers, respectively, computed by partially blind register machines. If a partially blind register machine accepts the value of all counters 1,2, . . . , m, then this register machine is said to be blind (no counter is checked for zero during the computations or when reaching the final label lh). By NBRM and PsBRM we denote the families of sets of natural numbers and of sets of vectors of natural numbers, respectively, generated by blind register machines. Atechnical detail: In the proofs of Theorems 1 and 2, we will construct register machines of a slightly more relaxed form than defined above, i.e., the same label l1∈Bwill be allowed to be assigned to several instructions; when such a label is introduced by another instruction, then in the next step any of the instructions labelled by l1can be executed, non-deterministically chosen. However, it is easy to pass from such a “super-non-deterministic” register machine to a usual non-deterministic register machine: For instance, assume that there are two instructions •l1: (op0(r0), l0 2, l0 3) and l1: (op00(r00), l00 2, l00 3) with the same label l1(op0and op00 are any operations ADD or SUB). We can replace these instructions by the following ones: •l1: (ADD(1), l0 1, l00 1), l0 1: (SUB(1), l000 1, l000 1), l00 1: (SUB(1), liv 1, liv 1), l000 1: (op0(r0), l0 2, l0 3),and liv 1: (op00(r00), l00 2, l00 3), where l0 1, l00 1, l000 1, liv 1are new labels. 160 R. Freund, O.H. Ibarra, Gh. P˘aun, H.-C. Yen In this way, the number of instructions labelled with l1has been decreased by one and no new pair of instructions having the same label was introduced. Continuing this way, we can eliminate all duplicate labelling. Ak×mvector replacement system (VRS), see [10], is a triple (w0, U, W ), where w0∈Nk(start vector),U∈Nk×m(check matrix), and W∈Zk×m(addition matrix) such that, for any i, j with 1 ≤i≤kand 1 ≤j≤m, we have Ui(j) + Wi(j)≥0. A vector Wi∈Wis said to be enabled in a vector x∈Nkif and only if x≥Ui; as Ui+Wi≥0, adding Wito xyields x+Wi∈Nk. For a VRS γ= (w0, U, W), P s(γ) denotes the sets of vectors from Nkthat can be reached from w0by iteratively adding vectors from Wenabled in the vector computed so far. By V RS we denote the family of all sets of vectors of natural numbers generated by vector replacement systems in that way. Avector addition system (VAS) is a pair (w0, W ), where w0∈Nk(start vector) and W∈Zk×m(addition matrix); for a vector addition system γ= (w0, W), by Ps(γ) we denote the set of vectors reachable in γfrom w0by iteratively adding vectors from Win such a way that the resulting vectors always are in Nk.The family of all sets of vectors of natural numbers generated in that way by vector addition systems is denoted by V AS. From [9] it is known that the sets of vectors form V AS generated by vector addition systems of dimension k≤5 are semilinear, while vector addition systems of dimension six can already produce non-semilinear sets of vectors. Some counterparts of these results for pure matrix languages will be given in Section 4. 3 The Equivalence of Register Machines and Matrix Grammars We now elaborate direct constructions for showing the equivalence of register machines and matrix grammars as already mentioned in the Introduction, in its general form. Theorem 1. P sRM =P sMATac. Proof. Inclusion P sRM ⊆P sMATac: Let us consider a register machine R= (m, B, l0, lh, P ) with mcounters, meant to generate a set Ps(R)⊆Nk, for some kwith 1 ≤k≤m. We construct the matrix grammar G= (N, T, S, M, F ) where N={Ai|1≤i≤m} ∪ B∪ {#}, T={ai|1≤i≤k}, S=l0, M={(l1→Arl2), (l1→Arl3)|l1: (ADD(r), l2, l3)∈P} Matrix Languages, Register Machines, Vector Addition Systems 161 ∪ {(l1→l2, Ar→λ), (l1→l3, Ar→#) |l1: (SUB(r), l2, l3)∈P} ∪ {(lh→lh, Ai→ai)|1≤i≤k} ∪ {(lh→λ)}, and the set Fconsists of all productions of the form Ar→#, 1 ≤r≤m, from the matrices of M. The equality P s(R) = ΨT(L(G)) is obvious: a computation in Rhalts correctly only after reaching the instruction lh:HALT, with all registers k+ 1, . . . , m being empty, and this corresponds to the fact that a derivation in Greaches a terminal string only after introducing the nonterminal symbol lh, in the presence of which the nonterminal symbols Aiare transformed into the terminal symbols ai,1≤i≤ k(if any nonterminal symbol Aj, j > k, is still present, then it cannot be removed, hence, the sentential form cannot be turned into a terminal one). Inclusion PsRM ⊇PsMATac: Now consider a matrix grammar G= (N, T, S, M, F ) in the f-binary normal form, i.e., with N=N1∪N2∪ {S, #}, and the matrices only being of the four forms specified in the previous section. Without any loss of generality (because we are interested in the Parikh image of the language L(G) only), we can assume that T={a1, . . . , ak}and N2= {Ak+1, . . . , As}, for some k, s with 1 ≤k < s. Hence, by αj,1≤j≤s, we denote a symbol from T∪N2with the understanding that αi=aifor 1 ≤i≤kand αi=Aifor k+ 1 ≤i≤s. Let us suppose all matrices of types 2 from Mto be labelled in a one-to-one manner by m1, . . . , mn. We then construct the register machine R= (s, B, l0, lh, P ) where B={S, #} ∪ N1 ∪ {hmi,1i | mi: (X→β, A →x)∈M, β ∈N1∪ {λ},1≤i≤n, with |x|= 1} ∪ {hmi,1i,hmi,2i | mi: (X→β, A →x)∈M, β ∈N1∪ {λ},1≤i≤n, with |x|= 2}, l0=S, P={S: (ADD(r), X, X)|(S→XAr)∈M, for some k+ 1 ≤r≤s} ∪ {X: (SUB(r), Y, #) |(X→Y, Ar→λ)∈M, for some k+ 1 ≤r≤s} ∪ {X: (SUB(r),hmi,1i,#), hmi,1i: (ADD(j), Y, Y )|mi: (X→Y, Ar→αj)∈M for some k+ 1 ≤r≤sand 1 ≤j≤s} ∪ {X: (SUB(r),hmi,1i,#), hmi,1i: (ADD(j1),hmi,2i,hmi,2i), hmi,2i: (ADD(j2), Y, Y )|mi: (X→Y, Ar→αj1αj2)∈M, 162 R. Freund, O.H. Ibarra, Gh. P˘aun, H.-C. Yen for some k+ 1 ≤r≤sand 1 ≤j1, j2≤s} ∪ {X: (SUB(r),#, Y )|(X→Y, Ar→#) ∈M, for some k+ 1 ≤r≤s} ∪ {f:HALT} ∪ {# : (ADD(s),#,#)}. The matrices of Gare simulated by the register machine Ras follows: the nonterminal symbols from N1are labels of instructions. A rule Ar→αj1αj2is simulated by first subtracting one from register rand then adding one to each of the registers j1, j2(with the cases when one or two of the symbols αj1, αj2is missing being still simpler); these steps are controlled by the labels hmi,1i,hmi,2i, and they start in the presence of label Xand end with introducing the label Y, thus completing the simulation of the matrix mi: (X→Y, Ar→αj1αj2). The matrices (X→Y, A →#) of type 3 are directly simulated by a subtract instruction X: (SUB(r),#, Y ). Entering label # (the “trap”) leads to an infinite loop with # : (ADD(s),#,#). The simulation of the terminal matrix (f→λ) introduces the label fof the halt instruction. If the derivation in Ghas been a terminal one, then all registers k+1, . . . , s are empty at that moment, hence, the computation in Rends correctly. Thus, the equality ΨT(L(G)) = Ps(R) follows, and observing the technical detail from the previous section concerning the elimination of duplicate labels concludes the proof. 2 If we start from a partially blind register machine, then the matrices of the form (l1→l3, Ar→#) can be omitted in the construction of the matrix grammar from the first part of the previous proof, hence, we obtain a matrix grammar without appearance checking. Conversely, if we start the second part of the proof from a matrix grammar without appearance checking, then the register machine we obtain will be partially blind: the only subtract instructions l1: (SUB(r), l2, l3) having the label l3different from the trap # are those corresponding to matrices of type 3 – which now are missing. Consequently, from the proof of Theorem 1 we immediately infer the following result: Corollary 1. P sMAT =PsP BRM and NMAT =NPBRM. 4 Pure Matrix Grammars and Vector Addition Systems The proof of Theorem 1 cannot be repeated for pure matrix grammars, because we cannot use any auxiliary symbol, but some counterparts of it can be obtained in this case, too. Since a (pure) matrix grammar with λas the starting string can only generate the language {λ}, in our subsequent discussion we assume that the VAS under consideration starts with a non-zero initial vector. More about this will be said later. Matrix Languages, Register Machines, Vector Addition Systems 163 Theorem 2. V AS ⊂PspMAT ⊆PsBRM. Proof. (Sketch) Given a vector addition system (with vectors of dimension k≥1) γ= (w0, W ), we construct a pure matrix grammar G= (V, w, M) with V= {a1, . . . , ak},ΨV(w) = w0, and with the matrices in Massociated with vectors Wi∈Wconstructed as follows: for a vector Wi, we consider the set of matrices obtained by examining each component Wi(j) of the vector and proceeding as follows: if Wi(j) is positive, then we take a rule aq→aqaWi(j) j, for some 1 ≤q≤k, otherwise we have to take Wi(j) rules of the form aj→λ. Thus, for the same vector Wiwe get a set of matrices, obtained by combining all possibilities to take the rules aq→aqaWi(j) jfor those components Wi(j) which are positive. The idea is that we have to add Wi(j) occurrences of aj, and to this aim we need a rewriting rule aq→ufor some symbol aqwhich is already present in the string. As an important additional constraint, we can suppose that we always have at least one symbol in the string – except when generating the empty string. More precisely, in the vector addition system γwe may suppose that each “computation” to a vector vdifferent from (0,0, . . . , 0) never passes through the vector (0,0, . . . , 0). Indeed, if to a vector v0we add a vector Wi,1≤i≤t, such that v0+Wi= (0,0, . . . , 0), and then we add Wj, we immediately infer that all components of (the non-zero vector) Wjmust be non-negative, hence, we can commute Wiand Wj, thus computing (v0+Wj) + Wi=Wjinstead of (v0+Wi) + Wj; in that way, (0,0, . . . , 0) can be avoided avoided as an immediate result. Hence, to the matrices constructed so far, we have to add all matrices associated (in the sense of the preceding arguments) with vectors Wj+Wiwhere Wjis a positive vector. In this way, using one of the matrices associated as above with a vector Wior Wj+Wiexactly corresponds to the addition of the associated vector in the VAS. Thus, P s(γ) = ΨV(L(G)); hence, we have proved the inclusion V AS ⊆PspMAT. Now we show the strictness of this inclusion, i.e., V AS 6=P spMAT : Consider the following pure matrix grammar G1= (V, aab, M) where V={a, b}, M={(a→λ, a →a, b →λ),(a→λ, a →a)}. Clearly ΨV(L(G1)) = {(|w|a,|w|b)|aab =⇒∗w}={(2,1),(1,0),(1,1)}. We now show that no VAS can have this set as its reachability set. Assume, on the contrary, that there were a VAS γ= (v0, V ) with Ps(γ)={(2,1),(1,0),(1,1)}. First note that v06= (1,0) and v06= (1,1), because otherwise, (1,0) =⇒∗(2,1) or (1,0) =⇒∗(1,1), respectively, thus yielding infinite reachability sets. As a consequence, v0= (2,1). Consider two cases: 1. Case 1: (2,1) =⇒(1,0). Then (−1,−1) ∈Xand therefore (1,1) + (−1,−1) ∈ Ps(γ) – a contradiction. 2. Case 2: (2,1) →(1,1). Then (−1,0) ∈Xand therefore (1,0)+(−1,0) ∈P s(γ) – a contradiction.