Testing Identifiable Kernel P Systems Using an X-machine Approach

Testing Identifiable Kernel P Systems Using an X-machine Approach Marian Gheorghe1, Florentin Ipate2, Raluca Lefticaru1,2, Ana T¸urlea2 1School of Electrical Engineering and Computer Science, University of Bradford, West Yorkshire, Bradford BD7 1DP, UK {m.gheorghe,r.lefticaru}@bradford.ac.uk 2Department of Computer Science, Faculty of Mathematics and Computer Science and ICUB University of Bucharest, Str. Academiei nr. 14, 010014, Bucharest, Romania [email protected],[email protected] Summary. This paper presents a testing approach for kernel P systems (kP systems), based on the X-machine testing framework and the concept of cover automaton. The testing methodology ensures that the implementation conforms the specifications, under certain conditions, such as the identifiably concept in the context of kernel P systems. Keywords: membrane computing; kernel P systems; X-machines; cover automata; testing. 1 Introduction Membrane computing [19] is a research field initiated twenty years ago [17, 18] by Gheorghe P˘aun. Initially inspired by the structure and functioning of the living cells, the field has known a fast development, different types of membrane systems (or P systems) being investigated. Having so many computational models (cell-like, tissue-like P systems, P colonies, kernel P systems) and also different software implementations for these models, it is important to devise testing methodologies that ensure that the implementation conforms with the specification. The testing task is not trivial, given the fact that the models are parallel and non-deterministic. Previous works on P systems testing include testing cell-like P systems with methods like finite state-based inspired [13], stream X-machine based testing [14], mutation testing for evaluating the efficiency of the test sets [16], model-checking based testing [15]. In this paper we will present a testing approach for kernel P systems, which is based on the X-machine testing approach and has as core concept the identifiability of multisets of rules. Kernel P systems are a model introduced in [9], which can be simulated using a software framework, called kPWorkbench [5] or some earlier 80 M. Gheorghe et al. variants (so called simple kP systems) using P-Lingua and the MeCoSim simulator [11]. This paper is structured as follows: Section 2 presents the preliminaries regarding kP systems and theoretical background regarding automata and X-machine based testing. Section 3 introduces the concept of identifiable kernel P systems, while Section 4 illustrates our testing approach for kP systems. Finally, conclusions are presented in Section 5. 2 Preliminaries This section briefly presents the notations used, then gives the basic definitions regarding kernel P systems [9] and presents the previous testing approaches for automata and X-machines, that have been applied also for testing simple cell-like P systems. In the following we introduce the notations used in the paper. For a finite alphabet A={a1, ..., ap},A∗represents the set of all strings (sequences) over A. The empty string is denoted by λand A+=A∗\{λ}denotes the set of non-empty strings. Andenotes the set of all strings of length n,n≥0, with members in the alphabet A, and A[n] = S0≤i≤nAidenotes the set of all strings of length at most n. For a string u∈A∗,|u|adenotes the number of occurrences of ain u, where a∈A. For a subset S⊆A,|u|Sdenotes the number of occurrences of the symbols from Sin u. The length of a string uis given by Pai∈A|u|ai. The length of the empty string is 0, i.e. |λ|= 0. A multiset over Ais a mapping f:A→N. Considering only the elements from the support of f(where f(aij)>0, for some j, 1 ≤j≤p), the multiset is represented as a string af(ai1) i1. . . af(aip) ip, where the order is not important. In the sequel multisets will be represented by such strings. 2.1 Kernel P systems In the following we will give a formal definition of kernel P systems (or kP systems) [9]. We start by introducing the concept of a compartment type utilised later in defining the compartments of a kernel P system (kP system). Definition 1. Tis a set of compartment types,T={t1, . . . , ts},where ti= (Ri, σi),1≤i≤s, consists of a set of rules, Ri, and an execution strategy, σi, defined over Lab(Ri), the labels of the rules of Ri. Kernel P systems have features inspired by object-oriented programming, for example one compartment type can have one or more instances. These instances share the same set of rules and execution strategies (so will deliver the same functionality), but they may contain different multisets of objects and different neighbours according to the graph relation specified. Testing Identifiable Kernel P Systems 81 Definition 2. AkP system of degree nis a tuple kΠ = (A, µ, C1, . . . , Cn, i0), where •Ais a finite set of elements called objects; •µdefines the membrane structure, which is a graph, (V, E), where Vis a set of vertices representing components (compartments), and Eis a set of edges, i. e., links between components; •Ci= (ti, wi,0),1≤i≤n, is a compartment of the system consisting of a compartment type,ti, from a set Tand an initial multiset, wi,0over A; the type ti= (Ri, σi)consists of a set of evolution rules, Ri, and an execution strategy, σi; •i0is the output compartment where the result is obtained. In this paper we will only deal with a simplified version of kP systems having one single compartment as this does not affect the general method introduced here and makes the presentation easier to follow. For details regarding the ways of flattening an arbitrary P system, including the kP system discussed in this paper, we refer mainly to [7], but similar approaches are also presented in other papers ([20], [1]). The kP system will be denoted kΠ = (A, µ1, C1,1),where µ1denotes the graph with one node. Within the general kP systems framework, the following types of evolution rules have been considered so far: •rewriting and communication rule: x→y{g}, where grepresents a guard (will be formally explained in Def. 4), x∈A+and y∈A∗, where yis a multiset with potential different compartment type targets (each symbol from the right side of the rule can be sent to a different compartment, specified by its type; if multiple compartments of the same type are linked to the current compartment, then one is randomly chosen to be the target). Unlike cell-like P systems, the targets in kP systems indicate only the types of compartments to which the objects will be sent, not particular instances (for example, y= (a1, t1). . . (ah, th), where h≥0, and for each 1 ≤j≤h,aj∈Aand tjindicates a compartment type from T). •structure changing rules: membrane division, membrane dissolution, link creation and link destruction rules, which all may also incorporate complex guards and that are covered in detail in [9]. However, this type of rules will not be considered in the following discussion. Remark 1. In the context of one compartment kP systems, there will be no need to specify the target compartment, so the rules will be simple communication rules, which in addition can have guards. Each rule occurring in the following discussion has the form r:x→y{g}, where ridentifies the rule and is called label,x→y is the rule itself and gis its guard. The part x→yis also called the body of the rule, denoted also b(r). The guards are constructed using multisets over A, as operands, and relational or Boolean operators. The definition of the guards is now introduced. We start with some notations. 82 M. Gheorghe et al. For a multiset wover Aand an element a∈A, we denote by |w|athe number of objects aoccurring in w. Let us denote Rel ={<, ≤,=,6=,≥, >}, the set of relational operators, γ∈Rel, a relational operator, and ana multiset, consisting of ncopies of a. We first introduce an abstract relational expression. Definition 3. If gis the abstract relational expression denoting γanand wa multiset, then the guard gapplied to wdenotes the relational expression |w|aγn. The abstract relational expression gis true for the multiset w, if |w|aγn is true. We consider now the following Boolean operators ¬(negation), ∧(conjunction) and ∨(disjunction). An abstract Boolean expression is defined by one of the following conditions: •any abstract relational expression is an abstract Boolean expression; •if gand hare abstract Boolean expressions then ¬g,g∧hand g∨hare abstract Boolean expressions. The concept of a guard, introduced for kP systems, is a generalisation of the promoter and inhibitor concepts utilised by some variants of P systems. Definition 4. If gis an abstract Boolean expression containing gi,1≤i≤q, abstract relational expressions and wa multiset, then gapplied to wmeans the Boolean expression obtained from gby applying gito wfor any i, 1≤i≤q. As in the case of an abstract relational expression, the guard gis true with respect to the multiset w, if the abstract Boolean expression gapplied to wis true. Example 1. If gis the guard defined by the abstract Boolean expression ≥a4∧< b2∨ ¬ > c and wa multiset, then gapplied to wis true if it has at least 4 a0s and less than 2 b0s or no more than one c. In addition to its evolution rules, each compartment type in a kP system has an associated execution strategy. The rules corresponding to a compartment can be grouped in blocks, each having one of the following strategies: In kP systems the way in which rules are executed is defined for each compartment type tfrom T– see Def. 1. As in Def. 1, Lab(R) is the set of labels of the rules R. Definition 5. For a compartment type t= (R, σ)from Tand r∈Lab(R), r1, . . . , rs∈Lab(R), the execution strategy,σ, is defined by the following •σ=λ, means no rule from the current compartment will be executed; •σ={r}– the rule ris executed; •σ={r1, . . . , rs}– one of the rules labelled r1, . . . , rswill be non-deterministically chosen and executed; if none is applicable then nothing is executed; this is called alternative or choice; •σ={r1, . . . , rs}∗– the rules are applied an arbitrary number of times ( arbitrary parallelism); Testing Identifiable Kernel P Systems 83 •σ={r1, . . . , rs}>– the rules are executed according to the maximal parallelism strategy; •σ=σ1&. . . &σs, means executing sequentially σ1, . . . , σs, where σi,1≤i≤s, describes any of the above cases; if one of σifails to be executed then the rest is no longer executed. These execution strategies and the fact that in any compartment several blocks with different strategies can be composed and executed offer a lot of flexibility to the kP system designer, similarly to procedural programming. Definition 6. Aconfiguration of a kP system, kΠ, with ncompartments, is a tuple c= (c1, . . . , cn), where ci∈A∗,1≤i≤n, is the multiset from compartment i. The initial configuration is (w1, . . . , wn), where wi∈A∗is the initial multiset of the compartment i,1≤i≤n. Atransition (or computation step), introduced by the next definition, is the process of passing from one configuration to another. Definition 7. Given two configurations c= (c1, . . . , cn)and c0= (c0 1, . . . , c0 n)of a kP system, kΠ, with ncompartments, where for any i, 1≤i≤n,ui∈A∗, and a multiset of rules Mi=rn1,i 1,i . . . rnki,i ki,i ,nj,i ≥0,1≤j≤ki, ki≥0, a transition or acomputation step is the process of obtaining c0from cby using the multisets of rules Mi,1≤i≤n, denoted by c=⇒(M1,...,Mn)c0, such that for each i,1≤i≤n, c0 iis the multiset obtained from ciby first extracting all the objects that are in the left-hand side of each rule of Mifrom ciand then adding all the objects athat are in the right-hand side of each rule of Mirepresented as (a, ti)and all the objects b that are in the right-hand side of each rule of Mj,j6=i, such that bis represented as (b, ti). In the theory of kP systems, each compartment might have its own execution strategy. In the sequel we focus on three such execution strategies, namely maximal parallelism, arbitrary parallelism (also called asynchronous execution) and sequential execution. These will be denoted by max, async and seq, respectively. When in a transition from cto c0using (M1, . . . , Mm), we intend to refer to a specific transition mode tm,tm ∈ {max, async, seq}, then this will be denoted by c=⇒(M1,...,Mm) tm c0. Acomputation in a P system is a sequence of transitions (computation steps). A configuration is called final configuration, if no rule can be applied to it. In a final configuration the computation stops. As usual in P systems, we only consider terminal computations, i.e., those arriving in a final configuration and using one of the above mentioned transition modes. We are now ready to define the result of a computation. Definition 8. For a kP system kΠ using the transition mode tm,tm ∈ {max, async, seq}, in each compartment, we denote by Ntm(Π)the number of objects appearing in the output compartment of a final configuration. 84 M. Gheorghe et al. Two kP systems kΠ and kΠ0are called equivalent with respect to the transition mode tm,tm ∈ {max, async, seq}, if Ntm(kΠ) = Ntm(kΠ0). In this paper we will only deal with kP systems having one single compartment as this does not affect the general method introduced here and makes the presentation easier to follow. Indeed, limiting the investigation to one compartment kP systems does not affect the generality of it due to the fact that there are ways of flattening an arbitrary P system, including the kP system discussed in this paper, into a P system with one single compartment. For details regarding the flattening of a P system we refer mainly to [7], but similar approaches are also presented in other papers ([20], [1]). Such a kP system will be denoted kΠ = (A, µ1, C1,1), where µ1denotes the graph with one node. The rules on the right-hand side will have multisets over A, as in the case of one single compartment there is no need to indicate where objects are sent to. 2.2 The W-method for testing finite cover automata In the following subsection we introduce the basic finite cover automata concepts [3, 12] and the W-method for generating test suites from finite cover automata [13]. We will consider only deterministic finite automata. Finite Cover Automata Definition 9. A finite automaton (abbreviated FA) is a tuple A= (V, Q, q0, F, h), where: •Vis the finite input alphabet; •Qis the finite set of states; •q0∈Qis the initial state; •F⊆Qis the set of final states; •h:Q×V→Qis the next-state function. Definition 10. Let A= (V, Q, q0, F, h)be a FA, U⊆V∗a finite language and l the length of the longest sequence(s) in U. Then Ais called a deterministic finite cover automaton (DFCA) of Uif LA∩V[l] = U. A minimal DFCA for Uis a DFCA for Uhaving the least number of states. The concept of DFCA was introduced by Cˆampeanu et al. [2], [3]. A minimal DFCA have considerably fewer states than the minimal FA that accepts U. The W-method In conformance testing there is a formal specification of the system (for example a FA) and the aim is to generate a test suite such that whenever the implementation under test (IUT) passes all tests, it is guaranteed to conform to the specification. The IUT is unknown but it is assumed to behave like some element from a set of Testing Identifiable Kernel P Systems 85 models, called fault model. In the case of the W-method, the fault model consists of all FAs A0with the same input alphabet Vas the specification A, whose number of states m0does not exceed the number of states mof Aby more than k(m0−m≤k), where k≥0 is a predetermined integer that must be estimated by the tester. The W-method was originally devised for when the conformance relation is automata equivalence [4], but in this paper we are interested in conformance for bounded sequences. This problem is described in [10] as follows: given an FA specification Aand an integer l≥1 (the upper bound) such that LAcontains at least one sequence of length l, we want to construct a set of sequences of length less than or equal to lthat can establish whether the implementation behaves as specified for all sequences in V[l]. Since LAcontains at least one sequence of length l,Ais a DFCA for LA∩V[l] and so the test suite will check whether the IUT model A0is also a DFCA for LA∩V[l]. Atest suite will be a finite set Yk⊆V[l] of input sequences that, for every A0in the fault model that is not V[l]-equivalent to A, will produce at least one erroneous output. That is, Aand A0are V[l]-equivalent whenever Aand A0are Yk-equivalent. Suppose the specification Aused for test generation is a minimal DFCA for LA∩V[l]. The W-method for bounded sequences, as developed in [12], involves the selection of two sets of input sequences, Sand W, as follows: Definition 11. S⊆V∗is called a proper state cover of Aif for every state qof Athere exists s∈Ssuch that h(q0, s) = qand |s|=level(q). Definition 12. W⊆V∗is called a strong characterisation set of Aif for every two states q1and q2of Aand every j≥0, if q1and q2are V[j]-distinguishable then q1and q2are (W∩V[j])-distinguishable. Naturally, in the above definition, it is sufficient for q1and q2to be (W∩V[j])- distinguishable when jis the length of the shortest sequences that distinguish between q1and q2. Once Sand Whave been selected, the test suite is obtained using the formula: Yk=SV [k+ 1](W∪ {λ})∩V[l]\ {λ}[12]. 2.3 X-machine based testing This subsection presents the X-machine based testing methodology, giving the formal definitions for X-machines, the test transformation of an X-machine and l-bounded conformance test suites. For more details and complete proofs [10] can be consulted, here only the main results are given. An X-machine is a finite automaton in which transitions are labelled by partial functions on a data set X instead of mere symbols [6]. Definition 13. An X-machine (XM) is a tuple Z= (Q, X, Φ, H, q0, x0)where: •Qis a finite set of states; 86 M. Gheorghe et al. •Xis the (possible infinite) data set; •Φis a finite set of distinct processing functions; a processing function is a non-empty (partial) function of type X→X; •His the (partial) next-state function, H:Q×Φ→Q; •q0∈Qis the initial state; •x0∈Xis the initial data value. We regard an X-machine as a finite automaton with the arcs labelled by functions from the set Φ, which is often called the type of Z. The automaton AZ= (Φ, Q, H, q0) over the alphabet Φis called the associated finite automaton (FA) of Z. The language accepted by the automaton is denoted by LAZ. Definition 14. Acomputation of Z is a sequence x0,...xn, with xi∈X, 1≤ i≤n, such that there exist φ1, . . . , φn∈Φwith φi(xi−1) = xi,1≤i≤nand φ1. . . φn∈LAZ. The set of computations of Z is denoted by Comp(Z). A sequence of processing functions that can be applied in the initial data value x0is said to be controllable. Definition 15. A sequence φ1, . . . , φn∈Φ∗, with φi∈Φ, 1≤i≤n, is said to be controllable if there exist x1,...xn∈Xsuch that φi(xi−1) = xi,1≤i≤n. A set P⊆Φ∗is called controllable if for every p∈P,pis controllable. Let us assume we have an X-machine specification Zand an (unknown) IUT that behaves like an element Z0of a fault model. In this case, the fault model will be a set of X-machines with the same data set X, type Φand initial data value x0as the specification. The idea of test generation from an X-machine is to reduce checking that the IUT Z0conforms to the specification Zto checking that the associated automaton of the IUT conforms to the associated automaton of the X-machine specification. Definition 16. The test transformation of Zis the (partial) function t:Φ∗→X∗ defined by: •t(λ) = x0.(1) •Let p∈Φ∗and φ∈Φ. – Suppose t(p)is defined. Let t(p) = x0. . . xn. ·If xn∈domφ then: ·If p∈LAZthen t(pφ) = t(p)φ(xn).(2) ·Else t(pφ) = t(p).(3) ·Else t(pφ)is undefined. (4) – Otherwise, t(pφ)is undefined. (5) Lemma 1. Let tbe a test transformation of Zand p=φ1. . . φn, with φ1, . . . , φn∈ Φ. •Suppose pis controllable and let x1, . . . , xn∈Xsuch that φi(xi−1) = xi,1≤ i≤n. Testing Identifiable Kernel P Systems 87 – If p∈LAZ, then t(p) = x0. . . xn. – If p /∈LAZ, then t(p) = x0. . . xk+1, where 0≤k≤n−1, is such that φ1. . . φk∈LAZand φ1. . . φkφk+1 /∈LAZ. •If p is not controllable, then t(p) is not defined. In order to establish that the associated automaton of the IUT Z0conforms to the associated automaton of the X-machine specification Z, we have to be able to identify the processing functions that are applied when the computations of Z and Z0are examined. Definition 17. Φis called identifiable if for all φ1, φ2∈Φ, whenever there exists x∈Xsuch that φ1(x) = φ2(x),φ1=φ2. If Φis identifiable, then we are able to establish if a controllable sequence of processing functions is correctly implemented by examining the computations of the specification Zand the implementation Z0, as shown by the following lemma. Lemma 2. Let Zand Z0be XMs with type Φ. Suppose Φis identifiable. Let p= φ1. . . φn∈Φ∗, with φi∈Φ,1≤i≤n, be a controllable sequence. Suppose t(p)is a computation of Zif and only if t(p)is a computation of Z0. Then p∈LAZif and only if p∈LA0 Z. Definition 18. Let Z be an X-machine and C a fault model for Z. An l-bounded conformance test suite for Z w.r.t. C, l > 0, is a set T⊆X[l+ 1] such that for every Z0∈Cthe following holds: if T∩Comp(Z) = T∩Comp(Z0)then Comp(Z)∩X[l+ 1] = Comp(Z0)∩X[l+ 1]. That is, whenever any element of Tis a computation of Zif and only if it is a computation of Z0,Z0conforms to Zfor sequences of length up to l. The following theorem shows that the test transformation defined earlier provides a mechanism for converting test suites for finite automata into set suites for X-machines. Theorem 1. Let Zbe an XM with type Φ, data set Xand initial data value x0. Suppose Φis identifiable and LAZ∪Φ[l]is controllable. Let Cbe a set of XMs such that for every Z0∈C,LA0 Z∩Φ[l]is controllable. Let P⊆Φ[l], such that, for every Z0∈C, whenever P∩LAZ=P∩LA0 Zwe have LAZ∩Φ[l] = LA0 Z∩Φ[l]. Then t(P)is an l-bounded conformance test suite for Zw.r.t. C. Let l > 0 be a predefined upper bound. We assume that Φis identifiable and LAZ∩Φ[l] is controllable. We assume that AZ, the associated automaton of Z, is a minimal DFCA for LAZ∪Φ[l] (if not, this is minimised 3). Suppose the fault model Cis the set of X-machines Z0with the same data set X, type Φand initial data value x0as Zsuch that LAZ0∩Φ[l] is controllable, whose number of states m0does not exceed the number of states mof Zby more than k(m0−m≤k), k≤0. Then an l-bounded conformance test suite for Zw.r.t. Cis 3The minimisation preserves the controlability requirements as the set LAZ∩Φ[l] remains unchanged. 94 M. Gheorghe et al. Consider again the P system kΠ1as in Example 3. Then ab =⇒r2bc and bc =⇒r4bc2, but bc2=⇒r4bc3does not hold since the rules of kΠ1must be applied in the maximally parallel mode. However, if we consider that in the fault model of the IUT rules may be applied in the asynchronous mode, the sequence r2r4r4is controllable. The fault model is also determined by the maximum number of states m+kthat the IUT may have, where mis the number of states of the X-machine Zand k≥0 is a non-negative integer estimated by the tester. 3. Construct an l-bounded conformance test suite. This is Tk=t(Yk), where Yk=SΦ[k+ 1](W∪ {λ})∩Φ[l]\ {λ}and tis a test transformation of Z. According to [4], the upper bound for the number of sequences in SΦ[k+ 1]W is m2·rk+1 and the total length of all sequences is not greater that m2·(m+ k)·rk+1,where ris the number of elements of Φ. In particular, for k= 0, the respective bounds are m2·rand m3·r. The increase in size produced by replacing Wwith W∪ {λ}in the above formula is negligible. Note that these bounds refer to the worst case; in an average case, the size of Ykis much lower. Furthermore, the size of t(Yk) is normally significantly lower than the size of Yksince only the controllable sequences are in the domain of t. The construction of Ykis straightforward, so we illustrate only the construction of the test transformation twith an example. Consider again rule application mode is maximal parallelism for kΦ and the asynchronous mode for the fault model. Consider the sequences s0=λ,s1=r2,s2=s1r4,s3=s2r4,s4= s3r4,s5=s4r1and s6=s5r1. By rule (1) of Definition 16, t(s0) = x0=ab. As ab =⇒r2bc, by rule (2) t(s1) = ab bc. Similarly, as bc =⇒r4bc2, by rule (2) t(s2) = ab bc bc2. On the other hand r4cannot be applied in configuration bc2in the maximally parallel mode, but bc2=⇒r4 F M bc3(in the asynchronous mode) and so, by rule (2), t(s3) = ab bc bc2bc3. Furthermore, bc3=⇒r4 F M bc4 and so, by rule (3) of Definition 16, t(s4) = t(s3) = ab bc bc2bc3. As r1cannot be applied in bc4, by rule (4) t(s5) is undefined. Furthermore, by rule (5), t(s6) is also undefined, so no test sequences will be generated for s5and s6. 5 Conclusions This paper presents a testing approach for kernel P systems that, under certain conditions, ensures that the implementation conforms to the specification. The methodology is based on the identifiable kernel P systems concept, which is essential for testing, and has been introduced for one-compartment kP systems with rewriting rules, but could be extended. Testing Identifiable Kernel P Systems 95 Acknowledgements This work is supported by a grant of the Romanian National Authority for Scientific Research, CNCS-UEFISCDI, project number PN-III-P4-ID-PCE-2016-0210. References 1. Agrigoroaiei, O., Ciobanu, G.: Flattening the transition P systems with dissolution. In: Gheorghe, M., Hinze, T., Paun, G., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing - 11th International Conference, CMC 2010, Jena, Germany, August 2427, 2010. Revised Selected Papers. Lecture Notes in Computer Science, vol. 6501, pp. 53–64. Springer (2010), https://doi.org/10.1007/978-3-642-18123-8_7 2. Cˆampeanu, C., Sˆantean, N., Yu, S.: Minimal cover-automata for finite languages. In: International Workshop on Implementing Automata. pp. 43–56. Springer (1998), https://doi.org/10.1007/3-540-48057-9_4 3. Cˆampeanu, C., Santean, N., Yu, S.: Minimal cover-automata for finite languages. Theoretical Computer Science 267(1-2), 3–16 (2001), https://doi.org/10.1016/ S0304-3975(00)00292-9 4. Chow, T.S.: Testing software design modeled by finite-state machines. IEEE Transactions on Software Engineering 4(3), 178–187 (1978), https://doi.org/10.1109/ TSE.1978.231496 5. Dragomir, C., Ipate, F., Konur, S., Lefticaru, R., Mierla, L.: Model checking kernel p systems. In: Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Y., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing. Lecture Notes in Computer Science, vol. 8340, pp. 151–172. Springer Berlin Heidelberg (2014), https://doi.org/10.1007/ 978-3-642-54239-8_12 6. Eilenberg, S.: Automata, languages, and machines. Academic press (1974) 7. Freund, R., Leporati, A., Mauri, G., Porreca, A.E., Verlan, S., Zandron, C.: Flattening in (tissue) P systems. In: Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Y., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing. Lecture Notes in Computer Science, vol. 8340, pp. 173–188. Springer Berlin Heidelberg (2014), https://doi.org/10.1007/978-3-642-54239-8_13 8. Gheorghe, M., Ipate, F.: Identifiable kernel P systems. Submitted (2018) 9. Gheorghe, M., Ipate, F., Dragomir, C., Mierla, L., Valencia-Cabrera, L., Garc´ıaQuismondo, M., P´erez-Jim´enez, M.J.: Kernel P Systems - Version I. Eleventh Brainstorming Week on Membrane Computing (11BWMC) pp. 97–124 (2013), http: //www.gcn.us.es/files/11bwmc/097_gheorghe_ipate.pdf 10. Gheorghe, M., Ipate, F., Konur, S.: Testing based on identifiable P systems using cover automata and X-machines. Information Sciences 372, 565–578 (2016), https: //doi.org/10.1016/j.ins.2016.08.028 11. Gheorghe, M., Ipate, F., Lefticaru, R., P´erez-Jim´enez, M.J., Turcanu, A., ValenciaCabrera, L., Garc´ıa-Quismondo, M., Mierla, L.: 3-col problem modelling using simple kernel P systems. International Journal of Computer Mathematics 90(4), 816–830 (2013), https://doi.org/10.1080/00207160.2012.743712 12. Ipate, F.: Bounded sequence testing from deterministic finite state machines. Theoretical Computer Science 411(16-18), 1770–1784 (2010), https://doi.org/10.1016/ j.tcs.2010.01.030 96 M. Gheorghe et al. 13. Ipate, F., Gheorghe, M.: Finite state based testing of P systems. Natural Computing 8(4), 833 (2009), https://doi.org/10.1007/s11047-008-9099-3 14. Ipate, F., Gheorghe, M.: Testing non-deterministic stream X-machine models and P systems. Electronic Notes in Theoretical Computer Science 227, 113–126 (2009), https://doi.org/10.1016/j.entcs.2008.12.107 15. Ipate, F., Gheorghe, M., Lefticaru, R.: Test generation from P systems using model checking. Journal of Logic and Algebraic Programming 79(6), 350–362 (2010), https: //doi.org/10.1016/j.jlap.2010.03.007 16. Lefticaru, R., Gheorghe, M., Ipate, F.: An empirical evaluation of P system testing techniques. Natural Computing 10(1), 151–165 (2011), https://doi.org/10.1007/ s11047-010-9188-y 17. P˘aun, G.: Computing with membranes. Tech. rep., Turku Centre for Computer Science (1998), http://tucs.fi/publications/view/?pub_id=tPaun98a 18. P˘aun, G.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000), https://doi.org/10.1006/jcss.1999.1693 19. The P systems website. http://ppage.psystems.eu, [Online; accessed 12/05/2018] 20. Verlan, S.: Using the formal framework for P systems. In: Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Y., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing. Lecture Notes in Computer Science, vol. 8340, pp. 56–79. Springer Berlin Heidelberg (2014), https://doi.org/10.1007/978-3-642-54239-8_6