2013 | OriginalPaper | Buchkapitel
Complexity Results for Elementary Hornets
verfasst von : Michael Köhler-Bußmeier, Frank Heitmann
Erschienen in: Application and Theory of Petri Nets and Concurrency
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.
We have shown previously that the reachability problem for this class requires at least exponential space, which is a major increase when compared to safe, elementary object nets, which require polynomial space.
Here, we show how a safe, elementary
Hornets
can be simulated by a safe
Eos
, which establishes an upper bound for the complexity, since we know that that the reachability problem for safe
Eos
is PSpace-complete.