Input-Driven Tissue P Automata

Input-Driven Tissue P Automata Artiom Alhazov1, Rudolf Freund2, Sergiu Ivanov3, Marion Oswald2, and Sergey Verlan4 1Institute of Mathematics and Computer Science Academiei 5, Chişinău, MD-2028, Moldova [email protected] 2Faculty of Informatics, TU Wien Favoritenstraße 9–11, 1040 Vienna, Austria {rudi,marion}@emcc.at 3IBISC, Université Évry, Université Paris-Saclay 23 Boulevard de France, 91025, Évry, France [email protected] 4Laboratoire d’Algorithmique, Complexité et Logique, Université Paris Est Créteil, 61 Avenue du Général de Gaulle, 94010 Créteil, France [email protected] Summary. We introduce several variants of input-driven tissue P automata where the rules to be applied only depend on the input symbol. Both strings and multisets are considered as input objects; the strings are either read from an input tape or defined by the sequence of symbols taken in, and the multisets are given in an input cell at the beginning of a computation, enclosed in a vesicle. Additional symbols generated during a computation are stored in this vesicle, too. An input is accepted when the vesicle reaches a final cell and it is empty. The computational power of some variants of input-driven tissue P automata is illustrated by examples and compared with the power of the input-driven variants of other automata as register machines and counter automata. 1 Introduction In the basic model of membrane systems as introduced at the end of the last century by Gheorghe Păun, e.g., see [9] and [30], the membranes are organized in a hierarchical membrane structure (i.e., the connection structure between the compartments/regions within the membranes being representable as a tree), and the multisets of objects in the membrane regions evolve in a maximally parallel way, with the resulting objects also being able to pass through the surrounding membrane to the parent membrane region or to enter an inner membrane. Many variants of membrane systems, for obvious reasons mostly called P systems, have 40 A. Alhazov et al. been investigated during nearly two decades, most of them being computationally complete, i.e., being able to simulate the computations of register machines. If an arbitrary graph is used as the connection structure between the cells/membranes, the systems are called tissue P systems, see [21]. Instead of multisets of plain symbols coming from a finite alphabet, P systems quite often operate on more complex objects (e.g., strings, arrays), too. A comprehensive overview of different variants of (tissue) P systems and their expressive power is given in the handbook which appeared in 2010, see [31]. For a short view on the state of the art on the domain, we refer the reader to the P systems website [34] as well as to the Bulletin series of the International Membrane Computing Society [33]. The notion and concept of input-driven push-down automata goes back to the seminal paper [22] as well as the papers [6] and [10] improving the complexity measures shown in [22]. The main idea of input-driven push-down automata is that the input letters uniquely determine whether the automaton pushes a symbol, pops a symbol, or leaves the pushdown unchanged. Input-driven push-down automata have been rediscovered at the beginning of this century under the name of visibly pushdown automata, see [3] and [4]. Since then, variants of input-driven pushdown automata have gained growing interest, especially because closure properties and decidable questions of the language classes defined by these devices turn out to be similar to those of regular languages. Several new variants of input-driven automata have been developed, for example, using stacks or queues, see [5], [19], and [20]. For complexity issues of input-driven push-down automata, the reader is referred to [24, 25, 26, 27]. The so-called point mutations, i.e., insertion,deletion, and substitution, which mean inserting or deleting one symbol or replacing one symbol by another one in a string or multiset are very simple biologically motivated operations. For example, on strings graph-controlled insertion-deletion systems have been investigated in [13], and P systems using these operations at the left or right end of string objects were introduced in [16], where also a short history of using these point mutations in formal language theory can be found. The operations of insertion and deletion in multisets show a close relation with the increment and decrement instructions in register machines. The power of changing states in connection with the increment and decrement instructions then can be mimicked by moving the whole multiset representing the configuration of a register machine from one cell to another one in the corresponding tissue system after the application of an insertion or deletion rule. Yet usually moving the whole multiset of objects in a cell to another one, besides maximal parallelism, requires target agreement between all applied rules, i.e., that all results are moved to the same target cell, e.g., see [15]. A different approach has been introduced in [2]: in order to guarantee that the whole multiset is moved even if only one point mutation is applied, the multiset Input-Driven Tissue P Automata 41 is enclosed in a vesicle, and this vesicle is moved from one cell to another one as a whole, no matter if a rule has been applied or not. Requiring that one rule has to be applied in every derivation step, a characterization of the family of sets of (vectors of) natural numbers defined by partially blind register machines, which itself corresponds with the family of sets of (vectors of) natural numbers obtained as number (Parikh) sets of string languages generated by graph-controlled or matrix grammars without appearance checking, is obtained. The idea of using vesicles of multisets has already been used in variants of P systems using the operations drip and mate, corresponding with the operations cut and paste well-known from the area of DNA computing, see [14]. Yet in that case, always two vesicles (one of them possibly an axiom available in an unbounded number) have to interact. In the model as introduced in [2] and also to be adapted in this paper, the rules are always applied to the same vesicle. The point mutations, i.e., insertion,deletion, and substitution, well-known from biology as operations on DNA, have also widely been used in the variants of networks of evolutionary processors (NEPs), which consist of cells (processors) each of them allowing for specific operations on strings, and in each derivation step, after the application of a rule, allow the resulting string to be sent to another cell provided specific conditions (for example, random context output and input filters). A short overview on NEPs is given in [2], too. In this paper, we now introduce input-driven tissue P automata where the rules to be applied only depend on the input symbol. Taking strings as input objects, these are either read from an input tape or defined by the sequence of symbols taken in, and as a kind of additional storage we use a multiset of different symbols enclosed in a vesicle which moves from one cell of the tissue P system to another one depending on the input symbol; the input symbol at the same time also determines whether (one or more) symbols are added to the multiset in the vesicle or removed from there. The given input is accepted if the whole input has been read and the vesicle has reached a final cell and is empty at this moment. When using multisets as input objects, these are enclosed in the vesicle in the input cell at the beginning of a computation, which vesicle then will also carry the additional symbols. The given input multiset is accepted if no input symbols are present any more and the vesicle has reached a final cell and is empty at this moment. As rules operating on the multiset enclosed in the vesicle when reading/consuming an input symbol we use insertion, deletion, and substitution of multisets, applied in the sequential derivation mode. As restricted variants, we consider systems without allowing substitution of multisets and systems only allowing symbols to be inserted or deleted (or substituted) as it is common when using point mutation rules. Multiset automata have already been considered in [7], where models for finite automata, linear bounded automata, and Turing machines working on multisets are discussed. When dealing with multisets only, the tissue P automata considered 42 A. Alhazov et al. in this paper can be seen as one of the variants of multiset pushdown automata as investigated in [18], where no checking for the emptiness of the multiset memory during the computation is possible. Various lemmas proved there then can immediately be adapted for our model. Moreover, also the input-driven variants can be defined in a similar manner, although input-driven multiset pushdown automata have not yet been considered in that paper. We should also like to mention that the control given by the underlying communication structure of the tissue P system could also be interpreted as having a P system with only one membrane but using states instead. For a discussion on how to use and interpret features of (tissue) P systems as states we refer to [1], where also an example only using the point mutation rules insertion and deletion is given. Moreover, we will also consider another alternative model very common in the P systems area, i.e., P systems with antiport and symport rules, which were introduced in [29]; for an overview, we refer to [31], Chapter 5. One-membrane P systems using antiport rules in a sequential manner and with specific restrictions on the rules then are an adequate model for (input-driven) P automata, yet the restrictions are less visible than in the model of input-driven tissue P automata. On the other hand, when dealing with strings instead of multisets, the way how to read or define the input string in P systems with antiport rules has already been investigated thoroughly, e.g., see [8], [28], and [11] for an overview. The rest of the paper now is structured as follows: In Section 2 we recall some well-known definitions from formal language theory. The main definitions for the model of (input-driven) tissue P automata as well as its variants to be considered in this paper are given in Section 3, and there we also present the definition of the alternative model of (input-driven) one-membrane P automata with (restricted) antiport rules; moreover we also give some first examples and results. Further illustrative examples and some more results, especially for input-driven tissue P automata are exhibited in Section 4. As upper bound for the family of sets of vectors of natural numbers accepted by input-driven tissue P automata we get the family of sets of vectors of natural numbers generated by partially blind register machines, and as upper bound for the family of sets of strings accepted by inputdriven tissue P automata we get the family of sets of strings accepted by partially blind counter automata. A summary of the results obtained in this paper and an outlook to future research are presented in Section 5. 2 Prerequisites We start by recalling some basic notions of formal language theory. An alphabet is a non-empty finite set. A finite sequence of symbols from an alphabet Vis called astring over V. The set of all strings over Vis denoted by V∗; the empty string is denoted by λ; moreover, we define V+=V∗\ {λ}. The length of a string xis denoted by |x|, and by |x|awe denote the number of occurrences of a letter ain a string x. Input-Driven Tissue P Automata 43 Amultiset Mwith underlying set Ais a pair (A, f)where f:A→Nis a mapping, with Ndenoting the set of natural numbers (non-negative integers). If M= (A, f)is a multiset then its support is defined as supp(M) = {x∈A|f(x)>0}. A multiset is empty (respectively finite) if its support is the empty set (respectively a finite set). If M= (A, f)is a finite multiset over Aand supp(M) = {a1, . . . , ak}, then it can also be represented by the string af(a1) 1. . . af(ak) kover the alphabet {a1, . . . , ak}(the corresponding vector (f(a1), . . . , f(ak)) of natural numbers is called Parikh vector of the string af(a1) 1. . . af(ak) k), and, moreover, all permutations of this string precisely identify the same multiset M(they have the same Parikh vector). The set of all multisets over the alphabet Vis denoted by V◦. The family of all recursively enumerable sets of strings is denoted by RE, the corresponding family of recursively enumerable sets of Parikh vectors is denoted by P sRE. For more details of formal language theory the reader is referred to the monographs and handbooks in this area, such as [32]. 2.1 Insertion, Deletion, and Substitution For an alphabet V, let a→bbe a rewriting rule with a, b ∈V∪ {λ}, and ab 6=λ; we call such a rule a substitution rule if both aand bare different from λand we also write S(a, b); such a rule is called a deletion rule if a6=λand b=λ, and it is also written as D(a);a→bis called an insertion rule if a=λand b6=λ, and we also write I(b). The sets of all insertion rules, deletion rules, and substitution rules over an alphabet Vare denoted by InsV,DelV, and SubV, respectively. Whereas an insertion rule is always applicable, the applicability of a deletion and a substitution rule depends on the presence of the symbol a. We remark that insertion rules, deletion rules, and substitution rules can be applied to strings as well as to multisets. Whereas in the string case, the position of the inserted, deleted, and substituted symbol matters, in the case of a multiset this only means incrementing the number of symbols b, decrementing the number of symbols a, or decrementing the number of symbols aand at the same time incrementing the number of symbols b. These types of rules and the corresponding notations can be extended by allowing more than one symbol on the left-hand and/or the right-hand side, i.e., a, b ∈V∗, and ab 6=λ. The corresponding sets of all extended insertion rules, deletion rules, and substitution rules over an alphabet Vare denoted by Ins∗ V, Del∗ V, and Sub∗ V, respectively. 2.2 Register Machines Register machines are well-known universal devices for computing (generating or accepting) sets of vectors of natural numbers. Definition 1. Aregister machine is a construct M= (m, B, I, h, P)where •mis the number of registers, 44 A. Alhazov et al. •Bis a set of labels bijectively labeling the instructions in the set P, •I⊆Bis the set of initial labels, and •h∈Bis the final label. The labeled instructions of Min Pcan be of the following forms: •p: (ADD (r), K), with p∈B\ {lh},K⊆B,1≤r≤m. Increase the value of register rby one, and non-deterministically jump to one of the instructions in K. •p: (SUB (r), K, F), with p∈B\ {lh},K, F ⊆B,1≤r≤m. If the value of register ris not zero then decrease the value of register rby one (decrement case) and jump to one of the instructions in K, otherwise jump to one of the instructions in F(zero-test case). •h:HALT. Stop the execution of the register machine. Aconfiguration of a register machine is described by the contents of each register and by the value of the current label, which indicates the next instruction to be executed. In the accepting case, a computation starts with the input of a k-vector of natural numbers in its first kregisters and by executing one of the initial instructions of P(labeled with l∈I); it terminates with reaching the HALT-instruction. Without loss of generality, we may assume all registers to be empty at the end of the computation. By L(RM)we denote the family of sets of vectors of natural numbers accepted by register machines. It is folklore (e.g., see [23]) that PsRE =L(RM). Partially blind register machines In the case when a register machine cannot check whether a register is empty we say that it is partially blind: the registers are increased and decreased by one as usual, but if the machine tries to subtract from an empty register, then the computation aborts without producing any result (that is we may say that the subtract instructions are of the form p: (SUB (r), K, abort); instead, we simply will write p: (SUB (r), K). Moreover, acceptance now by definition also requires all registers to be empty at the end of the computation, i.e., there is an implicit test for zero at the end of a (successful) computation, that is why we say that the device is partially blind. By L(PBRM)we denote the family of sets of vectors of natural numbers accepted by partially blind register machines. It is known (e.g., see [12]) that partially blind register machines are strictly less powerful than general register machines (hence, than Turing machines); moreover, L(PBRM)characterizes the Parikh sets of languages generated by graph-controlled or matrix grammars without appearance checking. Input-Driven Tissue P Automata 45 2.3 Counter Automata Register machines can also be equipped with an input tape to be able to process strings, and the registers then are only used as auxiliary storage. We then call the registers counters and the automaton a counter automaton (we mention that in the literature slightly different definitions with respect to the instructions may be found). The additional instruction needed then is a read instruction reading one symbol from the input tape: p: (read(a), K), with p∈B\ {h},K⊆B, and a∈T. Tis the input alphabet, i.e., in sum we obtain a counter automaton as a construct M= (m, B, I, h, P, T). A counter automaton accepts an input w∈T∗if and only if it starts in some initial state and with won its input tape, and finally Mreaches hhaving read the whole input string w. Without loss of generality, we again may assume all registers to be empty at the end of the computation. It is folklore (e.g., see [23]) that the family of string languages accepted by counter automata equals RE (in fact, only two counters are needed). Partially blind counter automata As in the case of register machines, a counter automaton is called partially blind if it cannot check whether a register is empty, and acceptance by definition requires the whole input to be read and all counters to be empty at the end of the computation. For basic results on partially blind counter automata we refer to the seminal paper [17]. The family of string languages accepted by partially blind counter automata is denoted by L(PBCA). 2.4 Input-Driven Register Machines and Counter Automata An input-driven register machine / counter automaton (an IDRM∗and IDCA∗, respectively, for short) can be defined in the following way: any decrement of an input register r/ any reading of a terminal symbol ais followed by fixed sequences of instructions on the working registers / counters only depending on the input register r/ the terminal symbol a. If each such sequence is of length exactly one, then we speak of a real-time input-driven register machine / counter automaton (an IDRM and IDCA, respectively, for short). In the case of an IDCA, these sequences are of the form p: (read(a), K)→q: (α(r), Kq), q ∈K, with α∈ {ADD, SUB},1≤r≤m, and they could be written as one extended instruction p: (read(a), α(r),Sq∈KKq). 46 A. Alhazov et al. In a similar way, for an IDCA∗we replace α(r)by the whole sequence of instructions following the reading of the input symbol a. A similar notation can be adapted for the case of a SUB-instruction on an input register instead of read(a). Moreover, analogous definitions and notations hold for the partially blind variants of input-driven register machines / counter automata. Remark 1. We emphasize that we have chosen a very restricted variant of what it means that the actions on the working registers only depend on the input symbol just read: no matter which label the read instruction read(a)has, it must always be followed by the same sequence α(r); only the branching to labels from Sq∈KKq) allows for taking different actions afterwards. ut Remark 2. Allowing a set of initial labels as well as sets of labels in the ADDand SUB-instructions may look quite unusual, but especially for the input-driven automata this feature turns out to be essential: Assume we had allowed only one initial label iin any input-driven counter automaton. Now consider the finite multiset language {a, b}: assume there is an input-driven partially blind counter automaton accepting {a, b}. By definition, the instruction assigned to the initial label imust be a read instruction. With the initial label i, only one of the read instructions read(a)or read(b)can be assigned, hence, only aor only bcan be accepted, a contradiction. A similar argument holds for partially blind register machines taking the input set of two-dimensional vectors {(1,0),(0,1)}: the instruction assigned to imust be a SUB-instruction either on register 1or on register 2, again leading to a contradiction. On the other hand, with our more general definition, we get closure under union for free for L(X),X∈ {IDRM, IDCA, IDRM∗, IDCA∗}.ut 3 Tissue P Automata as Multiset Pushdown Automata We now define a model of a tissue P automaton and its input-driven variants, first for the case of working with multisets as input objects: Definition 2. Atissue P automaton (a tPA∗for short) is a tuple Π= (L, V, Σ, Γ, R, g, I, F) where •Lis a set of labels identifying in a one-to-one manner the |L|cells of the tissue P system Π; •Vis the alphabet of the system; •Σ⊆Vis the (non-empty) input alphabet of the system; •Γ⊆Vis the (possibly empty) memory alphabet of the system, Γ∩Σ=∅; Input-Driven Tissue P Automata 47 •Ris a set of rules of the form (i, p)where i∈Land p∈Ins∗ V∪Del∗ V∪Sub∗ V, i.e., pis an extended insertion, deletion or substitution rule over the alphabet V; we may collect all rules from cell iin one set and then write Ri={(i, p)| (i, p)∈R}, so that R=Si∈LRi; moreover, for the sake of conciseness, we may simply write Ri={p|(i, p)∈R}, too; •gis a directed graph describing the underlying communication structure of Π, g= (N, E)with N=Lbeing the set of nodes of the graph gand the set of edges E⊆L×L; •I⊆Lis the set of labels of initial cells one of them containing the input multiset wat the beginning of a computation; •f⊆Lis the set of labels of final cells for acceptance. If in the definition above we take p∈InsV∪DelV∪SubVinstead of p∈ Ins∗ V∪Del∗ V∪Sub∗ V, then we speak of a tPA instead of a tPA∗. AtPA∗Πnow works as follows: The computation of Πstarts with a vesicle containing the input multiset win one of the initial cells i∈I, and the computation proceeds with derivation steps until a specific output condition is fulfilled. In each derivation step, with the vesicle enclosing the multiset wbeing in cell k, one rule from Rkis applied to wand the resulting multiset in its vesicle is moved to a cell msuch that (k, m)∈E. As we are dealing with membrane systems, the classic output condition is to only consider halting computations; yet in case of automata, the standard acceptance condition is reaching a final state, which in our case means reaching a final cell h, and, moreover, the vesicle to be empty. We will take these two conditions as our mode of acceptance in this paper, as with the vesicle being empty no decrement rule can be applied any more and, moreover, it is guaranteed that we have “read the whole input”. Only requiring the vesicle to be empty or else requiring to have reached a final cell with the vesicle containing no input symbol any more, are two other variants of acceptance. The set of multisets accepted by Πis denoted by Psacc(Π). The families of sets of vectors of natural numbers accepted by tP A∗and tP A with at most n cells are denoted by Ln(tPA∗)and Ln(tPA), respectively. If nis not bounded, we simply omit the subscript in these notations. In order to specify which rules are allowed in the tPA∗and tPA, we may explicitly specify I∗, D∗, S∗and I, D, S, respectively, to indicate the use of (extended) insertion, deletion, and substitution rules. For example, L(tPA, ID)then indicates that only insertion and deletion rules are used. Remark 3. The model of a tPA∗comes very close to the model of a multiset pushdown automaton as introduced in [18]; in fact, the family of sets of vectors of natural numbers accepted by these multiset pushdown automata equals L(tPA∗). A formal proof would go far beyond the scope of this paper, but the basic similarity of these two models becomes obvious when identifying the cells in the tPA∗ with the states in the multiset pushdown automaton; moving the vesicle from one 54 A. Alhazov et al. ΠD= (L={1,2,3,4,5}, V, Σ, Γ, R, g = (L, E), I ={1}, F ={5}), V={a1,[,]}, Σ={[,]}, Γ={a1}, R={(1, read ( [ )),(2, I (a1)),(3, read ( ] )),(4, D (a1))}, E={(1,2),(2,1),(2,3),(3,4),(4,1),(4,3),(4,5)}. The two constructions elaborated above implement the following definition of a well-formed bracket expression wover the alphabet of brackets {[,]}: •for every prefix of w, the number of closing brackets ]must not exceed the number of opening brackets [; •the number of closing brackets ]in wequals the number of opening brackets [. Hence, during the whole computation, the (non-negative) difference between the number of opening and the number of closing brackets is stored as the number of symbols a1; at the end, this number must be zero, which is guaranteed by the acceptance conditions. ut L(IDPBCArt)even contains a non-context-free language: Example 2. The language Lil ={anbmcndm|m, n ≥1}is not context-free, but accepted by the following tIDPALrt Πil: Πil = (L={1,...,9}, V, Σ, Γ, R, g = (L, E), I ={1}, F ={9}), V={a1, a2, a, b, c, d}, Σ={a, b, c, d}, Γ={a1, a2}, R={(1, read (a)),(2, I (a1)),(3, read (b)),(4, I (a2)), (5, read (c)),(6, D (a1)),(7, read (d)),(8, D (a2))}, E={(1,2),(2,1),(2,3),(3,4),(4,3), (4,5),(5,6),(6,5),(6,7),(7,8),(8,7),(8,9)}. By this construction, we conclude Lil ∈ L(tIDPALrt, ID).ut For the language considered in the next example we show that it is in L(tIDPAL∗rt), but we claim that it is not in L(tIDP ALrt): Example 3. Let k > 2and consider the string language Lk={b1n. . . bkn|n≥1}, which is not context-free, but accepted by the following tIDPAL∗rt Π: Input-Driven Tissue P Automata 55 1 start read(a) 2 I(a1) 3 read(b) 4 I(a2) 5 read(c) 6 D(a1) 7 read(d) 8 D(a2) 9 Fig. 1. Graphic representation of the tIDP ALrt Πil. Πk= (L={1,...,2k+ 1}, V, Σ, Γ, R, g = (L, E), I ={1}, F ={2k+ 1}), V={ai, bi|1≤i≤k}, Σ={bi|1≤i≤k}, Γ={ai|1≤i≤k}, R={(1, read (b1)),(2, I (a2. . . ak))} ∪ {(2j−1, read (bj)),(2j, D (aj)) |1< j ≤k}, E={(2j−1,2j),(2j, 2j−1),(2j, 2j+ 1) |1≤j≤k}. Without proof we claim that Lk/∈ L(tIDPALrt).ut 5 Conclusion and Future Research In this paper, we have introduced tissue P automata as a specific model of multiset automata as well as input-driven tissue P automata where the rules to be applied depend on the input symbol. Taking strings as input objects, these are either read from an input tape or defined by the sequence of symbols taken in, and as an additional storage of a multiset of different symbols we use a vesicle which moves from one cell of the tissue P system to another one depending on the input symbol; the input symbol at the same time determines whether (one or more) symbols are added to the multiset in the vesicle or removed from there and where the vesicle moves afterwards. The given input is accepted if the whole input has been read and the vesicle has reached a final cell and/or is empty at this moment. When using multisets as input objects, these are enclosed in the vesicle in the input cell at the beginning of a computation, which vesicle then will also take the additional symbols. The given input multiset is accepted if no input symbols are present any more and the vesicle has reached a final cell and is empty at this moment. As rules operating on the multiset enclosed in the vesicle when reading/consuming an input symbol we have used insertion, deletion, and substitution of multisets, working in the sequential derivation mode. As restricted variants, we have considered systems without allowing substitution of multisets and systems only allowing symbols to be inserted or deleted (or substituted). 56 A. Alhazov et al. We have shown how input-driven tissue P automata with multisets and strings can be characterized by input-driven register machines and input-driven counter automata, respectively. Moreover, we have exhibited some illustrative examples, for example, how the Dyck language or even some non-contextfree languages can be accepted by simple variants of input-driven tissue P automata. Several challenging topics remain for future research: for example, a characterization of the language classes accepted by several variants of tissue P automata accepting multisets or strings, especially for the input-driven variants, introduced in this paper is still open. As acceptance condition we have only considered reaching the final cell hwith an empty vesicle. The other variants of acceptance, i.e., only requiring the vesicle to be empty or else requiring to have reached the final cell with the vesicle containing no input symbol any more, are to be investigated in the future in more detail. References 1. Alhazov, A., Freund, R., Heikenwälder, H., Oswald, M., Rogozhin, Yu., Verlan, S.: Sequential P systems with regular control. In: Csuhaj-Varjú, E., Gheorghe, M., Rozenberg, G., Salomaa, A., Vaszil, Gy. (eds.) Membrane Computing - 13th International Conference, CMC 2012, Budapest, Hungary, August 28-31, 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7762, pp. 112–127. Springer (2013). https://doi.org/10.1007/978-3-642-36751-9_9 2. Alhazov, A., Freund, R., Ivanov, S., Verlan, S.: (tissue) P systems with vesicles of multisets. In: Csuhaj-Varjú, E., Dömösi, P., Vaszil, Gy. (eds.) Proceedings 15th International Conference on Automata and Formal Languages, AFL 2017, Debrecen, Hungary, September 4-6, 2017. EPTCS, vol. 252, pp. 11–25 (2017). https://doi.org/10.4204/EPTCS.252.6 3. Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Babai, L. (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. pp. 202–211. ACM (2004). https://doi.org/10.1145/1007352.1007390 4. Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56(3), 16:1– 16:43 (2009). https://doi.org/10.1145/1516512.1516518 5. Bensch, S., Holzer, M., Kutrib, M., Malcher, A.: Input-driven stack automata. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds.) Theoretical Computer Science - 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7604, pp. 28–42. Springer (2012). https://doi.org/10.1007/978-3-642-33475-7_3 6. von Braunmühl, B., Verbeek, R.: Input-driven languages are recognized in log n space. In: Karpinski, M. (ed.) Foundations of Computation Theory. pp. 40–51. Springer, Berlin, Heidelberg (1983) 7. Csuhaj-Varjú, E., Martín-Vide, C., Mitrana, V.: Multiset automata. In: Calude, C.S., Păun, Gh., Rozenberg, G., Salomaa, A. (eds.) Multiset Processing. pp. 69–83. Springer, Berlin, Heidelberg (2001) Input-Driven Tissue P Automata 57 8. Csuhaj-Varjú, E., Vaszil, Gy.: P automata or purely communicating accepting p systems. In: Păun, Gh., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) Membrane Computing. pp. 219–233. Springer, Berlin, Heidelberg (2003) 9. Dassow, J., Păun, Gh.: On the power of membrane computing. J. UCS 5(2), 33–49 (1999). https://doi.org/10.3217/jucs-005-02-0033 10. Dymond, P.W.: Input-driven languages are in log n depth. Information Processing Letters 26(5), 247–250 (1988). https://doi.org/10.1016/0020-0190(88)90148-2 11. Freund, R.: P automata: New ideas and results. In: Bordihn, H., Freund, R., Nagy, B., Vaszil, Gy. (eds.) Eighth Workshop on Non-Classical Models of Automata and Applications, NCMA 2016, Debrecen, Hungary, August 29-30, 2016. Proceedings. [email protected], vol. 321, pp. 13–40. Österreichische Computer Gesellschaft (2016) 12. Freund, R., Ibarra, O., Păun, Gh., Yen, H.C.: Matrix languages, register machines, vector addition systems. Third Brainstorming Week on Membrane Computing pp. 155–167 (2005) 13. Freund, R., Kogler, M., Rogozhin, Yu., Verlan, S.: Graph-controlled insertion-deletion systems. In: Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, DCFS 2010, Saskatoon, Canada, 8-10th August 2010. pp. 88–98 (2010). https://doi.org/10.4204/EPTCS.31.11 14. Freund, R., Oswald, M.: Tissue P systems and (mem)brane systems with mate and drip operations working on strings. Electr. Notes Theor. Comput. Sci. 171(2), 105– 115 (2007). https://doi.org/10.1016/j.entcs.2007.05.011 15. Freund, R., Păun, Gh.: How to obtain computational completeness in P systems with one catalyst. In: Proceedings Machines, Computations and Universality 2013, MCU 2013, Zürich, Switzerland, September 9-11, 2013. pp. 47–61 (2013). https://doi.org/10.4204/EPTCS.128.13 16. Freund, R., Rogozhin, Yu., Verlan, S.: Generating and accepting P systems with minimal left and right insertion and deletion. Natural Computing 13(2), 257–268 (2014). https://doi.org/10.1007/s11047-013-9396-3 17. Greibach, S.A.: Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science 7, 311–324 (1978). https://doi.org/10.1016/03043975(78)90020-8 18. Kudlek, M., Totzke, P., Zetzsche, G.: Multiset pushdown automata. Fundam. Inform. 93(1-3), 221–233 (2009). https://doi.org/10.3233/FI-2009-0098 19. Kutrib, M., Malcher, A., Wendlandt, M.: Tinput-driven pushdown, counter, and stack automata. Fundamenta Informaticae 155(1-2), 59–88 (2017). https://doi.org/10.3233/FI-2017-1576 20. Kutrib, M., Malcher, A., Wendlandt, M.: Queue automata: Foundations andÂădevelopments. In: Adamatzky, A. (ed.) Reversibility and Universality: Essays Presented to Kenichi Morita on the Occasion of his 70th Birthday. pp. 385–431. Springer (2018). https://doi.org/10.1007/978-3-319-73216-9_19 21. Martín-Vide, C., Pazos, J., Păun, Gh., Rodríguez-Patón, A.: A new class of symbolic abstract neural nets: Tissue P systems. In: Computing and Combinatorics, pp. 290– 299. Springer (2002). https://doi.org/10.1007/3-540-45655-4_32 22. Mehlhorn, K.: Pebbling mountain ranges and its application to dcfl-recognition. In: de Bakker, J., van Leeuwen, J. (eds.) Automata, Languages and Programming. pp. 422–435. Springer, Berlin, Heidelberg (1980) 23. Minsky, M.L.: Computation. Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ (1967) 58 A. Alhazov et al. 24. Okhotin, A., Salomaa, K.: Input-driven pushdown automata: nondeterminism and unambiguity. In: Bensch, S., Drewes, F., Freund, R., Otto, F. (eds.) Fifth Workshop on Non-Classical Models for Automata and Applications - NCMA 2013, Umeå, Sweden, August 13 - August 14, 2013, Proceedings. [email protected], vol. 294, pp. 31–33. Österreichische Computer Gesellschaft (2013) 25. Okhotin, A., Salomaa, K.: Input-driven pushdown automata with limited nondeterminism - (invited paper). In: Shur, A.M., Volkov, M.V. (eds.) Developments in Language Theory - 18th International Conference, DLT 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8633, pp. 84–102. Springer (2014). https://doi.org/10.1007/978-3-319-09698-8_9 26. Okhotin, A., Salomaa, K.: Descriptional complexity of unambiguous inputdriven pushdown automata. Theoretical Computer Science 566, 1–11 (2015). https://doi.org/10.1016/j.tcs.2014.11.015 27. Okhotin, A., Salomaa, K.: State complexity of operations on inputdriven pushdown automata. J. Comput. Syst. Sci. 86, 207–228 (2017). https://doi.org/10.1016/j.jcss.2017.02.001 28. Oswald, M.: P Automata. Ph.D. thesis, Faculty of Computer Science, TU Wien (2003) 29. Paun, A., Păun, Gh.: The power of communication: P systems with symport/antiport. New Generation Comput. 20(3), 295–306 (2002). https://doi.org/10.1007/BF03037362 30. Păun, Gh.: Computing with Membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000). https://doi.org/10.1006/jcss.1999.1693 31. Păun, Gh., Rozenberg, G., Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford, England (2010) 32. Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. 1-3. Springer (1997) 33. Bulletin of the International Membrane Computing Society (IMCS). http://membranecomputing.net/IMCSBulletin/index.php 34. The P Systems Website. http://ppage.psystems.eu/