Misplaced Pages

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 ${\displaystyle 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 ${\displaystyle O(n^{1/2})}$.

References

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.
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. Vol. 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

This formal methods-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Permutations
• Finite automata
• Formal methods stubs