Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems

Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems Artiom Alhazov1, Omar Belingheri2, Rudolf Freund3, Sergiu Ivanov4, Antonio E. Porreca2, and Claudio Zandron2 1Institute of Mathematics and Computer Science Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova E-mail: [email protected] 2Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy E-mail: {o.belingheri@campus,porreca@disco,zandron@disco}.unimib.it 3Faculty of Informatics, TU Wien Favoritenstraße 9-11, 1040 Vienna, Austria E-mail: [email protected] 4Universit´e Paris Est, France E-mail: [email protected] Summary. In this paper we consider P systems working with multisets with integer multiplicities. We focus on a model in which rule applicability is not influenced by the contents of the membrane. We show that this variant is closely related to blind register machines and integer vector addition systems. Furthermore, we describe the computational power of these models in terms of linear and semilinear sets of integer vectors. 1 Introduction P systems have been traditionally viewed as hierarchical processors of multisets [11]. In the list of open problems disseminated in 2015 [10], Gheorghe P˘aun suggested going beyond the traditional setting and considering multisets in which objects would not be restricted to having natural multiplicities. Several possible approaches have been suggested since then, including the one from [3], which defines generalised multisets as taking multiplicities from finitely generated, totally ordered Abelian groups. The work [1] takes a different approach — the objects of the P system are partitioned into two classes: regular objects, which may have any integer multiplicity, and “catalysts”, which may only appear in a bounded number of copies and cannot be consumed without being immediately reproduced. Thus, the regular objects cannot influence the applicability of rules, while the always bounded 28 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron catalysts induce a finite set of “rule teams” which can be applied in parallel in one step. The virtual absence of applicability conditions and the finiteness of the “teams” hints at the possibility of seeing them as integer vectors; in this case the P system itself can be seen as evolving by sequentially adding such vectors to the contents of its membranes. Even though this vision is quite reminiscent of the folklore vector addition systems (VAS), the latter model is actually limited to having natural vectors as configurations [2, 8]. On the other hand, P systems manipulating integer multisets allow symbols with negative multiplicities to appear. It turns out that vector addition systems without the limitation of having natural configurations (integer VAS) have received relatively little attention in the literature [7]. Another related model which has received notoriously little attention are the blind register machines, whose registers are allowed to range over the whole set of integers. Blind counter automata have been introduced and studied as string recogniser devices by Sheila Greibach in [6]; their adaptation to recognising vectors of integer numbers seems quite relevant to the study of multisets with integer multiplicities. In the present work we bring together the three models — P systems over integer multisets as defined in [1], integer vector addition systems, and blind register machines — and formally show the connections between their different variants. We also give detailed characterisations of their computing power in terms of linear and semilinear sets of natural and integer vectors. The article is structured as follows. Section 2 recalls some notions used throughout the paper, in particular semilinear sets and vector addition systems. Section 3 gives a general definition of a register machine over a set A, and then defines blind, partially blind, and conventional register machines within this general framework. Section 4 defines the model of integer vector addition P systems and gives some details as to their semantics. Section 5 investigates the power of blind register machines and gives characterisations in terms of semilinear sets of vectors. Finally, Section 6 studies the power integer vector addition systems with and without membranes, and compares different variants of the models between themselves and with blind register machines. 2 Preliminaries The reader is assumed to be familiar with the basic notions of formal languages and membrane computing; see [12] for a comprehensive introduction to both. 2.1 Linear Sets The N-linear set of Z-vectors (or just linear set of Z-vectors) generated by a set of vectors A={a1,· · · ,ad} ⊆ Znand an offset a0∈Znis defined as follows: Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems 29 hA, a0iN=(a0+ d X i=1 kiaiki∈N,1≤i≤d). We underline that the vectors are over Z, but the coefficients are from N(we will also consider the special case when A∪ {a0} ⊆ Nn; this would be an N-linear set of N-vectors, or just a linear set, a well-known concept from Formal Language Theory). AZ-linear set of Z-vectors hA, a0iZ=(a0+ d X i=1 kiai|ki∈N,1≤i≤d) can be considered, too. It corresponds precisely to the linear vector space notion from the classic course of Linear Algebra. However, it is also a particular case. Indeed, it is easy to see that hA, a0iZ=hB, a0iNfor B={a1,· · · ,ad,−a1,· · · ,−ad}. If the offset a0is the zero vector, we call the corresponding linear set homogeneous. Apositive-restricted N-linear set of Z-vectors generated by Aand an offset a0is defined to be the N-linear set of Z-vectors generated by A, restricted to non-negative vectors only: hA, a0i+ Z={x∈ hA, a0iZ|x≥0}, where x≥0 means that every component of xis non-negative. We will use the notations ZnLINN,NnLINN,ZnLINZ, and Zn +LINNto refer to the classes of all N-linear sets of Z-vectors, N-linear sets of N-vectors, Z-linear sets of Z-vectors, and positive restricted N-linear sets of Z-vectors of dimension n, correspondingly. Semilinear sets are defined as finite unions of the corresponding types of linear sets. We will use the notations ZnSLINN,NnSLINN,ZnSLINZ and Zn +SLINNto refer to the families of N-semilinear sets of Z-vectors, N- semilinear sets of N-vectors, Z-semilinear sets of Z-vectors, a nd positive-restricted N-semilinear sets of Z-vectors of dimension n, respectively. In case no particular restriction is imposed on the dimension, nwill be replaced by ∗. We may omit n if n= 1. We recall the following general result from number theory known as B´ezout’s identity. Given a set of integers A={a1,· · · , an} ⊆ Z, there exist integers x1,· · · , xn∈Zsuch that the following holds: n X i=1 xiai= gcd(a1,· · · , an), where gcd(a1, . . . , an) in the greatest common divisor of the integers from A. Furthermore, the greatest common divisor is the smallest positive integer which can be obtained as a linear combination of the elements of A. 30 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron 2.2 Vector Addition Systems Avector addition system (VAS) of dimension n∈Nis defined to be the pair (w0, W), where w0∈Nnis the start vector, and Wis a finite set of vectors from Zn, called addition vectors. An addition vector w∈Wis said to be enabled in a vector x∈Nnif x+w∈Nn, i.e. all the components of the vector x+ware non-negative. A VAS evolves from the start vector w0by sequentially iterating the addition of vectors from W. Avector addition system with states (VASS) is a VAS equipped with a finite state control. Essentially, state labels are assigned to addition vectors and a graph of states is given which defines the possible sequences of application of addition vectors. We will use the notation VAS and VASS to refer to the families of sets of natural vectors which can be generated by VAS and VASS, respectively. It was shown in [8] that VASS are equivalent in expressive power to VAS (without states): any n-dimensional VASS can be simulated by an equivalent (n+ 3)-dimensional VAS. A variation on the model of vector addition systems consists in lifting the restriction that the valid vectors must have non-negative components. This model has recently been defined in [7]. An integer vector addition system (Z-VAS) of dimension n∈Nis the pair (w0, W), where w0∈Znis the start vector, and W⊆Znis finite set of addition vectors. A Z-VAS evolves from w0by sequentially applying the addition vectors from W. The set of vectors generated by a Z-VAS is defined to be the set of reachable vectors. An integer vector addition systems with states (Z-VASS) is a Z-VAS equipped with a state control and is defined as a tuple (w0, Q, q0, qh, p, δ), where w0∈Zn is the start vector, Qis a finite set of state labels, q0∈Qis the starting state, qh∈Qis the halting state, p:Q\ {qh} → Znis a function assigning a vector to every state from Q\ {qh}, and δ:Q→2Qis a state transition function assigning to each state the set of possible successor states. AZ-VASS starts in w0and in state q0, applies the addition vector p(q0), and non-deterministically moves into one of the states from δ(q0). This process is iteratively repeated, until the halting state qhis reached. The vector language generated by a Z-VASS is defined as the set of all vectors which are reachable in the halting state qh. We will use the notations Z-VAS and Z-VASS to refer to the sets of integer vectors generated by Z-VAS or Z-VASS. 3 Register Machines Definition 1. Aregister machine over the set Ais the tuple MA= (n, A, Q, q0, qh, P), where n∈N,Ais a (possibly infinite) register alphabet, Q is a finite set of state labels, q0is the initial state, qh∈Qis the halting state, and Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems 31 Pis a mapping associating an instruction to every state of MA. An instruction is a function p:An→An×2Qassociating to every n-tuple of values from Aanother n-tuple of such values and a set of states from Q. A configuration C∈Q×Anof MAis a tuple combining a state and nvalues from A. MAcan be seen as storing values of type Ain its nregisters. A configuration of MAtherefore defines its current state and the values of its nregisters. When in state q∈Q,MAcan execute the instruction P(q), which will compute (1) new values for all registers of MAand (2) a set of possible new states; MAcan nondeterministically transition into one of these states. Definition 2. Ak-step (finite) computation of the register machine MA= (n, A, Q, q0, qh, P) is a finite sequence of configurations (Ci)0≤i≤ksuch that, 1. C0= (q0,a0), where some of the components of a0(registers) may contain input values; 2. Ck= (qh,ak), where some of the components of an(registers) may contain output values; 3. for every 0≤i<k,Ci= (qi,ai),Cj= (qj,aj),P(qi)(ai)=(aj, H), and qj∈H. MAtherefore transitions from a configuration to another by sequentially applying its instructions. Whenever MAis in state qi, it retrieves the corresponding instruction P(qi) and applies it to the tuple describing the values of the registers. The result, P(qi)(ai), gives the new values for the registers and a set of states H from which MApicks qjand moves into it. The last configuration Chis habitually referred to as the halting configuration. Often, in order to be able to express the instructions in a sensible way, one considers some kind of structure over the set A; one example of such a structure may be a finitely generated Abelian group. Classical definitions of register machines rely on (sub)sets of integers and on the associated structure of a linearly ordered finitely generated Abelian group. In what follows, we describe the existing models of register machines using the abstract language we have just introduced, and we show that blind register machines actually represent the least restricted variant. Definition 3. Ablind register machine is a register machine Bover the finitely generated Abelian group (Z,+). The instructions of blind register machines can be of the following two types: 1. (ADD(i), q, s)(a1, . . . , ai, . . . , an) = (a1, . . . , ai+ 1, . . . , an),{q, s}, and 2. (SUB∗(i), q)(a1, . . . , ai, . . . , an) = (a1, . . . , ai−1, . . . , an),{q}. The computations of blind register machines are defined as a computation of the corresponding register machine over (Z,+). 32 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron Definition 4. A blind register machine accepts an input vector by resetting all registers to zero in the halting configuration. A blind register machine generates (or computes from an input) a vector of numbers by resetting all registers not containing the output to zero. We will use the notation PsZBRM (resp., P sNBRM) to refer to the class of sets of vectors of integer (resp., natural) numbers accepted by blind register machines. All other well known types of register machines can be defined as subtypes of blind register machines. Definition 5. Apartially blind register machine is a blind register machine whose registers are only allowed to contain non-negative numbers: for any computation (Ci)1≤i≤kof a partially-blind register machine and for any Ci= (qi,ai),1≤i≤k, every component of aiis non-negative. Thus, if the partially blind register machine B0decides at some point to decrement a register whose value is already zero, it will produce an illegal configuration which will render the whole computation invalid. This means that B0still cannot check its registers for zero, but it knows that all of them are non-negative at any given time. The computations of partially blind machines therefore satisfy a condition which renders them strictly stronger than blind register machines [6]: the registers may never go below zero. Definition 6. A partially blind register machine accepts an input vector by resetting all registers to zero in the halting configuration. A partially blind register machine generates (or computes from an input) a vector of numbers by resetting all registers not containing the output to zero in the halting configuration. We will use the notation PsPBRM to refer to the class of sets of vectors of natural numbers accepted by partially blind register machines. We can now also define conventional register machines in our general framework. Definition 7. A (conventional) register machine is a register machine over (Z,+) with the following two types of instructions: 1. (ADD(i), q, s)(a1, . . . , ai, . . . , an) = (a1, . . . , ai+ 1, . . . , an),{q, s}, and 2. (SUB(i), q, z)(a1, . . . , ai, . . . , an) = ((a1, . . . , ai−1, . . . , an),{q},if ai>0, (a1, . . . , ai, . . . , an),{z},if ai= 0. Computations of conventional register machines are defined as computations of the corresponding register machines over (Z,+) with the restriction that, in the initial configuration, all registers must contain non-negative values. It follows from the form of instructions allowed in conventional register machines that their registers contain non-negative values at any time. Therefore, one Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems 33 can see such register machines as an even more powerful form of partially blind register machines (and thus a particular case of blind register machines), in which the machine is allowed to check whether any given register is zero. We would like to remark that by considering other types of instructions or restrictions on the class of valid computations, one can characterise many other variants of register machines. For example, reversal-bounded counter automata are register machines in which one can only switch from incrementing to decrementing a register (and conversely) a bounded number of times [9]. 4 Integer Vector Addition P Systems In the article [10], Gheorghe P˘aun suggested exploring multisets with negative multiplicities. Several possible answers were suggested. In [3], the authors define generalised multisets as having multiplicities from totally ordered Abelian groups. The work [1] takes a different approach and partitions the alphabet of objects into two categories: the regular objects, which may have any integer multiplicity, and the so-called “catalysts”, which are only allowed to appear in a bounded number of copies. Like in purely catalytic P systems, the “catalysts” in this model are used to guide the applicability of rules. In this work, we generalise this model to the concept of integer vector addition P systems. Before defining this model, we define the following natural extension of multisets. Definition 8. AZ-multiset over the (finite) alphabet Ois a mapping w:O→Z. The value w(a)is called the multiplicity of ain w. An object a∈Ois said to apear in wif w(a)6= 0. A multiset wis said to be empty if no objects appear in it. Thus, Z-multisets can also be seen as vectors of integers, indexed by elements of O. We will use the notation ZOto refer to the set of all Z-multisets over O. Definition 9. An integer vector addition P system (Z-VAPS) is the construct Π= (O, T, µ, w1, . . . , wn, R, hi, ho), where Ois a finite alphabet of objects, T⊆Ois the set of terminal objects, µis the membrane structure injectively labelled by the numbers from {1, . . . , n}and usually given by a sequence of correctly nested brackets, wiare the Z-multisets giving the initial contents of every membrane i,1≤i≤n,Ris a finite set of rules of the form r:{1, . . . , n} → ZO, and hiand hoare the labels of the input and the output membranes, respectively (1≤hi≤n,1≤ho≤n). Thus, integer vector addition P systems manipulate vectors of integers, indexed by the objects from O(Z-multisets). A rule r∈Rassigns such a vector to every membrane of Π; applying rmeans adding (by componentwise addition) the vector r(i) to the vector representing the contents of the membrane i, for every 1 ≤ 34 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron i≤n. Therefore, one may see ras only having a right-hand side and as being unconditionally applicable. Such a form comes in naturally, since, as also pointed out in [3, 1], considering multiplicities over Zrenders the usual rule applicability conditions irrelevant. We also remark that this way of defining the rules generalises naturally to a tissue-like membrane structure, i.e. a membrane structure which is not required to be a tree, but can be an arbitrary graph (cf. [5]). We will use the tuple notation to describe rules of vector addition P systems — a rule rwill be given by the set (i, r(i)) |1≤i≤n, r(i) is not empty. In [1], the authors use a special symbol δto command the dissolution of the membrane in which it is produced. To allow for the same possibility in vector addition P systems, we will define the rules as functions of the form {1, . . . , n} → ZO∪{δ}, i.e. as functions assigning Z-multisets over O∪ {δ}to each membrane. If r(i)(δ) = 1 for the elementary membrane i, the application of rwill dissolve this membrane after adding the multiplicities of symbols different from δto its contents. We may even allow r(i)(δ) = k > 1, in which case ksuccessive membranes in the hierarchy will be dissolved, but only the contents of the innermost dissolved membrane will be copied into the corresponding parent membrane (the contents of the intermediary membranes will be lost). Allowing dissolution makes it possible to introduce a rule applicability condition: ris applicable if every membrane i, for which r(i) is not empty, is still present in the system. The integer vector addition P system Πevolves by sequentially applying rules from Runtil a halting configuration is reached. Remark that, because of the use of Z-multisets, the only way to use the classical halting condition is to dissolve all the membranes to which the rules of Πmay contribute. This corresponds to the approach proposed in [1] which consists in dissolving all the working membranes until the result reaches a membrane without any rules. Thus, the classical halting condition becomes somewhat degenerate; it is therefore only natural to discuss other halting conditions, for example: •unconditional halting — the system may halt at any moment, independently of rule applicability or contents of the membranes; •halting by zero — the system halts when it reaches a configuration in which all multisets representing the contents of all membranes are empty. One may see unconditional halting as corresponding to the way in which the language generated by a grammar is defined [4]: essentially, the contents of the output membrane of Πin any configuration Πcan reach, projected on the terminal alphabet T, is part of the vector language generated by Π. On the other hand, halting by zero corresponds to the way in which blind register machines recognise input vectors. We will use the symbols uncond,zero, and inappl to refer to unconditional halting, halting by zero, and halting by inapplicability of rules. Similarly, we will use the symbols acc and gen to refer to the accepting and generating modes. We will use the notation PsZVAPS(m, h), m∈ {acc, gen},h∈ {uncond, zero, inappl}, Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems 35 to refer to the class of sets of vectors of integers accepted or generated by integer vector addition P systems working with the corresponding halting conditions. We will add the symbol δto refer to the vector languages associated with Z-VAPS with dissolution rules (PsZVAPS(m, h, δ)) and the symbol δ∗to refer to the languages of Z-VAPS which are allowed to dissolve multiple membranes at a time (PsZVAPS(m, h, δ∗)). Finally, we will replace Zby Nto refer to the languages of vectors of naturals (non-negative integers). We immediately observe that PsZVAPS(m, inappl) = {∅}, because if a Z- VAPS has any rules at all, it can never halt by rule inapplicability. 5 On the Power of Blind Register Machines In this section, we will focus on relating integer vector addition systems to blind register machines, as well as on expressing the power of both models in terms of semilinear vectors of numbers. We will show that blind register machines and Z-VASS generate exactly N-linear sets of Z-vectors. The work [2] also discusses the computational power of blind and partially blind register machines, but it uses a different definition of blindness: a blind register machine is defined as a partially blind register machine which may halt with any values in the registers. In the present paper we use a definition which is closer to Sheila Greibach’s blind and partially register machines [6]. We will start by giving a proof of the quite intuitive result that blind register machines recognise exactly the same sets of integer vectors as integer vector addition systems with states generate. Theorem 1. P sZBRM =Z-VASS. Proof. Take a blind register machine B= (n, Z, Q, q0, qh, P); we will construct aZ-VASS Γ= (w0, S, s0, sh, p, δ) with w0= (0,...,0) ∈Zn,S=Q,s0=qh, sh=q0. The set δ(p) will contains all the states of Bfrom which pcan be reached: δ(s) = {q∈Q|P(q) = (SUB(i), s) or P(q) = (ADD(i), s, s0) or P(q)=(ADD(i), s0, s)}. The vector p(s) associated with a state s∈Sdoes the opposite effect of the instruction associated with the same state in B: p(s) = (1i,if P(s) = (SUB(i), q), −1i,if P(S)=(ADD(i), q, q0), where 1i∈Znis a vector whose only non-zero component is the i-th component. It follows from the construction of Γthat, for every computation of Baccepting an input vector x, there exists a computation of Γhalting on the same vector, and conversely, which proves that PsZBRM ⊆Z-VASS. 42 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron References 1. O. Belingheri, A. E. Porreca, and C. Zandron. P systems with hybrid sets, 2016. Workshop on Membrane Computing, submitted. 2. R. Freund, O. Ibarra, Gh. P˘aun, and H.-C. Yen. Matrix languages, register machines, vector addition systems. Third Brainstorming Week on Membrane Computing, pages 155–167, 2005. 3. R. Freund, S. Ivanov, and S. Verlan. P systems with generalized multisets over totally ordered abelian groups. In Int. Conf. on Membrane Computing, volume 9504 of Lecture Notes in Computer Science, pages 117–136. Springer, 2015. 4. R. Freund, M. Kogler, and M. Oswald. A general framework for regulated rewriting based on the applicability of rules. In J. Kelemen and A. Kelemenov´a, editors, Computation, Cooperation, and Life, volume 6610 of Lecture Notes in Computer Science, pages 35–53. Springer Berlin Heidelberg, 2011. 5. R. Freund and S. Verlan. A formal framework for static (tissue) P systems. In G. Eleftherakis, P. Kefalas, Gh. P˘aun, G. Rozenberg, and A. Salomaa, editors, Membrane Computing, volume 4860 of Lecture Notes in Computer Science, pages 271–284. Springer Berlin Heidelberg, 2007. 6. S. A. Greibach. Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7(3):311–324, 1978. 7. C. Haase and S. Halfon. Integer vector addition systems with states. In J. Ouaknine, I. Potapov, and J. Worrell, editors, Reachability Problems: 8th International Workshop, RP 2014, Oxford, UK, September 22-24, 2014. Proceedings, pages 112–124. Springer, 2014. 8. J. Hopcroft and J.-J. Pansiot. On the reachability problem for 5-dimensional vector addition systems. Theoretical Computer Science, 8(2):135–159, 1979. 9. O. H. Ibarra. Automata with reversal-bounded counters: A survey. In H. J¨urgensen, J. Karhum¨aki, and A. Okhotin, editors, Descriptional Complexity of Formal Systems: 16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014. Proceedings, pages 5–22. Springer, 2014. 10. Gh. P˘aun. Some quick research topics. http://www.gcn.us.es/files/OpenProblems bwmc15.pdf. 11. Gh. P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61:108–143, 1998. 12. Gh. P˘aun, G. Rozenberg, and A. Salomaa. The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA, 2010.