Higher-dimensional automata theory

Speaker(s)

Uli Fahrenberg

Affiliation

EPITA Rennes & Paris

Date

Sept. 6, 2023, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

I will give a gentle introduction to higher-dimensional automata (HDAs) and their language theory. HDAs have been introduced some 30 years ago as a model for non-interleaving concurrency which generalizes, for example, Petri nets while retaining some automata-theoretic intuition. They have been studied mostly for their operational and geometric aspects and are one of the original motivations for directed algebraic topology. In a series of papers we have recently started to work on the language theory of HDAs: we have introduced languages of HDAs as weak sets of interval pomsets with interfaces [1,2] and shown that they satisfy Kleene and Myhill-Nerode type theorems [3,4]. Further, HDAs are not generally determinisable nor complementable, but language inclusion is decidable [4,5]. The picture which emerges is that, even though things can sometimes get hairy in proofs, HDAs have a rather pleasant language theory, a fact which should be useful in the theory of non-interleaving concurrency and its applications. Joint work with Amazigh Amrane, Hugo Bazille, Christian Johansen, Georg Struth, and Krzysztof Ziemiański [1] UF, C. Johansen, G. Struth, K. Ziemiański: Languages of Higher Dimensional Automata. Math. Struct. Comput. Sci. 31(5) (2021) [2] UF, C. Johansen, G. Struth, K. Ziemiański: Posets With Interfaces As a Model for Concurrency. Inf. Comput. 285(2) (2022) [3] UF, C. Johansen, G. Struth, K. Ziemiański: A Kleene Theorem for Higher Dimensional Automata. CONCUR 2022 [4] UF, K. Ziemiański: A Myhill-Nerode Theorem for Higher-Dimensional Automata. Petri Nets 2023 [5] A. Amrane, H. Bazille, UF, K. Ziemiański: Developments in Higher-Dimensional Automata Theory. CoRR abs/2305.02873 (2023)

---