ラビンオートマトン
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ラビンオートマトン（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 によるチュートリアル
 |
この項目「ラビンオートマトン」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。（ポータル 数学／ウィキプロジェクト 数学） |
 |
この「ラビンオートマトン」は、コンピュータに関連した書きかけです。この記事を加筆して下さる人を求めています。（Portal:コンピュータ） |
