Semi-deterministic Büchi automaton とは

オートマトン理論では、半決定的なBüchiオートマトンは、Büchiオートマトンの特別なタイプです。このようなオートマトンでは、状態を2つのパーティションに分割して、1つの部分が決定論的オートマトンを形成し、この部分もすべての受容状態を含むようにすることができる。
すべてのBüchiオートマトンについて、半決定性のBüchiオートマトンを構築して、両方が同じω言語を認識できるようにすることができます。しかし、決定的なBüchiオートマトンは同じω言語では存在しないかもしれません。