A Survey of Decidability Results for Elementary Object Systems

Issue title: Logics, Agents, and Mobility. Extended Papers from the International Workshops LAM'10 and LAM'11

Article type: Research Article

Authors: Köhler-Bußmeier, Michael

Affiliations: University of Hamburg, Department for Informatics, Vogt-Kölln-Straße 30, D-22527 Hamburg, Germany. [email protected]

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

Abstract: This contribution presents recent results on 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 work we study the relationship of EOS to existing Petri net formalisms. It turns out that EOS are equivalent to counter programs. But even for the restricted subclass of conservative EOS reachability and liveness are undecidable problems. On the other hand for other properties like boundedness are still decidable for conservative EOS. We also study the sub-class of generalised state machines, which is worth mentioning since it combines decidability of many theoretically interesting properties with a quite rich practical modelling expressiveness.

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

DOI: 10.3233/FI-2014-983

Journal: Fundamenta Informaticae, vol. 130, no. 1, pp. 99-123, 2014