New answers tagged

2

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, ...


0

This might be of some relevance http://www.cs.cmu.edu/~arielpro/15896s15/docs/paper13b.pdf Survey by Aranyak Mehta (Google Research)


Top 50 recent answers are included