<p>An NFA is just the data of a labelled, directed multigraph with a accepting predicate over the vertices.</p>
<p>Simplicial sets generalize directed multigraphs by allowing the existence of higher dimensional simplicies. Is there then a reasonable generalization of automaton that labels all of these higher dimensional simplicies as well?</p>
<p>If so, presume that we still label 1-simplicies with characters. What would then be a reasonable label to put on something like a 2-simplex? What would it mean to satisfy that label at parsing time?</p>

CC BY-SA 4.0
2024-04-13T15:45:18.817Z
You can sort of think of NFAs that way - multiple outgoing arrows from a given state with a given letter could be viewed as a (directed) simplex labeled with that letter. I don't know if this view is useful.
Joshua Grochow
CC BY-SA 4.0
2024-04-14T03:49:16.843Z
Related: https://arxiv.org/abs/2202.03791
Joshua Grochow
CC BY-SA 4.0
2024-04-14T20:02:46.523Z
A good place to start looking is [Eric Goubault's work](https://www.lix.polytechnique.fr/Labo/Eric.Goubault/publis.html) on algebraic methods for higher-dimensional automata, starting in the mid 1990s. There is a [book](https://link.springer.com/book/10.1007/978-3-319-15398-8) summarising  this work.
Martin Berger
<automata-theory><parsing><homotopy-type-theory><simplex>
Higher dimensional automata?
Steven Schaefer
# Higher dimensional automata?

(Asked by: username_0 on 2024-04-12)

An NFA is just the data of a labelled, directed multigraph with a accepting predicate over the vertices.

Simplicial sets generalize directed multigraphs by allowing the existence of higher dimensional simplicies. Is there then a reasonable generalization of automaton that labels all of these higher dimensional simplicies as well?

If so, presume that we still label 1-simplicies with characters. What would then be a reasonable label to put on something like a 2-simplex? What would it mean to satisfy that label at parsing time?

**Tags:** automata-theory, parsing, homotopy-type-theory, simplex
> **Comments:**
> **username_1**: You can sort of think of NFAs that way - multiple outgoing arrows from a given state with a given letter could be viewed as a (directed) simplex labeled with that letter. I don't know if this view is useful.  
> **username_1**: Related: https://arxiv.org/abs/2202.03791  
> **username_2**: A good place to start looking is [Eric Goubault's work](https://www.lix.polytechnique.fr/Labo/Eric.Goubault/publis.html) on algebraic methods for higher-dimensional automata, starting in the mid 1990s. There is a [book](https://link.springer.com/book/10.1007/978-3-319-15398-8) summarising  this work.  

---

## 0 answers

