English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The article continues our study of the genus of a regular language $L$,defined as the minimal genus among all genera of all finite deterministicautomata recognizing $L$. Here we define and study two closely related tools ona directed graph: directed emulators and automatic relations. A directedemulator morphism essentially encapsulates at the graph-theoretic level anepimorphism onto the minimal deterministic automaton. An automatic relation isthe graph-theoretic version of the Myhill-Nerode relation. We show that anautomatic relation determines a directed emulator morphism and respectively, adirected emulator morphism determines an automatic relation up to isomorphism.Consider the set $S$ of all directed emulators of the underlying directed graphof the minimal deterministic automaton for $L$. We prove that the genus of $L$is $\underset{G \in S}{\min}\ g(G)$. We also consider the more restrictivenotion of directed cover and prove that the genus of $L$ is reached in theclass of directed covers of the underlying directed graph of the minimaldeterministic automaton for $L$. This stands in sharp contrast to undirectedemulators and undirected covers which we also consider. Finally we prove thatif the problem of determining the minimal genus of a directed emulator of adirected graph has a solution then the problem of determining the minimal genusof an undirected emulator of an undirected graph has a solution.

The decidability of the genus of regular languages and directed emulators