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?
Asked By : Cornelius Brand
Answered By : J.-E. Pin
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
J.-É. Pin, On the languages accepted by finite reversible automata, in 14th ICALP, Berlin, (1987), 237-249, LNCS 267, Springer Verlag
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13759
0 comments:
Post a Comment
Let us know your responses and feedback