Presheaf automata
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918125355663360 |
|---|---|
| author | Struth, Georg Ziemiański, Krzysztof |
| author_facet | Struth, Georg Ziemiański, Krzysztof |
| contents | We introduce presheaf automata as a generalisation of different variants of higher-dimensional automata and other automata-like formalisms, including Petri nets and vector addition systems. We develop the foundations of a language theory for them based on notions of paths and track objects. We also define open maps for presheaf automata, extending the standard notions of simulation and bisimulation for transition systems. Apart from these conceptual contributions, we show that certain finite-type presheaf automata subsume all Petri nets, generalising a previous result by van Glabbeek, which applies to higher-dimensional automata and safe Petri nets. We also present a class of presheaf automata for which there is no Kleene theorem with respect to the notions of rational and regular languages introduced. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_04612 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Presheaf automata Struth, Georg Ziemiański, Krzysztof Formal Languages and Automata Theory Category Theory 18B20, 68Q45, 68Q85 F.4.3 We introduce presheaf automata as a generalisation of different variants of higher-dimensional automata and other automata-like formalisms, including Petri nets and vector addition systems. We develop the foundations of a language theory for them based on notions of paths and track objects. We also define open maps for presheaf automata, extending the standard notions of simulation and bisimulation for transition systems. Apart from these conceptual contributions, we show that certain finite-type presheaf automata subsume all Petri nets, generalising a previous result by van Glabbeek, which applies to higher-dimensional automata and safe Petri nets. We also present a class of presheaf automata for which there is no Kleene theorem with respect to the notions of rational and regular languages introduced. |
| title | Presheaf automata |
| topic | Formal Languages and Automata Theory Category Theory 18B20, 68Q45, 68Q85 F.4.3 |
| url | https://arxiv.org/abs/2409.04612 |