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 (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.^[1]^[3]

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})$ .^[4] The problem was later studied for the restriction to permutation automata. In this case, the known upper bound changes to $O(n^{1/2})$ .^[5]

References

^ ^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
^ Thierrin, Gabriel (March 1968). "Permutation automata". Theory of Computing Systems. 2 (1): 83–90. doi:10.1007/BF01691347.
^ 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)
^ Demaine, E. D.; Eisenstat, S.; Shallit, J.; Wilson, D. A. (2011). "Remarks on Separating Words". Descriptional Complexity of Formal Systems. Lecture Notes in Computer Science. 6808. pp. 147–157. doi:10.1007/978-3-642-22600-7_12. ISBN 978-3-642-22599-4.
^ J. M. Robson (1996), "Separating words with machines and groups", RAIRO – Informatique théorique et applications, 30 (1): 81–86, retrieved 2012-07-15

[McNaughton1967-1] 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.

[Brzozowski80-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)

[4] Demaine, E. D.; Eisenstat, S.; Shallit, J.; Wilson, D. A. (2011). "Remarks on Separating Words". Descriptional Complexity of Formal Systems. Lecture Notes in Computer Science. 6808. pp. 147–157. doi:10.1007/978-3-642-22600-7_12. ISBN 978-3-642-22599-4.

[5] J. M. Robson (1996), "Separating words with machines and groups", RAIRO – Informatique théorique et applications, 30 (1): 81–86, retrieved 2012-07-15

[1]

[2]

[3]

[4]

[5]