Document Open Access Logo

A Decidable Equivalence for a Turing-Complete, Distributed Model of Computation

Authors Arnaldo Cesco , Roberto Gorrieri

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.28.pdf
  • Filesize: 0.7 MB
  • 18 pages

Document Identifiers

Author Details

Arnaldo Cesco
  • Department of Computer Science and Engineering, University of Bologna, Italy
Roberto Gorrieri
  • Department of Computer Science and Engineering, University of Bologna, Italy

Cite As Get BibTex

Arnaldo Cesco and Roberto Gorrieri. A Decidable Equivalence for a Turing-Complete, Distributed Model of Computation. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.28

Abstract

Place/Transition Petri nets with inhibitor arcs (PTI nets for short), which are a well-known Turing-complete, distributed model of computation, are equipped with a decidable, behavioral equivalence, called pti-place bisimilarity, that conservatively extends place bisimilarity defined over Place/Transition nets (without inhibitor arcs). We prove that pti-place bisimilarity is sensible, as it respects the causal semantics of PTI nets.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • Petri nets
  • Inhibitor arc
  • Behavioral equivalence
  • Bisimulation
  • Decidability

Metrics

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

Related Versions

References

  1. Tilak Agerwala. A complete model for representing the coordination of asynchronous processes. Technical report, 1974. URL: https://doi.org/10.2172/4242290.
  2. Tilak Agerwala and Mike Flynn. Comments on capabilities, limitations and “correctness” of petri nets. SIGARCH Computer Architecture News, 2(4):81–86, 1973. URL: https://doi.org/10.1145/633642.803973.
  3. Marco Ajmone, Gianfranco Balbo, Gianni Conte, Susanna Donatelli, and Giuliana Franceschinis. Modelling with generalized stochastic petri nets. SIGMETRICS Performance Evaluation Review, 26(2):2, 1998. URL: https://doi.org/10.1145/288197.581193.
  4. Cyril Autant, Z. Belmesk, and Philippe Schnoebelen. Strong bisimilarity on nets revisited. In PARLE '91 Parallel Architectures and Languages Europe, volume 506 of Lecture Notes in Computer Science, pages 295-312. Springer, 1991. URL: https://doi.org/10.1007/3-540-54152-7_71.
  5. Massimo Bartoletti, Tiziana Cimoli, and G. Michele Pinna. Lending petri nets. Science of Computer Programming, 112:75-101, 2015. URL: https://doi.org/10.1016/j.scico.2015.05.006.
  6. Eike Best, Raymond R. Devillers, Astrid Kiehn, and Lucia Pomello. Concurrent bisimulations in petri nets. Acta Informatica, 28(3):231-264, 1991. URL: https://doi.org/10.1007/BF01178506.
  7. Nadia Busi. Analysis issues in petri nets with inhibitor arcs. Theoretical Computer Science, 275(1):127-177, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00127-X.
  8. Nadia Busi and Roberto Gorrieri. Distributed semantics for the π-calculus based on petri nets with inhibitor arcs. The Journal of Logic and Algebraic Programming, 78(3):138-162, 2009. URL: https://doi.org/10.1016/j.jlap.2008.08.002.
  9. Nadia Busi and G. Michele Pinna. Process semantics for place/transition nets with inhibitor and read arcs. Fundamenta Informaticae, 40:165-197, 1999. URL: https://doi.org/10.3233/FI-1999-402304.
  10. Nadia Busi and G. Michele Pinna. Comparing truly concurrent semantics for contextual place/transition nets. Fundamenta Informaticae, 44(3):209-244, 2000. URL: https://doi.org/10.5555/2376335.2376336.
  11. Arnaldo Cesco and Roberto Gorrieri. A decidable equivalence for a turing-complete, distributed model of computation, 2021. URL: http://arxiv.org/abs/2104.14859.
  12. Javier Esparza. Decidability and complexity of Petri net problems - An introduction, volume 1491 of Lecture Notes in Computer Science, pages 374-428. Springer Berlin Heidelberg, 1998. URL: https://doi.org/10.1007/3-540-65306-6_20.
  13. Ursula Goltz and Wolfgang Reisig. The non-sequential behaviour of petri nets. Information and Control, 57(2):125-147, 1983. URL: https://doi.org/10.1016/S0019-9958(83)80040-0.
  14. Roberto Gorrieri. Team bisimilarity, and its associated modal logic, for bpp nets. Acta Informatica, 2020. URL: https://doi.org/10.1007/s00236-020-00377-4.
  15. Roberto Gorrieri. Causal semantics for BPP nets with silent moves. Fundamenta Informaticae, 180(3):179-249, 2021. URL: https://doi.org/10.3233/FI-2021-2039.
  16. Roberto Gorrieri. Place bisimilarity is decidable, indeed!, 2021. URL: http://arxiv.org/abs/2104.01392.
  17. M. Hack. Petri net languages. Technical report, MIT, 1976. URL: https://doi.org/10.5555/888947.
  18. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing,, 2(4):225-231, 1973. URL: https://doi.org/10.1137/0202019.
  19. Ryszard Janicki and Maciej Koutny. Semantics of inhibitor nets. Information and Computation, 123(1):1-16, 1995. URL: https://doi.org/10.1006/inco.1995.1153.
  20. Petr Jančar. Undecidability of bisimilarity for petri nets and some related problems. Theoretical Computer Science, 148(2):281-301, 1995. URL: https://doi.org/10.1016/0304-3975(95)00037-W.
  21. Ivan Lanese, Jorge A. Pérez, Davide Sangiorgi, and Alan Schmitt. On the expressiveness and decidability of higher-order process calculi. Information and Computation, 209(2):198-226, 2011. URL: https://doi.org/10.1016/j.ic.2010.10.001.
  22. Alessandro Liberato. A study on bisimulation equivalence and team equivalence. Master thesis (supervisor R. Gorrieri), 2019. Google Scholar
  23. Roland Meyer and Roberto Gorrieri. On the relationship between π-calculus and finite place/transition petri nets. In CONCUR 2009 - Concurrency Theory, volume 5710 of Lecture Notes in Computer Science, pages 463-480. Springer Berlin Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-04081-8_31.
  24. Robin Milner, Joachim Parrow, and David Walker. A calculus of mobile processes. Information and Computation, 100(1):1-77, 1992. URL: https://doi.org/10.1016/0890-5401(92)90008-4.
  25. Ernst R. Olderog. Nets, Terms and Formulas, volume Cambridge Tracts in Theoretical Computer Science 23. Cambridge University Press, 1991. URL: https://doi.org/10.1017/CBO9780511526589.
  26. James Lyle Peterson. Petri Net Theory and the Modeling of Systems. Prentice Hall, 1981. URL: https://doi.org/10.5555/539513.
  27. Wolfgang Reisig. Petri Nets: An Introduction. Springer-Verlag, 1985. URL: https://doi.org/10.1007/978-3-642-69968-9.
  28. Davide Sangiorgi and David Walker. The π-calculus: A Theory of Mobile Processes. Cambridge University Press, 2001. Google Scholar
  29. Rob J. van Glabbeek. Structure Preserving Bisimilarity, Supporting an Operational Petri Net Semantics of CCSP, volume 9360 of Lecture Notes in Computer Science, pages 99-130. Springer International Publishing, 2015. URL: https://doi.org/10.1007/978-3-319-23506-6_9.
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