ラビンオートマトン

ラビンオートマトン（Rabin Automaton）は、無限長の文字列を扱う有限オートマトンの一種。その形式は ${\displaystyle {\mathcal {A}}=(Q,~\Sigma ,~q_{0},~\delta ,~\Omega )}$ としたとき、${\displaystyle Q,~q_{0}}$ および ${\displaystyle \Sigma }$ は Büchi automaton と同様に定義される。${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$ は遷移関数であり、${\displaystyle \Omega }$ はペア ${\displaystyle (E_{j},~F_{j})}$ の集合で、${\displaystyle E_{j},F_{j}\subset Q}$ である。${\displaystyle \rho \in Q^{\omega }}$ である ${\displaystyle {\mathcal {A}}}$ の実行において、${\displaystyle F_{i}}$ からの一部の状態を無限回訪れる間に ${\displaystyle E_{i}}$ からの全状態を有限回訪れるようなインデックス ${\displaystyle i}$ があるとき、${\displaystyle {\mathcal {A}}}$ は入力単語 ${\displaystyle \alpha }$ を受容する。

参考文献

• Automata on Infinite Objects, Handbook of Theoretical Computer Science (Vol. B), 1991. Wolfgang Thomas による調査
• Automata on Infinite Words Paritosh K. Pandya によるチュートリアル