An Event Based Semantics of P Systems

Published in Volume XVIII, 2008, pages 99-127

Authors: G.M. Pinna and A. Saba

Abstract

Membrane systems have many similarities with classical concurrency models. In particular notions like parallelism, causality and concurrency seem to belong to membrane computing, though they are not yet regarded as central or cornerstone notions. Recently the interest in comparing membrane systems and other models for concurrency has grown. In this paper we propose a translation of membrane system into zero safe nets and then we show how to associate an event automaton to the 1-unfolding of these nets. Thus we propose an event based view of computations of a membrane system.

Full Text (PDF)

References

[1] Baldan, P., “Modelling concurrent computations: from contextual Petri nets to graph grammars,” Ph.D. thesis, Department of Computer Science, University of Pisa (2000), TD-1/00.

[2] Baldan, P., N. Busi, A. Corradini and G. M. Pinna, Domain and event structure semantics for Petri nets with read and inhibitor arcs, Theoretical Computer Science 323 (2004), pp. 129-189.

[3] Bottoni, P., C. Mart´ın-Vide, G. Paun and G. Rozenberg, Membrane systems with promoters/inhibitors, Acta Informatica 38 (2002), pp. 695-720.

[4] Bruni, R. and U. Montanari, Zero-safe nets: Comparing the collective and individual token approaches, Information and Computation 156 (2000), pp. 46-89.

[5] Bruni, R. and U. Montanari, Transactions and zero-safe nets, in: Unifying Petri Nets, Advances in Petri Nets, LNCS 2128 (2001), pp. 380- 426.

[6] Busi, N., Causality in membrane systems, in: Membrane Computing, 8th International Workshop, WMC 2007, LNCS 4860 (2007), pp. 160- 171.

[7] Busi, N., Using well-structured transition systems to decide divergence for catalytic p systems, Theoretical Computer Science 372 (2007), pp. 125-135.

[8] Ciobanu, G. and D. Lucanu, Events, causality, and concurrency in membrane systems, in: Membrane Computing, 8th International Workshop, WMC 2007, LNCS 4860 (2007), pp. 209-227.

[9] Kleijn, J. and M. Koutny, Processes of membrane systems with promoters and inhibitors, Theoretical Computer Science (2008), doi:10.1016/j.tcs.2008.04.006.

[10] Kleijn, J., M. Koutny and G. Rozenberg, Towards a petri net semantics for membrane systems, in: Membrane Computing, 6th International Workshop, WMC 2005, LNCS 3850 (2005), pp. 292-309.

[11] Kleijn, J., M. Koutny and G. Rozenberg, Process semantics for membrane systems, Journal of Automata, Languages and Combinatorics 11 (2006), pp. 321-340.

[12] Paun, G., Computing with membranes: An introduction, Bulletin of the EATCS 67 (1999), pp. 139-152.

[13] Paun, G., Computing with membranes, J. Comput. Syst. Sci. 61 (2000), pp. 108-143.

[14] Pinna, G. M., Event structures for the collective tokens philosophy of inhibitor nets, in: Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, LNCS 3618 (2005), pp. 720-732.

[15] Pinna, G. M., Event structures with disabling/enabling relation and event automata, Fundamenta Informaticae 73 (2006), pp. 409-430.

[16] Pinna, G. M. and A. Poign´e, On the nature of events: another perspective in concurrency, Theoretical Computer Science 138 (1995), pp. 425-454.

[17] van Glabbeek, R. J. and G. D. Plotkin, Configuration structures, in: Proceedings, Tenth Annual IEEE Symposium on Logic in Computer Science (1995), pp. 199-209.

[18] van Glabbeek, R. J. and G. D. Plotkin, Event structures for resolvable conflict., in: Mathematical Foundations of Computer Science 2004, LNCS 3153 (2004), pp. 550-561.

Bibtex

@article{sacscuza:pinna2008aebsops,
  title={An Event Based Semantics of P Systems},
  author={G.M. Pinna and A. Saba},
  journal={Scientific Annals of Computer Science},
  volume={18},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2008},
  pages={99--127},
  publisher={``A.I. Cuza'' University Press}
}