Document Open Access Logo

Synthesis of Bounded Choice-Free Petri Nets

Authors Eike Best, Raymond Devillers

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2015.128.pdf
  • Filesize: 492 kB
  • 14 pages

Document Identifiers

Author Details

Eike Best
Raymond Devillers

Cite As Get BibTex

Eike Best and Raymond Devillers. Synthesis of Bounded Choice-Free Petri Nets. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 128-141, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CONCUR.2015.128

Abstract

This paper describes a synthesis algorithm tailored to the construction of choice-free Petri nets from finite persistent transition systems. With this goal in mind, a minimised set of simplified systems of linear inequalities is distilled from a general region-theoretic approach, leading to algorithmic improvements as well as to a partial characterisation of the class of persistent transition systems that have a choice-free Petri net realisation.

Subject Classification

Keywords
  • Choice-freeness
  • labelled transition systems
  • persistence
  • Petri nets
  • system synthesis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Eric Badouel, Benoît Caillaud, and Philippe Darondeau. Distributing finite automata through Petri net synthesis. Formal Asp. Comput., 13(6):447-470, 2002. Google Scholar
  2. Eric Badouel and Philippe Darondeau. Theory of regions. In Lectures on Petri Nets I: Basic Models, LNCS Vol. 1491, pages 529-586, 1998. Google Scholar
  3. Kamila Barylska, Eike Best, Evgeny Erofeev, Łukasz Mikulski, and Marcin Piątkowski. On binary words being Petri net solvable. In Algorithms and Theories for the Analysis of Event Data (ATAED 2015), pages 1-15, 2015. Google Scholar
  4. Eike Best and Philippe Darondeau. A decomposition theorem for finite persistent transition systems. Acta Inf., 46(3):237-254, 2009. Google Scholar
  5. Eike Best and Raymond R. Devillers. Characterisation of the state spaces of live and bounded marked graph Petri nets. In 8th International Conference on Language and Automata Theory and Applications (LATA 2014), pages 161-172, 2014. Google Scholar
  6. Eike Best and Raymond R. Devillers. Synthesis of persistent systems. In 35th International Conference on Application and Theory of Petri Nets and Concurrency (ICATPN 2014), pages 111-129, 2014. Google Scholar
  7. Eike Best and Raymond R. Devillers. State space axioms for T-systems. Acta Inf., 52(2-3):133-152, 2015. Google Scholar
  8. Eike Best and Raymond R. Devillers. Synthesis and reengineering of persistent systems. Acta Inf., 52(1):35-60, 2015. Google Scholar
  9. Eike Best and Raymond R. Devillers. Synthesis of live and bounded persistent systems. Fundamenta Informaticae, 140:39-59, 2015. Google Scholar
  10. Eike Best and Uli Schlachter. Analysis of Petri nets and transition systems. In Proc. 8th Interaction and Concurrency Experience (ICE), Grenoble, 2015. Google Scholar
  11. Jordi Cortadella, Michael Kishinevsky, Alex Kondratyev, Luciano Lavagno, and Alex Yakovlev. Logic Synthesis for Asynchronous Controllers and Interfaces, volume 8 of Advanced Microelectronics. Springer, 2002. Google Scholar
  12. Stefano Crespi-Reghizzi and Dino Mandrioli. A decidability theorem for a class of vector-addition systems. Inf. Process. Lett., 3(3):78-80, 1975. Google Scholar
  13. Philippe Darondeau. Equality of languages coincides with isomorphism of reachable state graphs for bounded and persistent Petri nets. Inf. Process. Lett., 94(6):241-245, 2005. Google Scholar
  14. Paul Gastin and Nathalie Sznajder. Fair synthesis for asynchronous distributed systems. ACM Trans. Comput. Log., 14(2):9, 2013. Google Scholar
  15. Robert M. Keller. A fundamental theorem of asynchronous parallel computation. In Sagamore Computer Conference, August 20-23 1974, LNCS Vol. 24, pages 102-112, 1975. Google Scholar
  16. Leslie Lamport. Arbitration-free synchronization. Distributed Computing, 16(2-3):219-237, 2003. Google Scholar
  17. Lawrence H. Landweber and Edward L. Robertson. Properties of conflict-free and persistent Petri nets. J. ACM, 25(3):352-364, 1978. Google Scholar
  18. Tadao Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4):541-580, 1989. Google Scholar
  19. Peter J. Ramadge and W. M. Wonham. Supervisory control of a class of discrete event processes. SIAM Journal on Control and Optimization, 25(1):206-230, 1987. Google Scholar
  20. Enrique Teruel, José Manuel Colom, and Manuel Silva. Choice-free Petri nets: a model for deterministic concurrent systems with bulk services and arrivals. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 27(1):73-83, 1997. Google Scholar
  21. Harro Wimmel and Karsten Wolf. Applying CEGAR to the Petri net state equation. In 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2011), pages 224-238, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact