ラビンオートマトン
ラビンオートマトン（Rabin Automaton）は、無限長の文字列を扱う有限オートマトンの一種。その形式は formula_1 としたとき、formula_2 および formula_3 は と同様に定義される。formula_4 は遷移関数であり、formula_5 はペア formula_6 の集合で、formula_7 である。formula_8 である formula_9 の実行において、formula_10 からの一部の状態を無限回訪れる間に formula_11 からの全状態を有限回訪れるようなインデックス formula_12 があるとき、formula_9 は入力単語 formula_14 を受容する。