On the Complexity of the Reachability Problem for Safe, Elementary Hornets
Michael Köhler-Bußmeier · Fundamenta Informaticae · 2014
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.