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.

Formally, a deterministic finite automaton A may be defined by the tuple (Q, Σ, δ, q₀, F), where Q is the set of states of the automaton, Σ is the set of input symbols, δ is the transition function that takes a state q and an input symbol x to a new state δ(q,x), q₀ is the initial state of the automaton, and F is the set of accepting states (also: final states) of the automaton. A is a permutation automaton if and only if, for every two distinct states q_i and q_j in Q and every input symbol x in Σ, δ(q_i,x) ≠ δ(q_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.

Another mathematical problem on regular languages is the separating words problem, which asks for the size of a smallest deterministic finite automaton that distinguishes between two given words of length at most n – by accepting one word and rejecting the other. The known upper bound in the general case is $O(n^{2/5}(\log n)^{3/5})$. The problem was later studied for the restriction to permutation automata. In this case, the known upper bound changes to $O(n^{1/2})$.