Conservative Elementary Object Systems

Issue title: Concurrency Specification and Programming (CS&P)

Article type: Research Article

Authors: Köhler-Bußmeier, Michael | Heitmann, Frank

Affiliations: University of Hamburg, Department for Informatics, Vogt-Kölln-Straße 30, D-22527 Hamburg, koehler@informatik.uni-hamburg.de

Note: [] Address for correspondence: University of Hamburg, Department for Informatics, Vogt-Kölln-Straße 30, D-22527 Hamburg

Abstract: This contribution presents decidability results for the formalism of Elementary Object Systems (EOS). Object nets are Petri nets which have Petri nets as tokens – an approach known as the nets-within-nets paradigm. In this paper we study the relationship of the reachability and the liveness problem. We prove that both problems are undecidable for EOS (even for the subclass of conservative EOS) while it is well known that both are decidable for classical p/t nets. Despite these undecidability results, boundedness can be decided for conservative EOS using a monotonicity argument similar to that for p/t nets.

Keywords: Petri nets, nets-within-nets, nets as tokens, reachability, liveness, boundedness

DOI: 10.3233/FI-2012-765

Journal: Fundamenta Informaticae, vol. 120, no. 3-4, pp. 325-339, 2012