I'm looking for a reference rather than an answer. I think I'm just not Googling the right combination of terms. I imagine that there is a class of graphs which is equivalent to some class of languages via some transformation (acceptance?). I'd like to know more about this, but can't seem to find much.


1 Answer 1


I guess you mean regular languages accepted by finite automata. Just Google one of these words: finite automaton, DFA, NFA, regular language or look at this question How to convert finite automata to regular expressions?

Edit. To answer your last remark, you might be interested in this paper, which heavily relies on Stone duality.

  • $\begingroup$ Yeah, that's all I can find. But I was hoping for something more general. $\endgroup$
    – ihaphleas
    May 4, 2015 at 20:40
  • $\begingroup$ @thatguy Such as what? From your question, this sounds exactly like what you had in mind. $\endgroup$
    – mrp
    May 6, 2015 at 13:43
  • $\begingroup$ @mrp That may be the only information available --- or, in fact, the only possibility. But I was hoping for more, like "What are the graph-theoretic properties of (a representation of) a DFA?" My field is topology, so, in analogy to that field, we know that Stone spaces are dual to Boolean algebras --- but we know a lot about Stone spaces (topologically), they are, for example, zero-dimensional. $\endgroup$
    – ihaphleas
    May 7, 2015 at 14:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .