On the Complexity of the Reachability Problem for Safe, Elementary Hornets

Issue title: Dedicated to the Memory of Professor Manfred Kudlek

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: In this paper we study the complexity of HORNETS, an algebraic extension of object nets. We define a restricted class: safe, elementary HORNETS, to guarantee finite state spaces. It will turn out, that the reachability problem for this class requires exponential space, which is a major increase when compared to safe, elementary object nets, which require polynomial space.

Keywords: Hornets, nets-within-nets, object nets, reachability, safeness

DOI: 10.3233/FI-2014-963

Journal: Fundamenta Informaticae, vol. 129, no. 1-2, pp. 101-115, 2014