Words near each other
 ・ Permotipula ・ Permotipula borealis ・ Permotipulidae ・ Permoșeni River ・ Permsky ・ Permsky (inhabited locality) ・ Permsky District ・ Permsky Uyezd ・ Permutable prime ・ Permutation ・ Permutation (album) ・ Permutation (Bill Laswell album) ・ Permutation (disambiguation) ・ Permutation (music) ・ Permutation (policy debate) ・ Permutation automaton ・ Permutation box ・ Permutation City ・ Permutation graph ・ Permutation group ・ Permutation matrix ・ Permutation model ・ Permutation pattern ・ Permutation polynomial ・ Permutation representation (disambiguation) ・ Permutatude theory ・ Permutohedron ・ Permutotetraviridae ・ Permyak Salty Ears ・ Pern
 Dictionary Lists
 mini英和辞書
 mini和英辞書
 Webster 1913
 Latin-English
 FOLDOC
 Wikipedia English
 ウィキペディア
 翻訳と辞書　辞書検索 [ 開発暫定版 ]
 スポンサード リンク
 Permutation automaton ： ウィキペディア英語版
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 may be defined by the tuple (''Q'', Σ, δ, ''q''''0'', ''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''''0'' is the initial state of the automaton, and ''F'' is the set of accepting states (also: final states) of the automaton. is a permutation automaton if and only if, for every two distinct states and in ''Q'' and every input symbol 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 ((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 $O\left(n^\left(\log n\right)^\right)$. The problem was later studied for the restriction to permutation automata. In this case, the known upper bound changes to $O\left(n^\right)$.

ウィキペディアで「Permutation automaton」の詳細全文を読む

スポンサード リンク
 翻訳と辞書 : 翻訳のためのインターネットリソース