Alternating Automata and Logics over Innite Words (Extended Abstract)
Christof Löding, Wolfgang H Thomas · 2000
We give a uniform treatment of the logical properties of al- ternating weak automata on innite strings, extending and rening work of Muller, Saoudi, and Schupp (1984) and Kupferman and Vardi (1997). Two ideas are essential in the present set-up: There is no acyclicity re- quirement on the transition structure of weak alternating automata, and acceptance is dened only in terms of reachability of states; moreover, the run trees of the standard framework are replaced by run dags of boun- ded width. As applications, one obtains a new normal form for monadic second order logic, a simple complementation proof for weak alternating automata, and elegant connections to temporal logic.