# Results on the languages recognized by undirected DFAs

For my Bachelor's thesis, I consider the class of languages recognized by symmetrical DFAs, that is, deterministic (complete) finite automata satisfying the following condition:

Let $A$ be a complete DFA over the alphabet $\Sigma$. If, for every $a\in \Sigma$ and every transition $u \stackrel{a}{\longrightarrow}v$ in $A$, there is a transition $v \stackrel{a}{\longrightarrow}u$ in $A$, we call $A$ a symmetrical DFA (SDFA). If $A$ is not complete, we call it a partial SDFA. We can regard an SDFA as an undirected, labeled graph in a natural way.

I could find an algebraic characterization of the class of languages recognized by (complete as well as partial) SDFAs and deduce some closure properties. However, neither me nor my supervisor are aware of previous results concerning this particular class of regular languages (barring results like Reingold's $\mathsf{SL = L}$ which might seem related).

Motivated by a comment that J.-E. Pin passed on a related question I asked, my question is now:

Are there results concerning these automata?

• Are you aware of an equivalent class of grammars? – Raphael Aug 15 '13 at 11:05
• @Raphael No, unfortunately not. As stated in the question, I am not aware of any results on the (specific) topic (there seem to be none. Too trivial?). – Cornelius Brand Aug 15 '13 at 11:08

I can only give a partial answer. Let $\mathcal{S}$ be the class of all regular languages recognized by a complete SDFA. Then $\mathcal{S}$ is a subclass of the class $\mathcal{G}$ of group languages. A group language is a language whose syntactic monoid is a finite group , or equivalently, recognized by a finite permutation automaton (each letter induces a permutation on the set of states). The inclusion $\mathcal{S} \subset \mathcal{G}$ is strict. However, the following result holds, showing that $\mathcal{S}$ is a kind of generator for $\mathcal{G}$:
For every group language $L \subseteq A^*$, there is an alphabet $B$, a monoid morphism $f: A^* \to B^*$ and a language $K \subseteq B^*$ in $\mathcal{S}$ such that $L = f^{-1}(K)$.
Proof. Let $\mathcal{A} = (\{1, ..., n\}, A, \cdot, 1, F)$ be a permutation automaton recognizing $L$. It is a well-known fact that the group of all permutations on $\{1, ..., n\}$ is generated by the set $B$ of its transpositions (a transposition permutes two states and fixes all the other states). By construction, the automaton $\mathcal{B} = (\{1, ..., n\}, B, \cdot, 1, F)$ is a SDFA and hence recognizes a language $K$ of $\mathcal{S}$. Now, for each letter $a \in A$, there is a word $u_a \in B^*$ which defines in $\mathcal{B}$ the same permutation as $a$ in $\mathcal{A}$. Let $f: A^* \to B^*$ be the morphism defined by $f(a) = u_a$ for each letter $a \in A$. It should now be clear that $f^{-1}(K) = L$.
The class $\mathcal{PS}$ of languages recognized by a partial SDFA is of course larger than $\mathcal{S}$, but does not exhaust the class of all regular languages. Actually, one can show that if $L$ is in $\mathcal{PS}$, then the syntactic monoid of $L$ is an inverse monoid and in particular, its idempotents commute. This latter property is shared by the slightly larger class of reversible automata. See
• I was aware of $\mathcal{S}\subsetneq \mathcal{G}$. The result involving morphisms is new to me however, as well as what you say about $\mathcal{PS}$. Do you have "citable" references for these two statements (I have not - yet - tried to prove them)? – Cornelius Brand Aug 15 '13 at 14:41