Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
(Sorry, I messed up) Isn't every permutation automaton transitive? – Hendrik Jan Mar 25 '13 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? – scaaahu Mar 25 '13 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? – Hendrik Jan Mar 25 '13 at 9:38

p-regular languages are commonly known as (regular) group languages in the literature since their syntactic monoid is a finite group.

If a language is accepted by a permutation automaton, then its minimal DFA is also a permutation group, but this group is transitive (since every state is accessible from the initial state). Thus your subclass is actually equal to the class of all group languages.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.