ラビンオートマトン

ウィキペディア

ラビンオートマトン

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2008/01/28 04:18 UTC 版)

ラビンオートマトン（Rabin Automaton）は、無限長の文字列を扱う有限オートマトンの一種。その形式は としたとき、 および Σ は Büchi automaton と同様に定義される。 は遷移関数であり、Ω はペア の集合で、 である。 である の実行において、F_i からの一部の状態を無限回訪れる間に E_i からの全状態を有限回訪れるようなインデックス i があるとき、 は入力単語 α を受容する。