We prove that the genus of a regular language is decidable . We show that the original question isequivalent to the existence of a special kind of graph epimorphism – a directedemulator morphism — onto the underlying graph of the minimal deterministicautomaton for the regular language . We also prove that class of directedemulators of genus less than or equal to $g$ is closed under minors .
Author(s) : Guillaume Bonfante, Florian DeloupLinks : PDF - Abstract
Code :
Keywords : genus - regular - language - graph - prove -