Decidability Problems of a Basic Class of Object Nets

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

Article type: Research Article

Authors: Dietze, Roxana | Kudlek, Manfred | Kummer, Olaf

Affiliations: Department Informatik, MIN-Fakultät, Universität Hamburg Vogt-Kölln-Str. 30, D-22527 Hamburg, Germany. E-mail: {dietze,kudlek,kummer}@informatik.uni-hamburg.de

Abstract: It is shown that the boundedness problem for a certain class of basic object nets and a corresponding class of multiset rewriting systems is decidable. To achieve this result Dickson's Lemma for a certain class of multisets, and a modified Karp Miller algorithm, is applied. This presents another class of nets with different decidability behaviour for reachability and boundedness.

Keywords: Object Petri nets, multiset rewriting, Dickson's lemma, Karp Miller algorithm

Journal: Fundamenta Informaticae, vol. 79, no. 3-4, pp. 295-302, 2007