Non-additivity of the emulation genus
Guillaume Bonfante, Florian Deloup · HAL (Le Centre pour la Communication Scientifique Directe) · 2026
The article continues our study of the genus of a regular language L, defined as the minimal genus among all genera of all finite deterministic automata recognizing L. In a previous work, we related the computation of the genus of a regular language L to that of the minimal genus of a directed emulator of the underlying directed graph G(L) (called the directed emulation genus). It seems therefore natural to consider the possible reduction of the computation of the directed emulation genus to that of the strongly connected components of G(L). We show two main results. First, the directed emulation genus is zero if and only if the directed emulation genus of each strongly connected component is zero. Secondly, we give an example of a (necessarily nonplanar) directed graph whose directed emulation genus is strictly greater than the sum of the directed emulation genera of its strongly connected components.