Simulating the Fredkin Gate with Energy-Based P Systems

Simulating the Fredkin Gate with Energy–Based P Systems Alberto LEPORATI, Claudio ZANDRON, Giancarlo MAURI Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano – Bicocca Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy E-mail: leporati/zandron/[email protected] Abstract. Reversibility plays a fundamental role when the possibility to perform computations with minimal energy dissipation is considered. Many papers on reversible computation have appeared in literature: the most famous are certainly the work of Bennett on (universal) reversible Turing machines and the work of Fredkin and Toffoli on conservative logic. The latter is based upon the Fredkin gate, a reversible and “conservative” (according to a definition given by Fredkin and Toffoli) three–input/three–output boolean gate. In this paper we introduce energy–based P systems as a parallel and distributed model of computation in which the amount of energy manipulated and/or consumed during computations is taken into account. Moreover, we show how energy–based P systems can be used to simulate the Fredkin gate. The proposed P systems that perform the simulation turn out to be themselves reversible and conservative. 1 Introduction Considerations of thermodynamics of computing started in the early fifties of the twentieth century, when the possibility to perform computations with minimal energy dissipation was first considered. As a result some bounds on the amount of dissipated energy during transmission and computation were established [18, 4, 2, 19], and some quantum theoretic models of computation were proposed [3, 8]. As shown in [18], erasing a bit necessarily dissipates kT ln 2 Joule in a computer operating at temperature T, and generates a corresponding amount of entropy. Here kis Boltzmann’s constant and Tthe absolute temperature in degrees Kelvin, so that kT ≈3×10−21 Joule at room temperature. However, in [18] Landauer also demonstrated that only logically irreversible operations necessarily dissipate energy when performed by a physical computer. (An operation is logically reversible if its inputs can always be deduced from its outputs.) This result gave substance to the idea that logically reversible computations could be performed with zero internal energy dissipation. Indeed, since the appearance of [18] many authors have concentrated their attention on reversible computations. The importance of reversibility has grown further with the development of quantum computing, where the dynamical behavior of quantum 292 systems is usually described by means of unitary operators, which are inherently logically reversible. Let us note, however, that computing in a logically reversible way says nothing about whether or not the computation dissipates energy: it merely means that the laws of physics do not require that such a dissipation occurs. Many papers on reversible computation have appeared in literature; the most famous are certainly the work of Bennett on (universal) reversible Turing machines [4], and the work of Fredkin and Toffoli on conservative logic [11]. In particular, conservative logic has been introduced as a mathematical model that allows one to describe computations which reflect some properties of microdynamical laws of physics, such as reversibility and conservation of the internal energy of the physical system used to perform the computations. In this model, computations are performed by reversible circuits composed by Fredkin gates. In this paper we introduce energy–based P systems as a parallel and distributed model of computation in which the amount of energy manipulated and/or consumed during computations is taken into account. In the most general version, a given amount of energy is associated to each object, membrane and rule of the system. Some energy units are provided from the external environment and are used to build, transform or move objects. When an object is transformed into another object as the effect of the application of a rule, the required (resp., exceeding) energy is taken from (resp., released to) the region where the rule is applied. The application of each rule consumes a given amount of energy. Membranes can be thought of as energy reservoirs which are able to accumulate a (possibly bounded) amount of energy and subsequently release part of it. A special case of energy– based P systems are conservative P systems, where the amount of energy entering the system with the input values is completely returned with the output values at the end of the computation. We show how the Fredkin gate can be simulated with energy–based P systems. The proposed P systems that perform the simulation turn out to be themselves reversible and conservative. The simulation of reversible Fredkin circuits is currently under examination and is proposed here as a direction for future work. This is by no means the first time that energy is considered when dealing with P systems. We recall in particular [1, 12, 29, 13, 14, 15]. The last two papers were inspired by [16]. Moreover, this is not even the first paper which deals with the simulation of boolean gates and circuits by biologically inspired models of computation: for instance, in [23] a model for simulating boolean circuits (composed by and,or and not gates) with DNA algorithms is proposed, in [10] the same goal is reached using finite splicing, and in [9] some P systems that simulate boolean circuits are presented. In [32], the ideas found in [9] are applied to tissue P systems. Finally we also mention [17], where a biomolecular implantation of logically reversible computation using short strands of DNA as input and output lines of a Fredkin gate is demonstrated, and a method to connect Fredkin gates in order to create more complicated genetic networks is described. The paper is organized as follows. In section 2 we recall some basic notions on conservative logic and the Fredkin gate. In section 3 we introduce the basic version of energy–based P systems, where energy is only associated to symbol objects with the requirement that for each rule the amount of energy occurring on the left side is the same as the amount of energy occurring on the right side. Conservative energy–based P systems are also introduced. In section 4 we show how the Fredkin gate can be simulated using this kind of P systems. In section 5 we propose some extensions to our model together with some open problems. Section 6 concludes the paper with further directions for future research. 293 2 Conservative Logic and the Fredkin Gate Conservative logic is a mathematical model of computation based upon the so called Fredkin gate, a three–input/three–output boolean gate originally introduced by Petri in [31] whose input/output map fg :{0,1}3→ {0,1}3associates any input triple (x1, x2, x3) with its corresponding output triple (y1, y2, y3) as follows: y1=x1 y2= (¬x1∧x2)∨(x1∧x3) y3= (x1∧x2)∨(¬x1∧x3) (1) Table 1 shows the truth table of the Fredkin gate. A useful point of view is that the Fredkin x1x2x37→ y1y2y3 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 Table 1: Truth table of the Fredkin gate gate behaves as a conditional switch (see Figure 1): that is, FG(1, x2, x3) = (1, x3, x2) and FG(0, x2, x3) = (0, x2, x3) for every x2, x3∈ {0,1}. In other words, x1can be considered as a control input whose value determines whether the input values x2and x3have to be exchanged or not. 1 a b 1 EXC b a 0 a b 0 Id a b Figure 1: The Fredkin gate as a conditional switch The Fredkin gate is functionally complete for Boolean logic: in fact, by fixing x3= 0 we get y3=x1∧x2, whereas by fixing x2= 1 and x3= 0 we get y2=¬x1. The Fredkin gate is also reversible, that is, it computes a bijective map on {0,1}3. As we can see in Table 1, for every input/output pair the number of 1’s in the input triple is the same as the number of 1’s in the output triple. In other words, the output triple is obtained by applying an appropriate permutation to the input triple. Let us note that the applied permutation is input–dependent: namely, if x1= 1 then the applied permutation is (2 3), whereas if x1= 0 then the applied permutation is the identity. Indeed, fg seems to be the most elementary input–dependent permutation which can be conceived. In [11] Fredkin and Toffoli interpret the conservation of the number of 1’s between input 294 and output triples as the conservation of the amount of energy associated to the input triple, thus assuming that two different triples having the same number of 0’s and 1’s require the same amount of energy to be realized in a physical system. Let us note that conservativeness is defined (both here and in [11]) as a mathematical notion; namely, it is not required that the entire energy used to perform the computation is preserved, or that the computing device be a conservative physical system (an ideal but unrealistic situation). In particular, we do not consider the energy needed to actually perform the computation, that is, to transform the input values into output values. Basing upon these observations, Fredkin and Toffoli introduce a computational model for reversible and conservative computations. Computations are performed by reversible Fredkin circuits having the same number nof input and output lines. Under this constraint, the conservativeness requirement (preservation of the number of 1’s) is again equivalent to the requirement that the output n-tuple is obtained by applying an appropriate (input–dependent) permutation to the input n-tuple. Here we just mention the fact that every permutation can be written in a unique way (up to the order of factors) as a composition of transpositions. This means not only that the Fredkin gate can be used to build an appropriate circuit to perform any given conservative computation (and thus it is universal also in this sense with respect to conservative computations), but also that it is the most elementary conceivable operation that can be used to describe conservative computations. It is important to note that reversibility and conservativeness are two independent notions: a function (computed by a gate or circuit) may be only reversible, only conservative, both or none of them. However, for any function f:{0,1}n→ {0,1}mit is possible to build a new function fR:{0,1}n+m→ {0,1}n+msuch that fRis a bijection on the set {0,1}n+mand moreover: ∀x∈ {0,1}nfR(x, 0m) = (x, f(x)), where 0mis the m-tuple consisting of all 0’s. The function fRis simply defined as follows: ∀x∈ {0,1}n,∀y∈ {0,1}mfR(x, y) = (x, y ⊕f(x)), where ⊕denotes the bitwise xor operation. Hence, given a circuit that computes the function fit is always possible to build a reversible circuit that, using some additional input and output lines, is able to compute the values assumed by fon its last moutput lines. Analogously, for any function f:{0,1}n→ {0,1}mit is possible to build a conservative function fCthat computes the values assumed by fin its first moutput bits. Precisely, let us define the following quantities: Of= max ½0,max x∈{0,1}n{Em(f(x)) −En(x)}¾, Zf= max ½0,max x∈{0,1}n{En(x)−Em(f(x))}¾. Informally, Of(resp., Zf) is the maximum number of 1’s (resp., 0’s) in the output pattern that should be converted to 0 (resp., 1) in order to make the function conservative. We can thus define fCas an (n+Of+Zf)–input/(m+Of+Zf)–output function such that: ∀x∈ {0,1}nfC(x, 1Of,0Zf) = (f(x),1w(x),0z(x)), 295 where 1k(resp., 0k) is the k–tuple consisting of all 1’s (resp., 0’s), and the pair (1w(x),0z(x))∈ {0,1}Of+Zfis such that w(x) = Of+En(x)−Em(f(x)) and z(x) = Zf−En(x) + Em(f(x)). Hence, we use some additional inputs (resp., outputs) in order to provide (resp., remove) the required (resp., exceeding) energy that allows fCto compute fin a conservative way. It is also possible, for any given function f:{0,1}n→ {0,1}m, to extend the reversible function fRbuilt above to a reversible and conservative function fRC by adding some additional input and output bits. For the proof we refer the reader to [7]. In [6, 7, 22] conservativeness has been extended to reversible and non reversible gates whose input and output lines may assume a finite number dof truth values. Some many– valued extensions of the Fredkin gate have also been presented. By associating equispaced energy levels to the truth values, the authors have shown that their notion of conservativeness corresponds to the energy conservation principle applied to the data which are manipulated during the computation. In the same papers the notion of conservative computation has been introduced, under the reasonable assumption that a gate may store, or accumulate, some energy in its internal machinery. Moreover, a new NP–complete decision problem concerning conservative computations has been defined. Some constant factor approximation algorithms for an associated NP–hard optimization problem are currently under examination. 3 Energy–Based P Systems P systems (also called membrane systems) were introduced in [24] as a new class of distributed and parallel computing devices, inspired by the structure and functioning of cells. The basic model consists of a hierarchical structure composed by several membranes, embedded into a main membrane called the skin. Membranes divide the Euclidean space into regions, that contain some objects (represented by symbols of an alphabet) and evolution rules. Using these rules, the objects may evolve and/or move from a region to a neighboring one. The rules are applied in a nondeterministic and maximally parallel way: all the objects that may evolve are forced to evolve. A computation starts from an initial configuration of the system and terminates when no evolution rule can be applied. The result of a computation is the multiset of objects contained into an output membrane or emitted from the skin of the system. In what follows we assume that the reader is already familiar with the basic notions and the terminology underlying P systems. For details, see [27]. The latest information about P systems can be found on the Web page http://psystems.disco.unimib.it/. In order to take into account the amount of energy used during computations, we define a new model which we call energy–based P system. In this model, we consider a special symbol ewhich denotes a free energy unit floating into regions; moreover, the rules are defined accordingly to conservativeness considerations. We will show how this model can be used to simulate the Fredkin gate. Formally, an energy–based P system (of degree m≥1) is a construct Π = (A, ε, µ, e, w1, . . . , wm, R1, . . . , Rm, iin, iout), where: •Ais an alphabet; its elements are called objects; 296 •ε:A→R+is a linear mapping that associates to each object a∈Athe real value ε(a) (also denoted by εa), which can be thought of as the “energy value of a”. Precisely, if A={a1, a2, . . . , ad}then for all i∈ {1,2, . . . , d}it holds ε(ai) = ε(a1) + (i−1)δfor an appropriate real value δ > 0. Hence, the energy values considered in the system are equispaced by the quantity δ. Through an appropriate rescaling, we can always assume that all energy values are positive integer values, and that δ= 1; •µis a hierarchical membrane structure consisting of mmembranes. For the sake of clarity, we will label membranes with mnemonic identifiers which recall their function; •e6∈ Ais a special symbol that denotes one free energy unit, that is, one unit of energy which is not embedded into any object; •wi, for all i∈ {1, . . . , m}, specify the multisets (over A∪ {e}) of objects initially present in region i; •Ri, for all i∈ {1, . . . , m}, is a finite set of evolution rules over Aassociated with region i. Only rules of the following types are allowed: aek→(b, p) , a→(b, p)ek,e→(e, p), where a, b ∈A,p∈ {here,in(name),out}and kis a non negative integer; •iin is an integer between 1 and mand specifies the input membrane of Π; •iout is an integer between 0 and mand specifies the output membrane of Π. If iout = 0, then the environment is used for the output, that is, the output value is the multiset of objects (over A) emitted from the skin. A special attention is due to the definition of rules. The meaning of rule aek→(b, p), with a, b ∈A,p∈ {here,in(name),out}, and ka positive integer number, is the following: the object a, in presence of kfree energy units, is allowed to be transformed into object b. If p= here then the new object bremains in the same region; if p= out then bexits from the current membrane. Finally, if p= in(name) then benters into the membrane labelled with name, which must be a child of the current membrane in the membrane hierarchy. The meaning of rule a→(b, p)ek, when kis a positive integer number, is analogous. The object ais allowed to be transformed into object bby releasing kunits of free energy. As above, the new object bmay optionally move one level up or down into the membrane hierarchy. The kfree energy units can now be used by another rule to produce “more energetic” objects from “less energetic” ones. When k= 0 the rule aek→(b, p) is written as a→(a, p), and simply moves (if p6= here) the object aupward or downward into the membrane hierarchy, without acquiring nor releasing any free energy unit. Analogously, rules e→(e, p) simply move (if p6= here) one unit of free energy upward or downward into the membrane hierarchy. A further constraint for the definition of rules is that each rule must be “conservative”, in the sense that the amount of energy occurring on the left side of the rule must be the same as the amount of energy which occurs on the right side. With a little abuse of notation, when the pair (x, p), with x∈A∪ {e}and p∈ {here,in(name),out}, appears into a rule we will write xp. Also, if p= in(name) and no 297 confusion arises we will usually write just the name of the membrane. Moreover, instead of writing ekwe will sometimes explicitly write kinstances of e. It is also understood that the position of ek(that is, on the left or on the right of the symbol of A) either into the left or into the right side of a rule is uninfluent. Finally, when the position pof an object which occurs in the right side of a rule is “here” we will omit to write it. Example 3.1 Let us assume A={a, b, c, d}, where the objects have energy values εa= 1, εb= 2,εc= 3 and εd= 4. Then the rule be2→(d, out)(also written as bee →dout) transforms an instance of the object binto an instance of the object d, provided that two free energy units are available, and makes the new object dleave the current membrane. On the other hand, the rule c→(a, here)e2(also written as c→aee) transforms an instance of the object cinto an instance of the object aand releases two free energy units into the region in which the rule is defined. Aconfiguration of Π is the collection {M1, . . . , Mm}of multisets (over A∪ {e}) of objects contained in each region of the system. {w1, . . . , wm}is called the initial configuration. For two configurations {M1, . . . , Mm},{M0 1, . . . , M0 m}of Π we write {M1, . . . , Mm} ⇒ {M0 1, . . . , M0 m}to denote a transition from {M1, . . . , Mm}to {M0 1, . . . , M0 m}, that is, the parallel application of one or more rules of the system. The reflexive and transitive closure of ⇒is denoted by ⇒∗. A final configuration is a configuration where no rule can be applied. Acomputation is a sequence of transitions between configurations of Π, starting from the initial configuration. A computation is successful if and only if it reaches a final configuration or, in other words, it halts. It is understood that the multiset (over A, that is, not considering free energy units) of objects which occur in wiin are the input values for the computation. Analogously, the multiset (over A) of objects occurring in the output membrane (or emitted from the skin if iout = 0) in the final configuration is the output of the computation. A non–halting computation produces no output. Since energy is an additive quantity, it is natural to define the energy of a multiset as the sum of the amounts of energy associated to each instance of the objects which occur into the multiset. Analogously, the energy of a configuration is the sum of the amounts of energy associated to each multiset which occurs into the configuration. A conservative computation is a computation where each configuration has the same amount of energy. Aconservative energy–based P system is an energy–based P system that performs only conservative computations. 4 Simulating the Fredkin Gate with Energy–Based P Systems In this section we show how P systems, and specifically the energy–based variant introduced in the previous section, can be used to simulate a Fredkin gate. When trying to simulate a Fredkin gate with a P system, perhaps the simplest idea is to associate a symbol to each possible input/output triple as shown in the table on the left side of Figure 2. Then, the gate is trivially simulated as shown on the right side of the same figure: when a symbol corresponding to the input triple is injected into the skin of the P system, in one step the symbol corresponding to the output triple is expelled into the environment. However, this method is not suitable to simulate circuits composed by Fredkin gates. In fact, consider for instance the circuit in Figure 3. The 298 Triple Symbol (0,0,0) a (0,0,1) b (0,1,0) c (0,1,1) d (1,0,0) e (1,0,1) f (1,1,0) g (1,1,1) h FG a a out bout cout dout e e out f g out g f out h h out b c d Figure 2: A trivial simulation of the Fredkin gate with a P system. To each possible input/output triple of the gate is associated a symbol of the alphabet x x x x x 2 3 4 5 6 1 2 3 x1y1 y2 y3 y4 y5 y6 Figure 3: A 6–input/6–output Fredkin circuit composed by three gates symbol corresponding to the input triple of gate number 3 depends upon the symbols corresponding to the output triples of both gates 1 and 2. It is immediately seen that the output symbols of a layer of a Fredkin circuit cannot be immediately used as an input to the next layer: instead, a non trivial transformation is required. An alternative approach, that solves the previous problem, is to use an energy–based P system as defined in the previous section. The system has 18 objects, with integer energies going from 1 to 18. However, we actually use only 12 objects: precisely, those having energies from 1 to 10 and those having energies 17 and 18. The objects having energies from 11 to 16 never appear into the system. These choices are made in order to have objects with distinct energies and to guarantee conservativeness. For the sake of clarity, we denote the 12 objects used into the system by [b, j] and [b0, j], with b, b0∈ {0,1} and j∈ {1,2,3}. Intuitively, [b, j] and [b0, j] indicate the boolean value which occurs in the j-th line of the Fredkin gate. It will be clear from the simulation that we need two different symbols to represent each of these boolean values. The energies are associated to the objects as illustrated in Table 2. In Figure 4 the energy–based P system that simulates the Fredkin gate is depicted. The simulation proceeds as follows. The input values [x1,1],[x2,2],[x3,3], with x1, x2, x3∈ {0,1}, are injected into the skin. If x1= 0 then the object [0,1] enters into membrane id, where it is transformed to the object [00,1] by releasing 8 units of energy. The object [00,1] leaves membrane id and waits for 8 energy units to transform back 299 Object Energy [0,1] 17 [1,1] 18 [0,2] 1 [1,2] 2 [0,3] 3 [1,3] 4 Object Energy [00,1] 9 [10,1] 10 [00,2] 5 [10,2] 6 [00,3] 7 [10,3] 8 Table 2: Association between objects and energies in the energy–based P system that simulates a Fredkin gate FG [0,1] ID ID [b,2] [b,2] [0,1] ID EXC [b,3] [b,3] [b,3] [b,3] [b’,1]ee [b,1] out [b’,2] e[b,2] out out e[b,3][b’,3] [1,1] [1,1] EXC EXC [b,2] [b,2] EXC ID [b,2]e out [b’,3] [b,3]e out [b’,2] [b,2] [b,2] out out [b,3] [b,3] [1,1] out [1’,1] ee [b,2]e out [b,3]e out [b,2] [b,2] out out [b,3] [b,3] out [0,1] [0’,1] ee [b’,2] [b’,3] Figure 4: Simulation of the Fredkin gate with an energy–based P system to [0,1] and leave the system. The objects [x2,2] and [x3,3], with x2, x3∈ {0,1}, may enter nondeterministically either into membrane id or into membrane exc; however, if they enter into exc they cannot be transformed to [x0 2,3] and [x0 3,2] since in exc there are no free energy units. Thus the only possibility for objects [x2,2] and [x3,3] is to leave exc and choose again between membranes id and exc in a nondeterministic way. Eventually, after some time they enter (one at the time or simultaneously) into membrane id. Here they have the possibility to transform to [x0 2,2] and [x0 3,3] respectively, using the 8 units of free energy which occur into the region enclosed by id (alternatively, they have the possibility to leave id and choose nondeterministically between membranes id and exc once again). When the objects [x0 2,2] and [x0 3,3] are produced they immediately leave id, and are only allowed to transform back to [x2,2] and [x3,3] respectively, releasing 8 units of energy. The objects [x2,2] and [x3,3] just produced leave the system, and the 8 units of energy can only be used to transform [00,1] back to [0,1] and expel it from the skin. On the other hand, if x1= 1 then the object [1,1] enters into membrane exc where it is transformed into the object [10,1] by releasing 8 units of energy. The object [10,1] leaves the membrane exc and waits for 8 energy units to transform back to [1,1] and leave the system. Once again the objects [x2,2] and [x3,3], with x2, x3∈ {0,1}, may choose 300 [16] S. Ji. The Bhopalator: An information/energy dual model of the living cell. In Pre– Proceedings of the Workshop on Membrane Computing, Curtea de Arges, Romania, August 2001, Technical Report 17/01 of Research Group on Mathematical Linguistics, Rovira i Virgili University, Tarragona, Spain, 2001, pp. 123-142 and Fundamenta Informaticae, 49(1-3):147–165, 2002. [17] J.P. Klein, T.H. Leete, H. Rubin. A biomolecular implementation of logically reversible computation with minimal energy dissipation. Biosystems 52:15–23, 1999. [18] R. Landauer. Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 5:183–191, 1961. [19] R. Landauer. Uncertainty principle and minimal energy dissipation in the computer. International Journal of Theoretical Physics, 21(3-4):283–297, 1982. [20] M. Madhu, K. Krithivasan. P systems with membrane creation: Universality and efficiency. In M. Margenstern, Y. Rogozhin (Eds.), Machines, Computations, and Universality, Proceedings of the Third International Conference, MCU 2001, Chisinau, Moldavia, May 2001, Lecture Notes in Computer Science 2055, Springer, 2001, pp. 276–287. [21] C. Martin–Vide, V. Mitrana. P Systems with valuations. In I. Antoniou, C. S. Calude, M. J. Dinneen (Eds.), Unconventional Models of Computation, UMC’2K, Solvay Institutes, Brussels, December 2000, DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, Springer, 2000, pp. 154–166. [22] G. Mauri, A. Leporati. On the computational complexity of conservative computing. In Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), Lecture Notes in Computer Science 2747, Springer– Verlag Heidelberg, 2003, pp. 92–112. [23] M. Ogihara, A. Ray. Simulating Boolean circuits on a DNA computer. Technical Report 631, 1996. Available at: http://citeseer.nj.nec.com/ogihara96simulating.html [24] G. P˘aun. Computing with membranes. Journal of Computer and System Sciences, 1(61):108–143, 2000. See also Turku Centre for Computer Science — TUCS Report No. 208, 1998. Available at: http://www.tucs.fi/Publications/techreports/TR208.php [25] G. P˘aun. Computing with membranes. An introduction. Bulletin of the EATCS, 67:139–152, February 1999. [26] G. P˘aun. Computing with membranes. A variant: P systems with polarized membranes. International Journal on Foundations of Computer Science, 11(1):167–182, 2000. See also CDMTCS Technical Report 098, University of Auckland, 1999. Available at: http://www.cs.auckland.ac.nz/CDMTCS [27] G. P˘aun. Membrane Computing. An Introduction. Springer–Verlag, Berlin, 2002. [28] G. P˘aun, G. Rozenberg. A guide to membrane computing. Theoretical Computer Science, 287(1):73–100, 2002. [29] G. P˘aun, Y. Suzuki, H. Tanaka. P Systems with energy accounting. International Journal Computer Math., 78(3):343–364, 2001. 307 [30] G. P˘aun, T. Yokomori. Membrane computing based on splicing. In E. Winfree, D. K. Gifford (Eds.), Proceedings of the 5th DIMACS Workshop on DNA Based Computers, Massachusetts Institute of Technology, Cambridge, MA, USA, June 1999, American Mathematical Society, 1999, pp. 213–227. [31] C. A. Petri. Gr¨undsatzliches zur Beschreibung diskreter Prozesse. In Proceedings of the 3rd Colloquium ¨uber Automatentheorie (Hannover, 1965), Birkh¨auser Verlag, Basel, 1967, pp. 121–140. English translation: Fundamentals of the Representation of Discrete Processes, ISF Report 82.04, 1982. [32] V. J. Prakash, K. Krithivasan. Simulating Boolean circuits with tissue P systems. Manuscript, 2004. [33] H. Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer– Verlag, 1999. [34] C. Zandron, C. Ferretti, G. Mauri. Using membrane features in P systems. Romanian Journal of Information Science and Technology, 4(1-2):241–257, 2001. [35] C. Zandron, G. Mauri, C. Ferretti. Universality and normal forms on membrane systems. In R. Freund, A. Kelemenova (Eds.), Proceedings of the International Workshop on Grammar Systems, July 2000, Bad Ischl, Austria, 2000, pp. 61–74. 308