Permutation automaton
Template:Short description 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.<ref name=McNaughton1967>Template:Citation</ref><ref>Template:Cite journal</ref>
Formally, a deterministic finite automaton Template:Mvar may be defined by the tuple (Q, Σ, δ, q0, 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), q0 is the initial state of the automaton, and F is the set of accepting states (also: final states) of the automaton. Template:Mvar is a permutation automaton if and only if, for every two distinct states Template:Math and Template:Math in Q and every input symbol Template:Mvar in Σ, δ(qi,x) ≠ δ(qj,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.
ApplicationsEdit
The pure-group languages were the first interesting family of regular languages for which the star height problem was proved to be computable.<ref name=McNaughton1967 /><ref name="Brzozowski80">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)</ref>
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 <math>O(n^{2/5}(\log n)^{3/5})</math>.<ref>Template:Cite book</ref> The problem was later studied for the restriction to permutation automata. In this case, the known upper bound changes to <math>O(n^{1/2})</math>.<ref>Template:Citation</ref>