Processes in Place/Transition (P/T) nets are defined inductively by a peculiar numbering of place occurrences. Along with an associative sequential composition called catenation and a neutral process, a monoid of processes is obtained. The power algebra of this monoid contains all process languages with appropriate operations on them. Hence the problems of analysis and synthesis, analogous to those in the formal languages and automata theory, arise. Here, the analysis problem is: for a given P/T net with an initial marking find the set of all processes the net may evoke. The synthesis problem is: given a process language L decide if there exists a marked net whose evolutions (represented by processes) are collected in L and, in the positive case, find such net and its initial marking. The problems are posed and given a general solution.
Classification : 68Q85
Mots clés : Petri net, process language, analysis and synthesis of nets
@article{ITA_2003__37_1_17_0, author = {Czaja, Ludwik}, title = {On the analysis of {Petri} nets and their synthesis from process languages}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {17--38}, publisher = {EDP-Sciences}, volume = {37}, number = {1}, year = {2003}, doi = {10.1051/ita:2003006}, zbl = {1090.68072}, mrnumber = {1991749}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2003006/} }
TY - JOUR AU - Czaja, Ludwik TI - On the analysis of Petri nets and their synthesis from process languages JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2003 DA - 2003/// SP - 17 EP - 38 VL - 37 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2003006/ UR - https://zbmath.org/?q=an%3A1090.68072 UR - https://www.ams.org/mathscinet-getitem?mr=1991749 UR - https://doi.org/10.1051/ita:2003006 DO - 10.1051/ita:2003006 LA - en ID - ITA_2003__37_1_17_0 ER -
Czaja, Ludwik. On the analysis of Petri nets and their synthesis from process languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 1, pp. 17-38. doi : 10.1051/ita:2003006. http://www.numdam.org/articles/10.1051/ita:2003006/
[1] Non-sequential Processes, A Petri Net View. Springer, Berlin, Heidelberg, New York, Tokyo, EATCS Monogr. Theoret. Comput. Sci. 13 (1988). | MR 955495 | Zbl 0656.68005
and ,[2] Relation-Algebraic Analysis of Petri Nets with RELVIEW, in Tools and Algorithms for the Construction and Analysis of Systems, Second Int. Workshop, TACAS'96, Passau, Germany. Springer-Verlag, Lecture Notes in Comput. Sci. 1055 (1996) 49-69.
, and ,[3] Sequential and Concurrent Behaviour in Petri Net Theory. Theoret. Comput. Sci. 55 (1987) 87-136. | MR 927275 | Zbl 0669.68043
and ,[4] Synthesis with Inhibitor Arcs, in Proc. of CONCUR'97, Warsaw, Poland. Springer-Verlag, Lecture Notes in Comput. Sci. 1243 (1997) 151-165.
and ,[5] Beta Processes of C/E Systems, Advances in Petri Nets. Springer-Verlag, Lecture Notes in Comput. Sci. 222 (1985) 83-100. | MR 864513 | Zbl 0606.68054
,[6] Net-Definability of Process Languages. Fund. Inform. 37 (1999) 213-223. | MR 1732387 | Zbl 0930.68094
,[7] Process Languages and Nets. Theoret. Comput. Sci. 238 (2000) 161-181. | MR 1760481 | Zbl 0944.68093
,[8] Lematy Iteracyjne dla Rownosciowo Definiowalnych Jezykow Procesow (in Polish), in Proc. of symposium Theoretical Informatics, Methods of Analysis of Incomplete and Distributed Information. Technical University Bialystok (1999) 8-23.
and ,[9] Rational, Linear and Algebraic Process Languages and Iteration Lemmata. Fund. Inform. 43 (2000) 49-60. | MR 1803262 | Zbl 0965.68045
and ,[10] -Process Languages for Place/Transition Nets. Fund. Inform. 47 (2001) 217-229. | MR 2009787 | Zbl 1050.68105
and ,[11] Deriving unbounded Petri nets from formal languages. IRISA, Internal Report No. 1172 (1998). | MR 1683381 | Zbl 0940.68097
,[12] Place/Transition Petri Nets, in Lecture Notes on Petri Nets 1: Basic Models, edited by R.W. Rozenberg. Springer-Verlag, Lecture Notes in Comput. Sci. 1491 (1998) 122-173. | Zbl 0926.68083
and ,[13] The Book of Traces. World Scientific, Singapore, New Jersey, London, Hong Kong (1995). | MR 1478992
and ,[14] On the Analysis and Synthesis of Free Choice Systems, in Advances in Petri Nets 1990. Springer-Verlag, Lecture Notes in Comput. Sci. 483 (1991) 243-286. | MR 1102690
and ,[15] The Non-sequential Behaviour of Petri Nets. Inform. and Comput. 57 (1983) 125-147. | MR 742704 | Zbl 0551.68050
and ,[16] Refinement, Atomicity and Transactions for Process Description Languages, Ph.D. Thesis TD-2/91. Università degli Studi di Pisa Dipartimento di Informatica (1991).
,[17] Petri Nets (in Russian). NAUKA, Moscow (1984). | MR 758444 | Zbl 0606.68052
,[18] Processes in Place/Transition Nets with weights (in Polish), M.Sc. Thesis. Institute of Informatics, Warsaw University (2001).
,[19] Sequential Behaviour of Nets with Unbounded Capacity of Places (in Polish), Ph.D. Thesis. Institute of Computer Science Foundations, Polish Academy of Sciences (1987).
,[20] On Occurrence Net Semantics for Petri Nets with Contacts, in Proc. of Fundamentals of Computation Theory, 11th International Symposium, FCT'97, Krakow, Poland. Springer-Verlag, Lecture Notes in Comput. Sci. 1279 (1997) 317-328.
,[21] Trace theory, edited by W. Brauer et al., Petri Nets, Applications and Relationship to other Models of Concurrency. Springer, Berlin-Heidelberg-New York, Lecture Notes in Comput. Sci. 255 (1987) 279-324. | MR 902669 | Zbl 0633.68051
,[22] Concurrency, Modularity and Synchronization. Mathematical Foundations of Computer Science, Porabka-Kozubnik, Poland. Springer-Verlag, Lecture Notes in Comput. Sci. 379 (1989) 577-598. | Zbl 0755.68098
,[23] Introduction to Trace Theory, in [13], pp. 3-41. | MR 1478993
,[24] On the Semantics of Place/Transition Petri Nets. Math. Struct. Comput. Sci. 7 (1997) 359-397. | MR 1460399 | Zbl 0876.68072
, and ,[25] Trace Structures and other Models of Concurrency, in [13], pp. 271-305. | MR 1479001
and ,[26] Occurrence traces - Processes of elementary net systems, in Advances in Petri Nets 88. Springer-Verlag, Lecture Notes in Comput. Sci. 340, 331-342. | Zbl 0667.68073
,[27] Recognizable Trace Languages, in [13], pp. 168-204.
,[28] Transition Systems of Elementary Net Systems with Inhibitor Arcs, in 18th International Conference on Application and Theory of Petri Nets, Toulouse, France. Springer-Verlag, Lecture Notes in Comput. Sci. 1248 (1997) 310-327.
,[29] Petri Nets. An Introduction. Springer, Berlin-Heidelberg-New York, Tokyo, EATCS Monogr. Theoret. Comput. Sci. 4 (1985). | MR 782303 | Zbl 0555.68033
,[30] Behaviour of elementary net systems, edited by W. Brauer, Petri nets: Central models and their properties; advances in Petri nets; proceedings of an advanced course, Bad Honef. Springer-Verlag, Lecture Notes in Comput. Sci. 254 (1986) 8-19. | MR 902654 | Zbl 0636.68064
,[31] Elementary Net Systems, in Lectures on Petri Nets 1: Basic Models, edited by W. Reisig and G. Rozenberg. Springer-Verlag, Lecture Notes in Comput. Sci. 1491 (1998) 12-121. | Zbl 0926.68082
and ,[32] Petri-Netze. Grundlagen, Anwendungen, Theorie. VEB Deutscher Verlag der Wissenschaften, Berlin (1980) Polish translation WNT (1987). | MR 741187 | Zbl 0449.68020
,[33] Behaviours of Concurrent Systems. Theoret. Comput. Sci. 12 (1980) 39-60. | MR 582241 | Zbl 0445.68044
,Cité par Sources :