Liveness of Safe Object Nets

• Autorzy: Köhler-Bußmeier M. , Heitmann F.
• Języki publikacji: EN

Abstrakty

EN

In this paper we study the complexity of the liveness problem for safe Elementary Object Nets (EOS). Object nets are Petri nets which have Petri nets as tokens. They are called elementary if the net system has a two levelled structure. The concept of safeness bounds the number of tokens which may reside on a place. PSPACE-hardness of the liveness problemfor safe EOS directly follows fromthe related result for safe p/t nets. We then devise a polynomial space algorithmfor this problem and indeed for every property that can be expressed in the temporal logic CTL.

Słowa kluczowe

EN

Elementary Object Systems; liveness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 112, nr 1
• Strony: 73--87
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Köhler-Bußmeier M.

autor

Heitmann F.

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

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] 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] Haddad, S., Poitrenaud, D.: Theoretical Aspects of Recursive Petri Nets, Application and Theory of Petri Nets (S. Donatelli, J. Kleijn, Eds.), 1639, Springer-Verlag, 1999.
• [4] 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.
• [5] Jones, N. D., Landweber, L. H., Lien, Y. E.: Complexity of Some Problems in Petri Nets, Theoretical Computer Science, 4, 1977, 277-299.
• [6] Köhler, M.: Reachable Markings of Object Petri Nets, Fundamenta Informaticae, 79(3-4), 2007, 401 - 413.
• [7] Köhler, M., Moldt, D., Rölke, H.: Modelling Mobility and Mobile Agents using Nets within Nets, Application and Theory of Petri Nets (W. v. d. Aalst, E. Best, Eds.), 2679, Springer-Verlag, 2003.
• [8] Köhler, M., Rölke, H.: Properties of Object Petri Nets, Application and Theory of Petri Nets (J. Cortadella, W. Reisig, Eds.), 3099, Springer-Verlag, 2004.
• [9] Köhler-Bußmeier, M.: Decidability Results for Elementary Object Systems, Technical report, Universität Hamburg, Fachbereich Informatik, 2011.
• [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] Kummer, O.: Undecidability in Object-Oriented Petri Nets, Petri Net Newsletter, 59, 2000, 18-23.
• [13] Lomazova, I. A.: Nested Petri Nets - a Formalism for Specification of Multi-agent distributed systems, Fundamenta Informaticae, 43(1-4), 2000, 195-214.
• [14] 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.
• [15] Reisig, W., Rozenberg, G., Eds.: Lectures on Petri Nets I: Basic Models, vol. 1491 of Lecture Notes in Computer Science, Springer-Verlag, 1998.
• [16] Savitch,W.: Relationship between nondeterministic and deterministic tape complexities, J. on Computer and System Sciences, 4, 1970, 177-192.
• [17] 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.
• [18] Velardo, F. R., de Frutos-Escrig, D.: Name Creation vs. Replication in Petri Net Systems, Fundamenta Informaticae, 88(3), 2008, 329-356.