Slabý Büchi automat - Weak Büchi automaton

v počítačová věda a teorie automatů, a Slabý Büchi automat je formalismus, který představuje množinu nekonečných slov. Slabý Büchi automat je modifikací Büchi automat takové, že pro všechny páry států ${ displaystyle q}$ a ${ displaystyle q '}$ patřící ke stejné silně připojená součást, ${ displaystyle q}$ přijímá pouze tehdy, když ${ displaystyle q '}$ přijímá.

A Büchi automat přijímá slovo ${ displaystyle w}$ pokud existuje běh, tak, že alespoň jeden stav se v sadě konečných stavů vyskytuje nekonečně často ${ displaystyle F}$. U automatů Weak Büchi je tato podmínka ekvivalentní existenci běhu, který nakonec zůstane v sadě přijímajících stavů.

Slabé automaty Büchi jsou přísně méně expresivní než automaty Büchi a než Co-Büchi automat.

Vlastnosti

Deterministické automaty Weak Büchi lze minimalizovat v čase ${ displaystyle O (n log (n))}$.^[1]

Jazyky přijímané automaty Weak Büchi jsou uzavřeny spojením, průnikem a doplňováním.

Nedeterministické automaty Weak Büchi jsou expresivnější než automaty Weak Büchi. Jako příklad jazyk ${ displaystyle (a + b) ^ {*} b ^ { omega}}$ může rozhodnout slabý automat Büchi, ale žádný deterministický automat Büchi

Reference

• Boigelot, Bernard (3. července 2005). "Efektivní rozhodovací postup pro lineární aritmetiku nad celými čísly a reálemi" (PDF). Transakce ACM ve výpočetní logice. 6 (3): 614–633. doi:10.1145/1071596.1071601.