順列オートマトン
オートマトン理論において、順列オートマトン、または純粋群オートマトンとは、各入力記号が状態の集合を順列させる決定論的な有限オートマトンです。 [ 1 ] [ 2 ]
正式には、決定性有限オートマトンA はタプル ( Q , Σ, δ, q 0 , F ) で定義されます。ここで、Qはオートマトンの状態の集合、 Σ は入力シンボルの集合、 δ は状態qと入力シンボルxから新しい状態 δ( q , x )に移行する遷移関数、 q 0はオートマトンの初期状態、F はオートマトンが受け入れる状態 (または最終状態) の集合です。Aが順列オートマトンである場合、かつその場合のみ、 Qの2 つの異なる状態q iとq jおよび Σ のすべての入力シンボルxに対して、 δ( q i , x ) ≠ δ( q j , x ) が成立します。
形式言語がp-正規言語（または純粋群言語）であるとは、それが順列オートマトンによって受理される場合を言う。例えば、偶数長の文字列の集合はp-正規言語を形成する。これは、すべての遷移が一方の状態を他方の状態に置き換える2つの状態を持つ順列オートマトンによって受理される可能性がある。
応用
純粋群言語は、スターハイト問題が計算可能であることが証明された最初の興味深い正規言語族でした。[ 1 ] [ 3 ]
正規言語に関するもう一つの数学的な問題は単語分離問題である。これは、長さが最大でn –の2つの単語を与えられたとき、一方の単語を受け入れ、もう一方の単語を拒否することで、それらの単語を区別する最小の決定性有限オートマトンのサイズを求める問題である。一般的な場合の既知の上限は である。[ 4 ]この問題は後に、順列オートマトンへの制限について研究された。この場合、既知の上限は に変わる。[ 5 ]
参考文献
- ^ a bマクノートン、ロバート（1967年8月）、「純粋群イベントのループ複雑性」、情報制御、11（1-2）：167-176、doi：10.1016/S0019-9958（67）90481-0
- ^ Thierrin, Gabriel (1968年3月). 「順列オートマトン」.計算システム理論. 2 (1): 83– 90. doi : 10.1007/BF01691347 .
- ^ Janusz A. Brzozowski：正規言語に関する未解決問題、Ronald V. Book編『形式言語理論：展望と未解決問題』pp. 23–47、Academic Press、1980年（技術報告書版）
- ^ Demaine, ED ; Eisenstat, S.; Shallit, J .; Wilson, DA (2011). 「単語の分離に関する考察」.形式システムの記述的複雑性. コンピュータサイエンス講義ノート. 第6808巻. pp. 147– 157. doi : 10.1007/978-3-642-22600-7_12 . ISBN 978-3-642-22599-4。
- ^ JM Robson (1996)、「機械とグループによる単語の分離」、RAIRO – Informatique théorique et applications、30 (1): 81– 86 、2012年7月15日閲覧
 | この形式手法関連の記事はスタブです。不足している情報を追加してWikipediaに貢献してください。 |
