順列オートマトン

オートマトン理論において、順列オートマトン、または純粋群オートマトンとは、各入力記号が状態の集合を順列するような決定性有限オートマトンである。 ^{[ 1 ] [ 2 ]}

形式的には、決定性有限オートマトンA はタプル ( Q、 Σ、 δ、q ₀、F ) で定義できます。ここで、Qはオートマトンの状態の集合、Σ は入力記号の集合、δ は状態qと入力記号xを新しい状態 δ( q、x )に遷移させる関数、 q ₀はオートマトンの初期状態、F はオートマトンの受理状態 (または最終状態) の集合です。A が順列オートマトンであるのは、 Q内の任意の 2 つの異なる状態q _iとq _jおよび Σ 内の任意の入力記号xに対して、δ( q _i、x ) ≠ δ( q _j、x ) が成り立つ場合のみです。

形式言語は、順列オートマトンによって受理される場合、 p-正則（または純粋群言語）である。例えば、偶数長の文字列の集合はp-正則言語を形成する。これは、すべての遷移が一方の状態を他方の状態に切り替える2つの状態を持つ順列オートマトンによって受理される可能性がある。

純粋群言語は、スター高さ問題が計算可能であることが証明された最初の興味深い正規言語のファミリーでした。^{[ 1 ] [ 3 ]}

正規言語に関するもう1つの数学的問題は、単語分離問題です。これは、長さが最大nの2つの単語を、一方の単語を受け入れ、もう一方の単語を拒否することによって区別する最小の決定性有限オートマトンのサイズを求める問題です。一般の場合の既知の上限は、${\displaystyle O(n^{2/5}(\log n)^{3/5})}$[ ^{4 ]}この問題は後に順列オートマトンへの制限について研究された。この場合、既知の上限は次のように変化する^。${\displaystyle O(n^{1/2})}$[ ^{5 ]​}