약한 뷔치 오토마톤

컴퓨터 과학과 오토마타 이론에서, 약한 뷔치 오토마톤은 무한한 단어의 집합을 나타내는 형식주의이다.Weak Büchi automaton은 Büchi automaton을 수정한 것으로, 동일한 강하게 연결된 컴포넌트에 속하는 모든 $상태{\displaystyle }$q$(\$$displaystyle$q$$)와${\displaystyle {}^{}}$q(\$displaystyle$q') 쌍에 대해${\displaystyle }$${\displaystyle {}^{}}$q$(\$q')가$$$$ 수용되는 $경우$에만 허용됩니다.

Büchi automaton은 최종 상태 $집합{\displaystyle }$F(\$displaystyle$ F$)$에서 적어도 하나의 상태가 무한히 자주 발생하도록 w$(\displaystyle$ w$$$)$라는 단어를 받아들인다. Weak Büchi automata의 경우, 이 조건은 최종적으로 수용 상태 집합에 머무르는 실행의 존재와 같다.

약한 Büchi automata는 Büchi automaton이나 Co-Büchi automaton보다 표현력이 엄격히 떨어집니다.

특성.

결정론적 Weak Büchi 오토마타는 시간 O${\displaystyle (n}$ log ${\displaystyle (}$ (${\displaystyle n}$ $){$ $display style$ O$(n\log(n)}$^[1])로 최소화할 수 있습니다.

Weak Büchi automata에 의해 받아들여진 언어는 통합, 교차 및 보완 하에 폐쇄된다.

비결정론적인 약한 Büchi 오토마타는 약한 Büchi 오토마타보다 더 표현력이 뛰어납니다.예를 들어 언어$({\displaystyle a}$ ${\displaystyle +{}^{}b}$)${\displaystyle {}^{}{}^{}}$ ${\displaystyle b^{}}$ ${\$ {{$displaystyle (a+b)^{*}b^{\omega$}}는$$ 약한 Büchi 오토마톤에 의해 결정될 수 있지만 결정론적 Büchi 오토마톤에 의해 결정되지 않는다.

레퍼런스

• Boigelot, Bernard (3 July 2005). "An effective decision procedure for linear arithmetic over the integers and reals" (PDF). ACM Transactions on Computational Logic. 6 (3): 614–633. doi:10.1145/1071596.1071601.