Permutation automaton
{{Short description|Finite-state machine in automata theory}}
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.{{Citation
| title = The loop complexity of pure-group events
|date=August 1967
| author = McNaughton, Robert
| journal = Information and Control
| pages = 167–176
| volume = 11
| issue = 1-2
| doi=10.1016/S0019-9958(67)90481-0
| doi-access = free
Formally, a deterministic finite automaton {{mvar|A}} 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. {{mvar|A}} is a permutation automaton if and only if, for every two distinct states {{math|qi}} and {{math|qj}} in Q and every input symbol {{mvar|x}} 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.
Applications
The pure-group languages were the first interesting family of regular languages for which the star height problem was proved to be computable.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 [https://www.cs.uwaterloo.ca/research/tr/1980/CS-80-03.pdf (technical report version)]
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 .{{Cite book | last1 = Demaine | first1 = E. D.| author-link1 = Erik Demaine| last2 = Eisenstat | first2 = S. | last3 = Shallit | first3 = J.| author-link3 = Jeffrey Shallit| last4 = Wilson | first4 = D. A.| chapter = Remarks on Separating Words | doi = 10.1007/978-3-642-22600-7_12 | title = Descriptional Complexity of Formal Systems| series = Lecture Notes in Computer Science | volume = 6808 | pages = 147–157| year = 2011 | isbn = 978-3-642-22599-4 }} The problem was later studied for the restriction to permutation automata. In this case, the known upper bound changes to .{{Citation
| author = J. M. Robson
| title = Separating words with machines and groups
| url = http://www.numdam.org/item?id=ITA_1996__30_1_81_0
| year = 1996
| journal = RAIRO – Informatique théorique et applications
| pages = 81–86
| volume = 30
| issue = 1
| access-date = 2012-07-15
}}