9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ (Sorry, I messed up) Isn't every permutation automaton transitive? $\endgroup$ – Hendrik Jan Mar 25 '13 at 2:14
  • $\begingroup$ @HendrikJan Is every permutation group transitive? Your question is part of my question. Is it a proper subclass of p-regular language? $\endgroup$ – scaaahu Mar 25 '13 at 2:28
  • $\begingroup$ 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? $\endgroup$ – Hendrik Jan Mar 25 '13 at 9:38
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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