On Trace-Expressible Behaviour of Petri Nets

• Autorzy: Jółkowska J. , Ochmański E.
• Języki publikacji: EN

Abstrakty

EN

We propose a trace-based approach to description behaviours of concurrent systems. First, we define the independency relation induced by arbitrary transition system, forming this way an asynchronous transition system. Then we introduce the notion of traceability of transition systems and study some decision problems, related to computing independency and deciding traceability for basic classes of Petri nets. Main results: traceability is decidable for place/transition nets and undecidable in broader classes of nets - inhibitor, reset and transfer nets

Słowa kluczowe

EN

Petri net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 85, nr 1-4
• Strony: 281--295
• Opis fizyczny: bibliogr. 15 poz., wykr.

Twórcy

autor

Jółkowska J.

autor

Ochmański E.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland,

Bibliografia

• [1] T. Araki, T. Kasami: Some Decision Problems Related to the Reachability Problem for Petri Nets. Theoretical, Computer Science 3(1), 1977, 85-104.
• [2] P. Chrza˛stowski-Wachtel: Testing Undecidability of the Reachability in Petri Nets with the Help of 10th Hilbert Problem. LNCS, 1639, Springer, 1999, 268-281.
• [3] Desel, J., Reising, W.: Place/Transition Petri Nets. In [13] LNCS, 1491, Springer, 1998, 122-173.
• [4] V. Diekert, G. Rozenberg: Book of Traces, World Scientific, 1995.
• [5] C. Dufourd, A. Finkel, Ph. Schnoebelen: Reset Nets Between Decidability and Undecidability. LNCS, 1443, Springer, 1998, 103-115.
• [6] M.H.T. Hack: Decidability Questions for Petri Nets. Ph. D. Thesis, M.I.T. 1976.
• [7] R.M. Keller: Formal Verification of Parallel Programs. Communications of ACM, 19(7), 1976, 371-384.
• [8] S.R. Kosaraju: Decidability of Reachability in Vector Addition Systems. Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982, 267-281.
• [9] Y. Matiyasevich: Enumerable sets are diophantine. Soviet Math. Dokl., 11, 1970, 354-357.
• [10] E.W. Mayr: An Algorithm for the General Petri Net Reachability Problem. Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981, 238-246.
• [11] A. Mazurkiewicz: Concurrent Program Schemes and Their Interpretations. Report DAIMI-PB-78, Aarhus University, 1977.
• [12] M. Minsky: Computation: Finite and Infinite Machines. Prentice-Hall, 1967.
• [13] Reisig, W., Rozenberg, G. (eds.): Lectures on Petri Nets. LNCS, 1491, Springer, 1998.
• [14] G. Rozenberg, J. Engelfriet: Elementary Net Systems. In [13], LNCS, 1491, Springer, 1998, 12-121.
• [15] E.W. Stark: Concurrent Transition Systems. Theoretical Computer Science, 64(3), 1989, 221-269