Kleene Theorem for Higher-Dimensional Automata
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917870500315136 |
|---|---|
| author | Fahrenberg, Uli Johansen, Christian Struth, Georg Ziemiański, Krzysztof |
| author_facet | Fahrenberg, Uli Johansen, Christian Struth, Georg Ziemiański, Krzysztof |
| contents | We prove a Kleene theorem for higher-dimensional automata. It states that the languages they recognise are precisely the rational subsumption-closed sets of finite interval pomsets. The rational operations on these languages include a gluing composition, for which we equip pomsets with interfaces. For our proof, we introduce higher-dimensional automata with interfaces, which are modelled as presheaves over labelled precube categories, and develop tools and techniques inspired by algebraic topology, such as cylinders and (co)fibrations. Higher-dimensional automata form a general model of non-interleaving concurrency, which subsumes many other approaches. Interval orders are used as models for concurrent and distributed systems where events extend in time. Our tools and techniques may therefore yield templates for Kleene theorems in various models and applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_03791 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Kleene Theorem for Higher-Dimensional Automata Fahrenberg, Uli Johansen, Christian Struth, Georg Ziemiański, Krzysztof Formal Languages and Automata Theory Algebraic Topology We prove a Kleene theorem for higher-dimensional automata. It states that the languages they recognise are precisely the rational subsumption-closed sets of finite interval pomsets. The rational operations on these languages include a gluing composition, for which we equip pomsets with interfaces. For our proof, we introduce higher-dimensional automata with interfaces, which are modelled as presheaves over labelled precube categories, and develop tools and techniques inspired by algebraic topology, such as cylinders and (co)fibrations. Higher-dimensional automata form a general model of non-interleaving concurrency, which subsumes many other approaches. Interval orders are used as models for concurrent and distributed systems where events extend in time. Our tools and techniques may therefore yield templates for Kleene theorems in various models and applications. |
| title | Kleene Theorem for Higher-Dimensional Automata |
| topic | Formal Languages and Automata Theory Algebraic Topology |
| url | https://arxiv.org/abs/2202.03791 |