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?

  • $\begingroup$ 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. $\endgroup$ Apr 13 at 15:45
  • 1
    $\begingroup$ Related: arxiv.org/abs/2202.03791 $\endgroup$ Apr 14 at 3:49
  • $\begingroup$ A good place to start looking is Eric Goubault's work on algebraic methods for higher-dimensional automata, starting in the mid 1990s. There is a book summarising this work. $\endgroup$ Apr 14 at 20:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.