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

• Autorzy: Köhler-Bußmeier M.

Identyfikatory

DOI

10.3233/FI-2014-963

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Hornets; nets within nets; object nets; reachability; safeness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 1/2
• Strony: 101--115
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Köhler-Bußmeier M.

• University of Hamburg, Department for Informatics, Vogt-Kölln-Straße 30, D-22527 Hamburg, Germany

Bibliografia

• [1] Ehrig, H., Mahr, B.: Fundamentals of algebraic Specification, EATCS Monographs on TCS, Springer-Verlag, 1985.
• [2] Esparza, J.: Decidability and Complexity of Petri Net Problems – An Introduction, Lectures on Petri Nets I: Basic Models, Advances in Petri Nets (W. Reisig, G. Rozenberg, Eds.), 1491, Springer-Verlag, 1998.
• [3] Hoffmann, K., Ehrig, H., Mossakowski, T.: High-Level Nets with Nets and Rules as Tokens, Application and Theory of Petri Nets and Other Models of Concurrency, 3536, Springer-Verlag, 2005.
• [4] Köhler, M.: Reachable Markings of Object Petri Nets, Fundamenta Informaticae, 79(3-4), 2007, 401 – 413.
• [5] Köhler, M., Rölke, H.: Concurrency for Mobile Object-Net Systems, Fundamenta Informaticae, 54(2-3), 2003.
• [6] Köhler, M., Rölke, H.: Properties of Object Petri Nets, International Conference on Application and Theory of Petri Nets 2004 (J. Cortadella, W. Reisig, Eds.), 3099, Springer-Verlag, 2004.
• [7] Köhler-Bußmeier, M.: Hornets: Nets within Nets combined with Net Algebra, International Conference on Application and Theory of Petri Nets (ICATPN’2009) (K. Wolf, G. Franceschinis, Eds.), 5606, Springer-Verlag, 2009.
• [8] Köhler-Bußmeier, M., Heitmann, F.: On the Expressiveness of Communication Channels for Object Nets, Fundamenta Informaticae, 93(1-3), 2009, 205–219.
• [9] Köhler-Bußmeier, M., Heitmann, F.: Safeness for Object Nets, Fundamenta Informaticae, 101(1-2), 2010, 29–43.
• [10] Köhler-Bußmeier,M., Heitmann, F.: Liveness of Safe Object Nets, Fundamenta Informaticae, 112(1), 2011, 73–87.
• [11] Lipton, R. J.: The reachability problem requires exponential space, Research Report 62, Dept. of Computer science, 1976.
• [12] Lomazova, I.: Nested Petri Nets for Adaptive Process Modeling, in: Pillars of Computer Science (A. Avron, N. Dershowitz, A. Rabinovich, Eds.), vol. 4800 of Lecture Notes in Computer Science, Springer-Verlag, 2008, 460–474.
• [13] Reisig, W.: Petri nets and algebraic specifications, Theoretical Computer Science, 80, 1991, 1–34.
• [14] Valk, R.: Modelling Concurrency by Task/Flow EN Systems, 3rd Workshop on Concurrency and Compositionality, number 191 in GMD-Studien, Gesellschaft für Mathematik und Datenverarbeitung, St. Augustin, Bonn, 1991.
• [15] Valk, R.: Object Petri nets: Using the nets-within-nets paradigm, Advanced Course on Petri Nets 2003 (J. Desel, W. Reisig, G. Rozenberg, Eds.), 3098, Springer-Verlag, 2003.