Zayıf Büchi otomat - Weak Büchi automaton

İçinde bilgisayar Bilimi ve otomata teorisi, bir Zayıf Büchi otomat bir dizi sonsuz kelimeyi temsil eden bir biçimciliktir. Zayıf Büchi otomatı, Büchi otomat öyle ki tüm devletler için ${ displaystyle q}$ ve ${ displaystyle q '}$ aynısına ait güçlü bağlantılı bileşen, ${ displaystyle q}$ kabul ediyor eğer ve ancak ${ displaystyle q '}$ kabul ediyor.

Bir Büchi otomat bir kelimeyi kabul eder ${ displaystyle w}$ bir çalıştırma varsa, en az bir durum son durum kümesinde sonsuz sıklıkta meydana gelir ${ displaystyle F}$. Zayıf Büchi otomataları için bu durum, nihayetinde kabul eden durumlar kümesinde kalan bir çalışmanın varlığına eşdeğerdir.

Zayıf Büchi otomatları, Büchi otomatından kesinlikle daha az ifade edicidir ve Co-Büchi otomat.

Özellikleri

Belirleyici Zayıf Büchi otomatı zaman içinde en aza indirilebilir ${ displaystyle O (n log (n))}$.^[1]

Zayıf Büchi otomatının kabul ettiği diller birleşme, kesişme ve tamamlama altında kapalıdır.

Belirleyici olmayan Zayıf Büchi otomatları, Zayıf Büchi otomatlarından daha etkileyicidir. Örnek olarak, dil ${ displaystyle (a + b) ^ {*} b ^ { omega}}$ zayıf bir Büchi otomatı ile karar verilebilir, ancak belirleyici bir Büchi otomatı ile karar verilebilir

Referanslar

• Boigelot, Bernard (3 Temmuz 2005). "Tam sayılar ve gerçekler üzerinde doğrusal aritmetik için etkili bir karar prosedürü" (PDF). Hesaplamalı Mantıkta ACM İşlemleri. 6 (3): 614–633. doi:10.1145/1071596.1071601.