From bidirectionality to alternation

We describe an explicit simulation of 2-way nondeterministic automata by 1-way alternating automata with quadratic blow-up. We first describe the construction for automata on finite words, and extend it to automata on infinite words.

Authors

• Nir Piterman
• Moshe Y. Vardi

Keywords

• Two-way automata
• Nondeterministic finite automata
• Nondeterministic Büchi automata
• Alternating finite automata
• Alternating Büchi automata