Document Open Access Logo

A Kleene Theorem for Higher-Dimensional Automata

Authors Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof Ziemiański

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2022.29.pdf
  • Filesize: 0.73 MB
  • 18 pages

Document Identifiers

Author Details

Uli Fahrenberg
  • EPITA Research and Development Laboratory (LRDE), Paris, France
Christian Johansen
  • NTNU Gjøvik, Norway
Georg Struth
  • University of Sheffield, UK
  • Collegium de Lyon, France
Krzysztof Ziemiański
  • University of Warsaw, Poland

Cite AsGet BibTex

Uli Fahrenberg, Christian Johansen, Georg Struth, and Krzysztof Ziemiański. A Kleene Theorem for Higher-Dimensional Automata. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CONCUR.2022.29

Abstract

We prove a Kleene theorem for higher-dimensional automata (HDAs). It states that the languages they recognise are precisely the rational subsumption-closed sets of interval pomsets. The rational operations include a gluing composition, for which we equip pomsets with interfaces. For our proof, we introduce HDAs with interfaces as presheaves over labelled precube categories and use tools inspired by algebraic topology, such as cylinders and (co)fibrations. HDAs are a general model of non-interleaving concurrency, which subsumes many other models in this field. Interval orders are used as models for concurrent or distributed systems where events extend in time. Our tools and techniques may therefore yield templates for Kleene theorems in various models and applications.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata extensions
Keywords
  • higher-dimensional automata
  • interval posets
  • Kleene theorem
  • concurrency theory
  • labelled precube categories

Metrics

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

Related Versions

References

  1. Marc Bezem, Thierry Coquand, and Simon Huber. A model of type theory in cubical sets. In Ralph Matthes and Aleksy Schubert, editors, TYPES, volume 26 of Leibniz International Proceedings in Informatics, pages 107-128. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. URL: https://doi.org/10.4230/LIPIcs.TYPES.2013.107.
  2. Paul Brunet and Damien Pous. Petri automata. Logical Methods in Computer Science, 13(3), 2017. URL: https://doi.org/10.23638/LMCS-13(3:33)2017.
  3. Christian Choffrut and Leucio Guerra. Logical definability of some rational trace languages. Mathematical Systems Theory, 28(5):397-420, 1995. URL: https://doi.org/10.1007/BF01185864.
  4. Manfred Droste. A Kleene theorem for recognizable languages over concurrency monoids. In Serge Abiteboul and Eli Shamir, editors, ICALP, volume 820 of Lecture Notes in Computer Science, pages 388-399. Springer, 1994. URL: https://doi.org/10.1007/3-540-58201-0_84.
  5. Uli Fahrenberg. Higher-Dimensional Automata from a Topological Viewpoint. PhD thesis, Aalborg University, Denmark, 2005. Google Scholar
  6. Uli Fahrenberg, Christian Johansen, Georg Struth, and Krzysztof Ziemiański. Languages of higher-dimensional automata. Mathematical Structures in Computer Science, 31(5):575-613, 2021. URL: https://doi.org/10.1017/S0960129521000293.
  7. Uli Fahrenberg, Christian Johansen, Georg Struth, and Krzysztof Ziemiański. A Kleene theorem for higher-dimensional automata. CoRR, abs/2202.03791, 2022. URL: http://arxiv.org/abs/2202.03791.
  8. Uli Fahrenberg, Christian Johansen, Georg Struth, and Krzysztof Ziemiański. Posets with interfaces as a model for concurrency. Information and Computation, 285(B):104914, 2022. URL: https://doi.org/10.1016/j.ic.2022.104914.
  9. Uli Fahrenberg and Axel Legay. Partial higher-dimensional automata. In Lawrence S. Moss and Pawel Sobocinski, editors, CALCO, volume 35 of Leibniz International Proceedings in Informatics, pages 101-115. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.CALCO.2015.101.
  10. Lisbeth Fajstrup, Eric Goubault, Emmanuel Haucourt, Samuel Mimram, and Martin Raussen. Directed Algebraic Topology and Concurrency. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-15398-8.
  11. Peter C. Fishburn. Interval Orders and Interval Graphs: A Study of Partially Ordered Sets. Wiley, 1985. Google Scholar
  12. Eric Goubault. Labelled cubical sets and asynchronous transition systems: an adjunction. In CMCIM, 2002. URL: http://www.lix.polytechnique.fr/~goubault/papers/cmcim02.ps.gz.
  13. Jan Grabowski. On partial languages. Fundamentae Informatica, 4(2):427, 1981. Google Scholar
  14. Marco Grandis. Directed algebraic topology: models of non-reversible worlds. New mathematical monographs. Cambridge University Press, 2009. Google Scholar
  15. Marco Grandis and Luca Mauri. Cubical sets and their site. Theory and Applications of Categories, 11(8):185-211, 2003. Google Scholar
  16. André Joyal, Mogens Nielsen, and Glynn Winskel. Bisimulation from open maps. Information and Computation, 127(2):164-185, 1996. Google Scholar
  17. Tobias Kappé, Paul Brunet, Bas Luttik, Alexandra Silva, and Fabio Zanasi. On series-parallel pomset languages: Rationality, context-freeness and automata. Journal of Logic and Algebraic Methods in Programming, 103:130-153, 2019. URL: https://doi.org/10.1016/j.jlamp.2018.12.001.
  18. Alexander Kurz and Jiří Rosický. Weak factorizations, fractions and homotopies. Applied Categorical Structures, 13(2):141-160, 2005. Google Scholar
  19. Kamal Lodaya and Pascal Weil. Series-parallel languages and the bounded-width property. Theoretical Computer Science, 237(1-2):347-380, 2000. URL: https://doi.org/10.1016/S0304-3975(00)00031-1.
  20. Saunders Mac Lane and Ieke Moerdijk. Sheaves in Geometry and Logic. Springer, 1992. Google Scholar
  21. Vaughan R. Pratt. Modeling concurrency with geometry. In POPL, pages 311-322, New York City, 1991. ACM Press. Google Scholar
  22. Pawel Sobocinski. Relational presheaves, change of base and weak simulation. J. Comput. Syst. Sci., 81(5):901-910, 2015. URL: https://doi.org/10.1016/j.jcss.2014.12.007.
  23. Rob J. van Glabbeek. Bisimulations for higher dimensional automata. Email message, June 1991. URL: http://theory.stanford.edu/~rvg/hda.
  24. Rob J. van Glabbeek. On the expressiveness of higher dimensional automata. Theoretical Computer Science, 356(3):265-290, 2006. Google Scholar
  25. Walter Vogler. Modular Construction and Partial Order Semantics of Petri Nets, volume 625 of Lecture Notes in Computer Science. Springer, 1992. URL: https://doi.org/10.1007/3-540-55767-9.
  26. Wiesław Zielonka. Notes on finite asynchronous automata. RAIRO - Theoretical Informatics and Applications, 21(2):99-135, 1987. URL: https://doi.org/10.1051/ita/1987210200991.
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 Imprint Privacy Contact