Analysis and Synthesis of Net Structures and Transition Graphs

• Autorzy: Czaja L. , Kudlek M.
• Języki publikacji: EN

Abstrakty

EN

We investigate relations between transition graphs and net structures. Whereas for a given net structure there always exists a reachability graph, the inverse problem to find a net structure for a given transition graph is not solvable in general. We present sufficient and necessary conditions for several classes of transition graphs such as general, pseudo-bounded, bounded and elementary transition graphs, corresponding to general and (pseudo-)bounded P/T nets or C/E nets. We also give maximal and minimal solutions within an algebraic structure of net structures. The entire investigation is formulated in the framework of multiset theory.

Słowa kluczowe

EN

net structures; transition graphs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 93, nr 1-3
• Strony: 97--110
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Czaja L.

autor

Kudlek M.

• Warsaw University Banacha 2, 02-097 Warsaw, Poland,

Bibliografia

• [1] N. Busi, G. M. Pinna: Synthesis with Inhibitor Arcs. Proc. CONCUR'97, LNCS 1243, pp. 151-165, 1997.
• [2] L. Czaja: Place/Transition Petri Net Evolution: Recording Ways, Analysis and Synthesis. FI 51, No. 1-2, pp. 43-58, 2002.
• [3] L. Czaja: Calculi of Net Structures and Sets are Similar. RAIRO-Theor. Inf. and Appl. 42, pp.271-284, 2008.
• [4] L. Czaja: Boolean Algebra of Nets, their Synthesis and Analysis. FI 85, No. 1-4, pp. 89-95, 2008.
• [5] J. Cortadella, M. Kishinevsky, L. Lavagno, A. Yakovlev: Deriving Petri Nets from State Transition Systems. IEEE Trans. Comp. 47 no. 8, pp. 859-882, 1998.
• [6] P. Darondeau: Deriving Unbounded Petri Nets from Formal Languages. IRISA, Intern. Rep. 1172, 1988.
• [7] J. Desel, W. Reisig: The Synthesis Problem of Petri Nets. AI 33, pp. 297-315, 1996.
• [8] V. Diekert, G. Rozenberg: The Book of Traces. World Scientific, 1995.
• [9] J. Esparza, M. Silva: On the Analysis and Synthesis of Free Choice Systems. Springer LNCS 483, pp. 243-286, 1991.
• [10] T. Kuzak: Sekwencyjne Zachowanie Sieci o Nieograniczonej Pojemnosci Miejsc (Sequential Behaviour of Nets with Unbounded Capacity of Places). PhD Thesis, Institute of Computer Science Foundations, Polish Academy of Sciences, 1987.
• [11] A. Mazurkiewicz: Concurrency, Modularity and Synchronization. Proc. MFCS'89, Springer LNCS 379, pp. 577-598, 1989.
• [12] A. Mazurkiewicz: Introduction to Trace Theory. In: The Book of Traces. eds. V. Diekert, G. Rozenberg, pp.3-41,World Scientific, 1995.
• [13] Meseguer, J., Montanari, U.: Petri Nets are Monoids: A New algebraic Foundation for Net Theory. Proc. LICS 88, pp. 155-164, 1988.
• [14] M. Mukund: Petri Nets and Step Transition Systems. IJFCS 34 no. 4, pp. 443-478, 1992.
• [15] M. Nielsen, G. Rozenberg, P.S. Thiagarajan: Elementary Transition Systems. TCS 96 no. 1, pp. 3-33, 1992.
• [16] M. Nielsen, G. Winskel: Trace Structures and other Models of Concurrency. In: The Book of Traces. eds. V. Diekert, G. Rozenberg, pp.271-305,World Scientific, 1995.
• [17] E. Ochmański: Recognizable Trace Languages. In: The Book of Traces. eds. V. Diekert, G. Rozenberg, pp.168-204,World Scientific, 1995.
• [18] M. Pietkiewicz-Koutny: Transition Systems of Elementary Net Systems with Inhibitor Arcs. Proc. ATPN'97, Springer LNCS 1248, pp. 310-327, 1997
• [19] M. Pietkiewicz-Koutny: Synthesising Elementary Systems with Inhibitor Arcs from Step Transition Systems. FI 50 no. 2, pp. 175-203, 2002.
• [20] W. Reisig: Petri Nets-An Introduction. EATCS Monographs 5, Springer, 1985.
• [21] R. Valk: Extension and Intension of Actions. in Concurrency and Nets, eds. K. Voss, H.J. Genrich, G. Rozenberg, pp. 575-584, Springer, 1987.