ラビンオートマトンのソースを表示

'''ラビンオートマトン'''（Rabin Automaton）は、無限長の[[文字列]]を扱う[[有限オートマトン]]の一種。その形式は <math>\mathcal{A} = (Q,~\Sigma,~q_0,~\delta,~\Omega)</math> としたとき、<math>Q,~q_0</math> および <math>\Sigma</math> は [[:en:Büchi automaton|Büchi automaton]] と同様に定義される。<math>\delta: Q \times \Sigma \rightarrow Q</math> は遷移関数であり、<math>\Omega</math> はペア <math>(E_j,~F_j)</math> の集合で、<math>E_j, F_j \subset Q</math> である。<math>\rho \in Q^\omega</math> である <math>\mathcal{A}</math> の実行において、<math>F_i</math> からの一部の状態を無限回訪れる間に <math>E_i</math> からの全状態を有限回訪れるようなインデックス <math>i</math> があるとき、<math>\mathcal{A}</math> は入力単語 <math>\alpha</math> を受容する。
<!--
==See also==
[[Streett automaton]] - A closely related automaton with the same components but a different acceptance condition.
-->
==参考文献==
*[http://portal.acm.org/citation.cfm?id=114895 Automata on Infinite Objects, Handbook of Theoretical Computer Science (Vol. B), 1991.] Wolfgang Thomas による調査
*[http://www.tcs.tifr.res.in/~pandya/grad/aut06/lect4.pdf Automata on Infinite Words] Paritosh K. Pandya によるチュートリアル



{{Computer-stub}}

{{DEFAULTSORT:らひんおおとまとん}}
[[Category:計算モデル]]
[[Category:数学に関する記事]]



[[en:Rabin automaton]]