Decidability Problems of a Basic Class of Object Nets

• Autorzy: Dietze R. , Kudlek M. , Kummer O.
• Języki publikacji: EN

Abstrakty

EN

It is shown that the boundedness problem for a certain class of basic object nets and a corresponding class of multiset rewriting systems is decidable. To achieve this result Dickson's Lemma for a certain class of multisets, and a modified Karp Miller algorithm, is applied. This presents another class of nets with different decidability behaviour for reachability and boundedness.

Słowa kluczowe

EN

object Petri-net; multiset rewriting; Dickson's lemma; Karp Miller algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 3-4
• Strony: 295--302
• Opis fizyczny: bibliogr. 11 poz.

Twórcy

autor

Dietze R.

autor

Kudlek M.

autor

Kummer O.

• Universität Hamburg Fachbereich Informatik Vogt-Kölln-Str. 30 D-22527 Hamburg, Germany,

Bibliografia

• [1] Berger, Thomas; Weispfennig, Volker : Gröbner Bases - A Computational Approach to Commutative Algebra. Springer Graduate Texts in Mathematics 141, 1993.
• [2] Dickson, Leonard Eugene : Finiteness of the Odd and Primitive Abundant Numbers with n Distinct Prime Factors. Amer. Journ. of Math. 35, pp 413-426, 1913.
• [3] Dufourd, Catherine; Finkel, Alain; Schnoebelen, Philippe : Reset Nets between Decidability and Undecidability. In Proceedings ICALP'98. Eds.: Kim G. Larsen, Sven Skyum, Glynn Winskel, LNCS 1443, pp 103-115, Springer, 1998.
• [4] Dufourd, Catherine; Jančar, Petr; Schnoebelen, Philippe : Boundedness of Reset P/T Nets. In Proceedings ICALP'99. Eds.: JiˇríWiedermann, Peter van Emde Boas,MogensNielsen, LNCS 1644, pp301-310, Springer, 1999.
• [5] Jessen, Eike; Valk, Rüdiger : Rechensysteme : Grundlagen der Modellbildung. Studienreihe Informatik, Springer, 1987.
• [6] Karp, Richard M.; Miller, Raymond E. : Parallel Program Schemata. JCSS 3, No. 2, pp 147-195, 1969.
• [7] Köhler, Michael : Objektnetze : Definition und Eigenschaften. Agent Technology - Theory and Application 1, Logos-Verlag, 2004.
• [8] Kummer, Olaf : Undecidability in Object-Oriented Petri Nets. Petri Net Newsletter 59, pp 18-23, 2000.
• [9] Kummer, Olaf : Referenznetze. Logos-Verlag, 2002.
• [10] Valk, Rüdiger : Modelling of Task Flow in Systems of Functional Units. FBI-Bericht 124/87, 1987.
• [11] Valk, Rüdiger : Petri Nets as Token Objects - An Introduction to Elementary Object Nets. In Proceedings of ICATPN'98. Eds.: Jörg Desel, Manuel Silva, LNCS 1420, pp 1-25, 1998.