nLab higher-dimensional automaton

Idea

In automata theory, a higher-dimensional automaton, or HDA, is a model of concurrency, where points correspond to states, edges to transitions, and squares, cubes, etc., to concurrently executing events. HDAs are defined as presheaves over a category of labelled pre-cubical sets equipped with sets of initial and accepting cells.

References

• Vaughan Pratt, Higher Dimensional Automata Revisited [pdf]

• Rob van Glabbeek, On the Expressiveness of Higher Dimensional Automata [pdf]

• Uli Fahrenberg, A Category of Higher-Dimensional Automata [pdf]

• Uli Fahrenberg, Developments in Higher-Dimensional Automata Theory [pdf]

On HDA languages and automata theory

• Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof Ziemiański, Languages of Higher-Dimensional Automata [arXiv:2103.07557]

• Uli Fahrenberg and Krzysztof Ziemiański, Myhill-Nerode Theorem for Higher-Dimensional Automata [arXiv:2210.08298]

On the relationship between Petri nets and HDAs

• Amazigh Amrane, Hugo Bazille, Uli Fahrenberg, Loïc Hélouët, Philipp Schlehuber-Caissier, Petri Nets and Higher-Dimensional Automata [arXiv:2502.02354]

On weak equivalences

• Thomas Kahl, Weak Equivalence of Higher-Dimensional Automata [arXiv:1910.12787]