P automata
| Erzsébet Csuhaj-Varjú and György Vaszil (2010), Scholarpedia, 5(4):9344. | doi:10.4249/scholarpedia.9344 | revision #129743 [link to/cite this article] |
Contents |
Introduction
P automata are automata-like accepting variants of membrane systems or P systems. The generic model is an antiport P system where the input sequences are distinguished as accepted or rejected input sequences. An input sequence is a sequence of multisets of objects which enter the system from the environment during the computational steps of the P automaton starting the computation from its initial configuration. Acceptance is defined by a set of final states, i.e., by a computable set of configurations satisfying certain conditions. The language accepted by a P automaton is obtained from the set of accepted input sequences by a mapping that orders words over a finite alphabet to the input sequences. The details of the construct can be found in (Csuhaj-Varjú et al. 2010, ref. 10).
The first variants of P automata were one-way P automata having only symport rules and special types of promoters (conditions on the selection of objects that can be communicated) (Csuhaj-Varjú, Vaszil 2002, ref.11), (Csuhaj-Varjú, Vaszil 2003, ref. 12), and analyzing P systems, which accept by halting configurations and map an input multiset to a word which is a permutation of the objects in the multiset (Freund, Oswald 2002, ref. 15).
Some formal details
A P automaton with (\(n\) membranes, \(n\ge 1\)) is a construct \[\Pi=(V,\mu,P_1,\ldots,P_n,c_0,\mathcal{F})\ ,\] where
- \(V\) is a finite alphabet of objects,
- \(\mu\) is a membrane structure with \(n\) membranes,
- \(P_i\) is a finite set of antiport rules associated to membrane \(i\) for all \(i\ ,\) \(1\leq i\leq n\ ,\)
- \(c_0\) is the initial configuration of \(\Pi\ ,\) and
- \(\mathcal{F}\) is a computable set of accepting configurations of \(\Pi\ .\)
A configuration of a P automaton with \(n\) membranes at a step of the computation is the \(n\)-tuple of multisets of objects which are present in the corresponding regions.
When an antiport rule \((x,out;y,in)\) is applied in a region (\(x\) and \(y\) are multisets consisting of elements of \(V\)), then objects of \(y\) enter the region from the directly upper region and in the same step the objects of \(x\) move to that region. In the case of symport rules the communication is one-way, i.e., \((x,out)\) or \((y,in)\ .\) If an antiport rule is associated with a promoter multiset \(z\ ,\) then it can only be applied in a region if all elements of \(z\) appear in that region. If it is associated with an inhibitor multiset \(z\ ,\) then no element of \(z\) must be present in the region.
A P automaton functions by changing its configurations, defined by the transition mapping \(\delta_X\) where \(X\) refers to the used computational mode (maximally parallel, sequential, etc.). For two configurations \(c_1\) and \(c_2\) of \(\Pi\ ,\) we have \(c_2\in \delta_{X}(v,c_1)\ ,\) if \(\Pi\) enters configuration \(c_2\) from configuration \(c_1\) by applying its rules in the \(X\) computation mode while the multiset of objects which enters the skin membrane from the environment is \(v\ .\)
The set of input sequences accepted by \(\Pi\) functioning with computation mode \(X\) is \[A_{X}(\Pi)= \{v_1\ldots v_s\mid\] there are configurations \(c_0,c_1,\ldots, c_s\) such that \(c_{i}\in \delta_X(v_i,c_{i-1})\ ,\) \(1\leq i\leq s\ ,\) and \(c_s\in {\mathcal F}\}\ .\)
Let \(f\) be a mapping from the set of multisets composed from elements of \(V\) to the words over an alphabet \(\Sigma\ .\) The language accepted by the P automaton \(\Pi\) with respect to \(f\) using the \(X\) computation mode is \[L_{X}(\Pi,f)= \{f(v_1)\ldots f(v_s)\in \Sigma^*\mid v_1\ldots v_s\in A_{X}(\Pi)\}\ .\]
An example
Let \(\Pi=(\{a,b,c\}, [_1\ [_2\ \ ]_2\ ]_1, P_1,P_2,(c,\emptyset),(\emptyset,\{a,b,c\}^*))\ ,\) with
\[P_1=\{(c,out; ca,in), (c,out; cb,in)\}\ ,\]
\[P_2=\{(ab,in),(abc,in)\}\ ,\] where multisets are denoted as strings, and \(\emptyset\) designates the empty multiset.
Then, for \(f\) with \(f(ac)=a\ ,\) \(f(bc)=b\ ,\) we have \[L_X(\Pi,f)=\{w\in\{a,b\}^*\mid w\text{ contains an equal number of symbols }a\text{ and }b\}\] for \(X\) being any of the maximally parallel or the sequential computation mode.
The accepting power of P automata
The class of languages accepted by the generic variant of P automata working in the maximally parallel computation mode and applying a non-erasing mapping to the input multisets to obtain the language, is equal to the class of context-sensitive languages. If the P automata work with the sequential computation mode (1-restricted parallel mode), then the obtained language class has sublogarithmic space complexity. If the mapping applied to the input multisets can also be erasing, then the language class of generic P automata is the class of recursively enumerable languages. These results were first published in (Csuhaj-Varjú et al. 2005, ref. 8), (Csuhaj-Varjú et al. 2006, ref. 9), see (Csuhaj-Varjú et al. 2010, ref. 10) for more details.
Any recursively enumerable language was shown to be acceptable both by one-way P automata and analyzing P systems. Computational completeness can also be obtained by several P automata variants with further constraints on the underlying P systems or on the way of their functioning. Any recursively enumerable language was shown to be acceptable with P automata with priorities (Cienciala, Ciencialová 2004, ref. 4), P automata with membrane channels (Oswald, Freund 2003, ref. 21), (Freund, Oswald 2004, ref. 16), P automata with conditional communication rules assigned to the membranes (Freund, Oswald 2004a, ref. 17), or evolution-communication P automata (Alhazov 2003, ref. 1).
Further features of P automata
P automata are also able to determine languages over infinite alphabets or languages consisting of infinite words. Due to the fact that the maximally parallel mode makes possible to input objects in one computational step in an unbounded number of copies, the inputs can be mapped to an infinite alphabet. Based on this observation, particular variants of P automata called P finite automata were constructed to realize an extension of the customary regular languages to regular languages over infinite alphabets (Dassow, Vaszil 2006, ref. 14). The description of languages consisting of infinite words is the consequence of the fact that P automata allow infinite runs, i.e., infinite sequences of configurations. The counterparts of \(\omega\)-Turing machines in terms of P automata, called \(\omega\)-P automata, can also be constructed for any well-known variant of acceptance mode of \(\omega\)-Turing machines (Freund et al. 2004, ref. 18).
Related variants
Further P automata variants are P automata with states (Madhu, Krithivasan 2003, ref. 20), where separate state sets are associated to the regions, active P automata, where the underlying P systems are active P systems and the construct is used for analyzing sentences (Bel-Enguix, Gramatovici 2004, ref. 2), (Bel-Enguix, Gramatovici 2006, ref. 3), and P automata with marked membranes which adopt some notions from brane calculi (Csuhaj-Varjú, Vaszil 2008, ref. 13). P automata counterparts of classical automata are formulated as Mealy multiset automata (Ciobanu, Gontineac 2006, ref. 5), simple P machines (Ciobanu, Gontineac 2006a, ref. 6), and P transducers (Ciobanu et al. 2006, ref. 7). Combinational P automata provide methods for constructing P automata for accepting the union, the concatenation, the Kleene closure, or the \(\omega\) closure of languages (Long, Fu 2007, ref. 19). Recent developments in the area are dP systems, i.e., distributed systems of P automata communicating and cooperating with each other. This concept builds a bridge between communication complexity theory and membrane computing (Paun, Pérez-Jiménez 2010, ref. 22).
References
1. A. Alhazov: Minimizing evolution-communication P systems and EC P automata. In: M. Cavaliere, C. Martín-Vide and Gh. Paun (eds.), Brainstorming Week on Membrane Computing. Technical Report 26/03 of the Research Group on Mathematical Linguistics, Rovira i Virgili University, Tarragona, Spain, 2003, 23-31.
2. G. Bel-Enguix and R. Gramatovici: Parsing with active P automata. In: C. Martín-Vide, G. Mauri, Gh. Paun, G. Rozenberg and A. Salomaa (eds.), Membrane Computing. International Workshop, WMC 2003, Tarragona, Spain, July 17-22, 2003. Revised Papers. Lecture Notes in Computer Science 2933, Springer, Berlin, 2004, 31-42.
3. G. Bel-Enguix and R. Gramatovici: Parsing with P automata. In: G. Ciobanu, M. Pérez-Jiménez and Gh. Paun ( eds.), Applications of Membrane Computing. Natural Computing Series, Springer, Berlin, 2006, 389-410.
4. L. Cienciala and L. Ciencialová: Membrane automata with priorities. Journal of Computer science and Technology 19(1) (2004), 89-97.
5. G. Ciobanu and V. M. Gontineac: Mealy multiset automata. International Journal of Foundations of Computer Science 17 (2006), 111-126.
6. G. Ciobanu and V. M. Gontineac: P machines: An automata approach to membrane computing. In: H.-J. Hoogeboom, Gh. Paun, G. Rozenberg and Arto Salomaa (eds.), Membrane Computing, 7th International Workshop, WMC 2006, Leiden, The Netherlands, July 17-21, 2006, Revised, Selected, and Invited Papers. Lecture Notes in Computer Science 4361, Springer, Berlin, 2006, 314-329.
7. G. Ciobanu, Gh. Paun and Gh. Stefanescu: P transducers. New Generation Computing 24(1) (2006), 1-28.
8. E. Csuhaj-Varjú, O.H. Ibarra and Gy. Vaszil: On the computational complexity of P automata. In: C. Ferretti, G. Mauri and C. Zandron (eds.), DNA Computing, 10th International Workshop on DNA Computing, DNA10, Milan, Italy, June 7-10, Revised Selected Papers. Lecture Notes in Computer Science 3384, Springer, 2005, 77-90.
9. E. Csuhaj-Varjú, O.H. Ibarra and Gy. Vaszil: On the computational complexity of P automata. Natural Computing 5(2) (2006), 109-126.
10. E. Csuhaj-Varjú, M. Oswald and Gy. Vaszil: P automata. Chapter in Handbook of Membrane Computing. Gh. Paun, G. Rozenberg and A. Salomaa (Eds.), Oxford University Press, 2010, 144-167.
11. E. Csuhaj-Varjú and Gy. Vaszil: P automata. In: Gh. Paun and C. Zandron (eds.), Pre-Proceedings of the Workshop on Membrane Computing WMC-CdeA 2002, Curtea de Arges, Romania, August 19-23, 2002. Pub. No.~1 of MolCoNet-IST-2001-32008, 2002, 177-192.
12. E. Csuhaj-Varjú and Gy. Vaszil: P automata or purely communicating accepting P systems. In: Gh. Paun, G. Rozenberg, A. Salomaa and C. Zandron (eds.), Membrane Computing. International Worskhop, WMC-CdeA 2002, Curtea de Arges, Romania, August 19-23, 2002, Revised Papers. Lecture Notes in Computer Science 2597, Springer, Berlin, 2003, 219-233.
13. E. Csuhaj-Varjú and Gy. Vaszil: (Mem)brane automata. Theoretical Computer Science 404(1-2) (2008), 52-60.
14. J. Dassow and Gy. Vaszil: P finite automata and regular languages over countably infinite alphabets. In: H.-J. Hoogeboom, Gh. Paun, G. Rozenberg and A. Salomaa (eds.), Membrane Computing. 7th International Workshop, WMC 2006, Leiden, The Netherlands, July 17-21, 2006, Revised, Selected, and Invited Papers. Lecture Notes in Computer Science 4361, Springer-Verlag, Berlin, 2006, 367-381.
15. R. Freund and M. Oswald: A short note on analysing P systems. Bulletin of the EATCS 78 (October 2002), 231-236.
16. R. Freund and M. Oswald: P automata with membrane channels. Artificial Life and Robotics 8(2004), 186-189.
17. R. Freund and M. Oswald: P systems with conditional communication rules assigned to membranes. Journal of Automata, Languages and Combinatorics 9(4) (2004), 387-397.
18. R. Freund, M. Oswald and L. Staiger\[\omega\]-P automata with communication rules. In: C. Martín-Vide, G. Mauri, Gh. Paun, G. Rozenberg and A. Salomaa (eds.), Membrane Computing. International Workshop, WMC 2003, Tarragona, Spain, July 17-22, 2003. Revised Papers. Lecture Notes in Computer Science 2933, Springer, Berlin, 2004, 203-217.
19. H. Long, Y. Fu: A general approach for building combinational P automata. International Journal of Computer Mathematics 84(12) (2007), 1715-1730.
20. M. Madhu and K. Krithivasan: On a class of P automata. International Journal of Computer Mathematics 80(9) (2003), 1111-1120.
21. M. Oswald, R. Freund: P Automata with Membrane Channels. In M. Sugisaka, H. Tanaka. (eds.), Proc. of the Eighth Int. Symp. on Artificial Life and Robotics, Beppu, Japan, 2003, 275-278.
22. Gh. Paun, M.J. Pérez-Jiménez: Solving Problems in a Distributed Way in Membrane Computing: dP systems. International Journal of Computers, Communication and Control V(2) (2010), 238-250.
Internal references
- Olaf Sporns (2007) Complexity. Scholarpedia, 2(10):1623.
- Gheorghe Paun (2010) Membrane Computing. Scholarpedia, 5(1):9259.
Further reading
E. Csuhaj-Varjú: P automata. In: G. Mauri, Gh. Paun, M. Pérez-Jiménez, G. Rozenberg and A. Salomaa (eds.), Membrane Computing: 5th International Workshop, WMC 2004, Milan, Italy, June, 14-16, 2004. Revised Selected and Invited Papers. Lecture Notes in Computer Science 3365, Springer, 2005, 19-35.
E. Csuhaj-Varjú: P Automata: Concepts, Results,and New Aspects. In: Gh. Paun, M. Pérez-Jiménez, A. Riscos-Nunez, G. Rozenberg and A. Salomaa (eds.), Membrane Computing: 10th International Workshop, WMC 2009, Curtea de Arges, Romania, August 24-27, 2009. Revised Selected and Invited Papers. Lecture Notes in Computer Science 5957, Springer, 2010, 1-15.
M. Oswald: P Automata. PhD dissertation, Vienna University of Technology, 2003.
Gy. Vaszil: Automata-like membrane systems - A natural way to describe complex phenomena. In: C. Campeanu, G. Pighizzini (eds.), 10th International Workshop on Descriptional Complexity of Formal Systems, July 16-18, Charlottetown, PE, Canada. Proceedings. University of Prince Edwards Island, 2008, 26-37.
The P system webpage: http://ppage.psystems.eu
