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.

@article{PV03,
         author = "N. Piterman and M. Vardi",
         title = "From Bidirectionality to Alternation",
         journal = "Theoretical Computer Science",
         volume = "295",
         number = "1-3",
         pages = "295-321",
         month = "February",
         year = 2003
}

PDF