On the analysis of Petri nets and their synthesis from process languages

Ludwik Czaja

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2003)

  • Volume: 37, Issue: 1, page 17-38
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Czaja, Ludwik. "On the analysis of Petri nets and their synthesis from process languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 37.1 (2003): 17-38. <http://eudml.org/doc/244704>.

@article{Czaja2003,
abstract = {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.},
author = {Czaja, Ludwik},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Petri net; process language; analysis and synthesis of nets},
language = {eng},
number = {1},
pages = {17-38},
publisher = {EDP-Sciences},
title = {On the analysis of Petri nets and their synthesis from process languages},
url = {http://eudml.org/doc/244704},
volume = {37},
year = {2003},
}

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
PB - EDP-Sciences
VL - 37
IS - 1
SP - 17
EP - 38
AB - 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.
LA - eng
KW - Petri net; process language; analysis and synthesis of nets
UR - http://eudml.org/doc/244704
ER -

References

top
  1. [1] E. Best and C. Fernandez, Non-sequential Processes, A Petri Net View. Springer, Berlin, Heidelberg, New York, Tokyo, EATCS Monogr. Theoret. Comput. Sci. 13 (1988). Zbl0656.68005MR955495
  2. [2] R. Berghammer, B. Karger and C. Ulke, 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. 
  3. [3] E. Best and R. Devillers, Sequential and Concurrent Behaviour in Petri Net Theory. Theoret. Comput. Sci. 55 (1987) 87-136. Zbl0669.68043MR927275
  4. [4] N. Busi and G.M. Pinna, Synthesis with Inhibitor Arcs, in Proc. of CONCUR’97, Warsaw, Poland. Springer-Verlag, Lecture Notes in Comput. Sci. 1243 (1997) 151-165. 
  5. [5] L.A. Castelano, Beta Processes of C/E Systems, Advances in Petri Nets. Springer-Verlag, Lecture Notes in Comput. Sci. 222 (1985) 83-100. Zbl0606.68054MR864513
  6. [6] L. Czaja, Net-Definability of Process Languages. Fund. Inform. 37 (1999) 213-223. Zbl0930.68094MR1732387
  7. [7] L. Czaja, Process Languages and Nets. Theoret. Comput. Sci. 238 (2000) 161-181. Zbl0944.68093MR1760481
  8. [8] L. Czaja and M. Kudlek, 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. 
  9. [9] L. Czaja and M. Kudlek, Rational, Linear and Algebraic Process Languages and Iteration Lemmata. Fund. Inform. 43 (2000) 49-60. Zbl0965.68045MR1803262
  10. [10] L. Czaja and M. Kudlek, ω -Process Languages for Place/Transition Nets. Fund. Inform. 47 (2001) 217-229. Zbl1050.68105MR2009787
  11. [11] P. Darondeau, Deriving unbounded Petri nets from formal languages. IRISA, Internal Report No. 1172 (1998). Zbl0940.68097MR1683381
  12. [12] J. Desel and W. Reisig, 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. Zbl0926.68083
  13. [13] V. Diekert and G. Rozenberg, The Book of Traces. World Scientific, Singapore, New Jersey, London, Hong Kong (1995). MR1478992
  14. [14] J. Esparza and M. Silva, 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. MR1102690
  15. [15] U. Goltz and W. Reisig, The Non-sequential Behaviour of Petri Nets. Inform. and Comput. 57 (1983) 125-147. Zbl0551.68050MR742704
  16. [16] R. Gorrieri, Refinement, Atomicity and Transactions for Process Description Languages, Ph.D. Thesis TD-2/91. Università degli Studi di Pisa Dipartimento di Informatica (1991). 
  17. [17] W.E. Kotov, Petri Nets (in Russian). NAUKA, Moscow (1984). Zbl0606.68052MR758444
  18. [18] A. Krzywicki, Processes in Place/Transition Nets with weights (in Polish), M.Sc. Thesis. Institute of Informatics, Warsaw University (2001). 
  19. [19] T. Kuzak, 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. [20] I.A. Lomazova, 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. [21] A. Mazurkiewicz, 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. Zbl0633.68051MR902669
  22. [22] A. Mazurkiewicz, Concurrency, Modularity and Synchronization. Mathematical Foundations of Computer Science, Porabka–Kozubnik, Poland. Springer-Verlag, Lecture Notes in Comput. Sci. 379 (1989) 577-598. Zbl0755.68098
  23. [23] A. Mazurkiewicz, Introduction to Trace Theory, in [13], pp. 3-41. MR1478993
  24. [24] J. Meseguer, U. Montanari and V. Sassone, On the Semantics of Place/Transition Petri Nets. Math. Struct. Comput. Sci. 7 (1997) 359-397. Zbl0876.68072MR1460399
  25. [25] M. Nielsen and G. Winskel, Trace Structures and other Models of Concurrency, in [13], pp. 271-305. MR1479001
  26. [26] E. Ochmanski, Occurrence traces – Processes of elementary net systems, in Advances in Petri Nets 88. Springer-Verlag, Lecture Notes in Comput. Sci. 340, 331-342. Zbl0667.68073
  27. [27] E. Ochmanski, Recognizable Trace Languages, in [13], pp. 168-204. 
  28. [28] M. Pietkiewicz–Koutny, 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. [29] W. Reisig, Petri Nets. An Introduction. Springer, Berlin-Heidelberg-New York, Tokyo, EATCS Monogr. Theoret. Comput. Sci. 4 (1985). Zbl0555.68033MR782303
  30. [30] G. Rozenberg, 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. Zbl0636.68064MR902654
  31. [31] G. Rozenberg and J. Engelfriet, 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. Zbl0926.68082
  32. [32] P.H. Starke, Petri-Netze. Grundlagen, Anwendungen, Theorie. VEB Deutscher Verlag der Wissenschaften, Berlin (1980) Polish translation WNT (1987). Zbl0449.68020MR741187
  33. [33] J. Winkowski, Behaviours of Concurrent Systems. Theoret. Comput. Sci. 12 (1980) 39-60. Zbl0445.68044MR582241

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.