Variants of Higher-Dimensional Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912845761871872 |
|---|---|
| author | Bazille, Hugo Dubut, Jérémy Fahrenberg, Uli Ziemiański, Krzysztof |
| author_facet | Bazille, Hugo Dubut, Jérémy Fahrenberg, Uli Ziemiański, Krzysztof |
| contents | The theory of higher-dimensional automata (HDAs) has seen rapid progress in recent years, and first applications, notably to Petri net analysis, are starting to show. It has, however, emerged that HDAs themselves often are too strict a formalism to use and reason about. In order to solve specific problems, weaker variants of HDAs have been introduced, such as HDAs with interfaces, partial HDAs, ST-automata or even relational HDAs.
In this paper we collect definitions of these and a few other variants into a coherent whole and explore their properties and translations between them. We show that with regard to languages, the spectrum of variants collapses into two classes, languages closed under subsumption and those that are not. We also show that partial HDAs admit a Kleene theorem and that, contrary to HDAs, they are determinizable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_17537 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Variants of Higher-Dimensional Automata Bazille, Hugo Dubut, Jérémy Fahrenberg, Uli Ziemiański, Krzysztof Formal Languages and Automata Theory Logic in Computer Science The theory of higher-dimensional automata (HDAs) has seen rapid progress in recent years, and first applications, notably to Petri net analysis, are starting to show. It has, however, emerged that HDAs themselves often are too strict a formalism to use and reason about. In order to solve specific problems, weaker variants of HDAs have been introduced, such as HDAs with interfaces, partial HDAs, ST-automata or even relational HDAs. In this paper we collect definitions of these and a few other variants into a coherent whole and explore their properties and translations between them. We show that with regard to languages, the spectrum of variants collapses into two classes, languages closed under subsumption and those that are not. We also show that partial HDAs admit a Kleene theorem and that, contrary to HDAs, they are determinizable. |
| title | Variants of Higher-Dimensional Automata |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2601.17537 |