An Upper Bound for the Reachability Problem of Safe, Elementary Hornets

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

Identyfikatory

DOI

10.3233/FI-2016-1305

• Języki publikacji: EN

Abstrakty

EN

In this paper we study the complexity of the reachability problem HORNETS, an algebraic extension of object nets. Here we consider the restricted class of safe, elementary HORNETS. In previouswork we established the lower bound, i.e. reachability requires at least exponential space. In another work we have shown we can simulate elementary HORNETS with elementary object nets EOS, where reachability is known to be PSpace-complete. Since this simulation leads to a double exponential increase in the size of the simulating EOS, we obtain that for HORNETS the reachability problem is solvable in double exponential space. In this contributionwe show that this kind of simulation is rather bad, since we show that exponential space is sufficient. Together with the known lower bound this shows that the upper is tight.

Słowa kluczowe

EN

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

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 143, nr 1/2
• Strony: 89--100
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Köhler-Bußmeier M.

• University of Applied Science Hamburg, Germany
• University of Hamburg, Germany

autor

Heitmann F.

• University of Hamburg, Germany

Bibliografia

• [1] Bednarczyk,M. A., Bernardinello, L., Pawlowski,W., Pomello, L.: Modelling mobility with Petri hypernets, Recent Trends in Algebraic Development Techniques (WADT 2004) (J. L. Fiadeiro, P. D. Mosses, F. Orejas, Eds.), 3423, Springer-Verlag, 2004.
• [2] Cardelli, L., Gordon, A. D., Ghelli, G.: Mobility types for mobile ambients, Proceedings of the Conference on Automata, Languages, and Programming (ICALP’99), 1644, Springer-Verlag, 1999.
• [3] Ehrig, H., Mahr, B.: Fundamentals of algebraic Specification, EATCS Monographs on TCS, Springer-Verlag, 1985.
• [4] Hiraishi, K.: PN2: An Elementary Model for Design and Analysis of Multi-agent Systems, Coordination Models and Languages, COORDINATION 2002 (F. Arbab, C. L. Talcott, Eds.), 2315, Springer-Verlag, 2002.
• [5] 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.
• [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.: On the Complexity of the Reachability Problem for Safe, Elementary Hornets, Fundamenta Informaticae, 129, 2014, 101–116, Dedicated to the Memory of Professor Manfred Kudlek.
• [9] Köhler-Bußmeier, M.: A Survey on Decidability Results for Elementary Object Systems, Fundamenta Informaticae, 130(1), 2014, 99–123.
• [10] Köhler-Bußmeier, M., Heitmann, F.: On the Expressiveness of Communication Channels for Object Nets, Fundamenta Informaticae, 93(1-3), 2009, 205–219.
• [11] Köhler-Bußmeier, M., Heitmann, F.: Safeness for Object Nets, Fundamenta Informaticae, 101(1-2), 2010, 29–43.
• [12] Köhler-Bußmeier,M., Heitmann, F.: Liveness of Safe Object Nets, Fundamenta Informaticae, 112(1), 2011, 73–87.
• [13] Köhler-Bußmeier,M., Heitmann, F.: Complexity Results for Elementary Hornets, PETRI NETS 2013 (J.-M. Colom, J. Desel, Eds.), 7927, Springer-Verlag, 2013.
• [14] Kummer, O.: Referenznetze, Logos Verlag, 2002.
• [15] Lakos, C.: A Petri Net View ofMobility, Formal Techniques for Networked and Distributed Systems (FORTE 2005), 3731, Springer-Verlag, 2005.
• [16] Lipton, R. J.: The reachability problem requires exponential space, Research Report 62, Dept. of Computer science, 1976.
• [17] 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.
• [18] Lomazova, I. A.: Nested Petri Nets – a Formalism for Specification of Multi-agent distributed systems, Fundamenta Informaticae, 43(1-4), 2000, 195–214.
• [19] Lomazova, I. A., van Hee, K. M., Oanea, O., Serebrenik, A., Sidorova, N., Voorhoeve, M.: Nested Nets for Adaptive Systems, Application and Theory of Petri Nets and Other Models of Concurrency, Lecture Notes in Computer Science, Springer-Verlag, 2006.
• [20] Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes, parts 1-2, Information and Computation, 100(1), 1992, 1–77.
• [21] Reisig, W.: Petri nets and algebraic specifications, Theoretical Computer Science, 80, 1991, 1–34.
• [22] 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.
• [23] Xu, D., Deng, Y.: Modeling Mobile Agent Systems with High Level Petri Nets, IEEE International Conference on Systems, Man, and Cybernetics’2000, 2000.