# What is the class of languages accepted by DFAs whose transition monoids are transitive permutation groups?

In the Wiki page

A permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes the set of states. ..... A formal language is p-regular (also: a pure-group language) if it is accepted by a permutation automaton.

The transition monoid of an automaton is the set of all functions on the set of states induced by input strings. See the page for more details.

The transition monoid can be regarded as a monoid acting on the set of states. See this Wiki page for more details.

In many literatures, an automaton is called strongly connected when the monoid action is transitive, i.e. there is always at least one transition (input string) from one state to another state.

The transition monoid of a permutation automaton can be regarded as a permutation group acting on the set of states. If the action is transitive, then the transition monoid is a transitive permutation group.

My question is

What is the class of the languages accepted by DFAs whose transition monoids are transitive permutation groups? Is this class a proper subclass of p-regular language?

Any literatures discussing this class of languages in details?

I have searched many books and articles and found nothing helpful so far. I believe I don't have the appropriate key words yet. Thus I am seeking help. Any pointers/references will be appreciated very much.

P.S. I asked a related question on CS.SE with more technical details toward computer science.

• (Sorry, I messed up) Isn't every permutation automaton transitive? Mar 25, 2013 at 2:14
• @HendrikJan Is every permutation group transitive? Your question is part of my question. Is it a proper subclass of p-regular language? Mar 25, 2013 at 2:28
• Thanks. I will have a try. Assume we have a transition labelled $a$ from $p$ to $q$. Look at the permutation automaton as labelled graph. Follow the edges labelled $a$ from $q$, we cannot reach the same vertex twice, so we must end up in $p$ again. (The edges with a fixed label form cycles in the graph). SO, if there is an edge from $p$ to $q$ there is a path from $q$ to $p$. This makes a connected automaton also strongly connected. Isn't that what you want? Mar 25, 2013 at 9:38