Permutation automaton

In automata theory, a permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes the set of states.^[1][2]

Formally, a deterministic finite automaton A may be defined by the tuple (S, I, δ, s₀, F) where S is the set of states of the automaton, I is the set of input symbols, δ is the transition function that takes a state s and an input symbol x to a new state δ(s,x), s₀ is the initial state of the automaton, and F is the set of accepting or final states of the automaton. A is a permutation automaton if and only if, for every two distinct states s_i and s_j in S and every input symbol x in I, δ(s_i,x) ≠ δ(s_j,x).

A formal language is p-regular (also: a pure-group language) if it is accepted by a permutation automaton. For example, the set of strings of even length forms a p-regular language: it may be accepted by a permutation automaton with two states in which every transition replaces one state by the other.

Applications

The pure-group languages were the first interesting family of regular languages for which the star height problem was proved to be computable.^[1][3]

References

1. ^ ^{a b} McNaughton, Robert (August 1967), "The Loop Complexity of Pure-Group Events", Information and Control 11 (1-2): 167–176, doi:10.1016/S0019-9958(67)90481-0 
2. ^ Thierrin, Gabriel (March 1968). "Permutation automata". Theory of Computing Systems 2 (1): 83–90. doi:10.1007/BF01691347. 
3. ^ Janusz A. Brzozowski: Open problems about regular languages, In: Ronald V. Book, editor, Formal language theory—Perspectives and open problems, pp. 23–47. Academic Press, 1980 (technical report version)