Published in Volume XXI, Issue 2, 2011, pages 199-225
Authors: J. Kleijn, M. Koutny, G. Rozenberg
Abstract
Petri nets are a general and well-established model of concurrent and distributed computation and behaviour, including that taking place in biological systems. In this survey paper, we are concerned with intrinsic relationships between Petri nets and two formal models inspired by aspects of the functioning of the living cell: membrane systems and reaction systems. In particular, we are interested in the benefits that can result from establishing strong semantical links between Petri nets and membrane systems and reaction systems. We first discuss Petri nets with localities reflecting the compartmentalisation modelled in membrane systems. Then special attention is given to set-nets, a new Petri net model for reaction systems and their qualitative approach to the investigation of the processes carried out by biochemical reactions taking place in the living cell.
Full Text (PDF)References
[1] A.Alhazov. P Systems Without Multiplicities of Symbol-objects. Information Processing Letters 100:124-129, 2006
[2] E.Badouel and P.Darondeau. Theory of Regions. volume 1491 of Lecture Notes in Computer Science, pages 529-586, Springer-Verlag, 1998
[3] R.Brijder, A.Ehrenfeucht, M.G.Main and G.Rozenberg. A Tour of Reaction Systems. Int. Journal of Foundations of Computer Science, 2011
[4] N.Busi. Analysis Issues in Petri Nets with Inhibitor Arcs. Theoretical Computer Science 275:127-177, 2002
[5] L.Czaja. A Calculus of Nets. Cybernetics and Systems Analysis 29:185- 193, 1993
[6] P.De Bra, G.J.Houben and Y.Kornatzky. A Formal Approach to Analyzing the Browsing Semantics of Hypertext. Proc. CSN-94 Conference, pages 78-89, 1994
[7] J.Desel and G.Juhas. What Is a Petri Net? volume 2128 of Lecture Notes in Computer Science, pages 1-25, Springer-Verlag, 2001
[8] J.Desel and W.Reisig. volume 1491 of Lecture Notes in Computer Science, pages 122-173, Springer-Verlag, 1998
[9] C.Dufourd, A.Finkel and Ph.Schnoebelen. Reset Nets Between Decidability and Undecidability. volume 1443 of Lecture Notes in Computer Science, pages 103-115, Springer-Verlag, 1998
[10] A.Ehrenfeucht, M.Main and G.Rozenberg. Combinatorics of Life and Death for Reaction Systems. International Journal of Foundations of Computer Science 22:345-356, 2009
[11] A.Ehrenfeucht and G.Rozenberg. Reaction Systems. Fundamenta Informaticae 76:1-18, 2006
[12] A.Ehrenfeucht, M.Main and G.Rozenberg. Events and Modules in Reaction Systems. Theoretical Computer Science 376:3-16, 2007
[13] M.Hack. Decision Problems for Petri Nets and Vector Addition Systems. Technical Memo 59, Project MAC, MIT, 1975
[14] M.Heiner, D.Gilbert and R.Donaldson. Petri Nets for Systems and Synthetic Biology. volume 5016 of Lecture Notes in Computer Science, pages 215-264, Springer-Verlag, 2008
[15] O.H.Ibarra, Z.Dang and O.Egecioglu. Catalytic P Systems, Semilinear Sets, and Vector Addition Systems. Theoretical Computer Science 312:379-399, 2004
[16] R.Janicki and M.Koutny. Semantics of Inhibitor Nets. Information and Computation 123:1-16, 1995
[17] K.Jensen. Coloured Petri Nets and the Invariant-Method. Theoretical Compututer Science 14:317-336, 1981
[18] R.M.Karp and R.E.Miller. Parallel Program Schemata. J. Comput. Syst. Sci. 3:147-195, 1969
[19] J.Kleijn and M.Koutny. Processes of Petri Nets with Range Testing. Fundamenta Informaticae 80:199-219, 2007
[20] J.Kleijn and M.Koutny. Processes of Membrane systems with Promoters and Inhibitors. Theoretical Computer Science 404:112-126, 2008
[21] J.Kleijn and M.Koutny. A Petri Net Model for Membrane Systems with Dynamic Structure. Natural Computing 8:781-796, 2009
22] J.Kleijn and M.Koutny. Step Coverability Algorithms for Communicating Systems. Science of Computer Programming, 2010, doi:10.1016/j.scico2010.11.003
[23] J.Kleijn and M.Koutny. Petri Nets and Membrane Computing. In: [36], pages 389-412, 2010
[24] J.Kleijn and M.Koutny. Membrane systems with Qualitative Evolution Rules. Fundamenta Informaticae, to appear (2011)
[25] J.Kleijn, M.Koutny, M.Pietkiewicz-Koutny and G.Rozenberg. Classifying Boolean Nets for Region-based Synthesis. CEUR Workshop Proceedings 725, pages 5-21, 2011
[26] J.Kleijn, M.Koutny and G.Rozenberg. Process Semantics for Membrane Systems. Journal of Automata, Languages and Combinatorics 11:321- 340, 2006
[27] J.Kleijn, M.Koutny and G.Rozenberg. Modelling Reaction Systems with Petri Nets. CEUR Workshop Proceedings 724, pages 36-52, 2011
[28] I.Koch, W.Reisig and F.Schreiber. Modeling in Systems Biology — The Petri Net Approach. Springer London Dordrecht Heidelberg New York, 2011
[29] S.R.Kosaraju. Decidability of Reachability in Vector Addition Systems. Proc. of STOC’82, pages 267-281, ACM, 1982
[30] M.Koutny and M.Pietkiewicz-Koutny. Synthesis of Elementary Net Systems with Context Arcs and Localities. Fundamenta Informaticae 88:307-328, 2008
[31] E.W.Mayr. An Algorithm for the General Petri Net Reachability Problem. SIAM J. Comput. 13:441-460, 1984
[32] U.Montanari and F.Rossi. Contextual Nets. Acta Informatica 32:545- 596, 1995
[33] G.Păun. Computing with Membranes. J. Comput. Syst. Sci. 61:108-143, 2000
[34] G.Păun. Membrane Computing, An Introduction. Springer-Verlag, Berlin Heidelberg New York, 2002
[35] G.Păun and G.Rozenberg. A Guide to Membrane Computing. Theoretical Computer Science 287:73-100, 2002
[36] G.Păun, G.Rozenberg and A.Salomaa. The Oxford Handbook of Membrane Computing. Oxford University Press, 2009
[37] C.A.Petri. Kommunikation mit Automaten. PhD Thesis, 1962
[38] G.Rozenberg and J.Engelfriet. Elementary Net Systems. volume 1491 of Lecture Notes in Computer Science, pages 12-121, Springer-Verlag, 1998
[39] W.Reisig and G.Rozenberg (eds.) Lectures on Petri Nets I and II. volumes 1491, 1492 of Lecture Notes in Computer Science, Springer-Verlag, 1998
[40] G.Rozenberg and R.Verraedt. Subset Languages of Petri Nets Part I: The Relationship to String Languages and Normal Forms. Theoretical Computer Science 26:301-326, 1983
[41] G.Rozenberg and R.Verraedt. Subset Languages of Petri Nets Part II: Closure Properties. Theoretical Computer Science 27:85-108, 1983
[42] M.Silva, E.Teruel and J.M.Colom. Linear Algebraic and Linear Programming Techniques for the Analysis of Place/Transition Net Systems. volume 1491 of Lecture Notes in Computer Science, pages 309-373, Springer-Verlag, 1998
Bibtex
@article{sacscuza:kleijn2011pnfbmc,
title={Petri Nets for Biologically Motivated Computing},
author={J. Kleijn and M. Koutny and G. Rozenberg},
journal={Scientific Annals of Computer Science},
volume={21},
number={2},
organization={``A.I. Cuza'' University, Iasi, Romania},
year={2011},
pages={199--225},
publisher={``A.I. Cuza'' University Press}
}