New answers tagged


From this question on cs.stackexchange, I became aware of the genus hierarchy of regular languages. Essentially, you can characterize regular languages based on the minimum genus surface in which the graph of their DFA may be embedded. It is shown in [1] that there exist languages of arbitrarily large genus and that this hierarchy is proper. Bonfante, ...


This might be of some relevance Survey by Aranyak Mehta (Google Research)

Top 50 recent answers are included