ラビンオートマトン
(Rabin automaton から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2008/01/28 04:18 UTC 版)
ラビンオートマトン（Rabin Automaton）は、無限長の文字列を扱う有限オートマトンの一種。その形式は 
としたとき、
および Σ は Büchi automaton と同様に定義される。
は遷移関数であり、Ω はペア 
の集合で、
である。
である 
の実行において、Fi からの一部の状態を無限回訪れる間に Ei からの全状態を有限回訪れるようなインデックス i があるとき、 は入力単語 α を受容する。
参考文献
- Automata on Infinite Objects, Handbook of Theoretical Computer Science (Vol. B), 1991. Wolfgang Thomas による調査
- Automata on Infinite Words Paritosh K. Pandya によるチュートリアル
 |
この「ラビンオートマトン」はコンピュータに関連した書きかけ項目です。この記事を加筆して下さる協力者を求めています（PJ コンピュータ / Portal:コンピュータ）。 |
ラビンオートマトンと同じ種類の言葉
- ラビンオートマトンのページへのリンク
