From bidirectionality to alternation
journal contribution
posted on 2012-03-02, 13:58 authored by Nir Piterman, M.Y. VardiWe 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.
History
Citation
Theoretical computer science, 2003, 295 (1-3), pp. 295-321.Author affiliation
/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer ScienceVersion
- AM (Accepted Manuscript)
Published in
Theoretical computer sciencePublisher
Elsevierissn
0304-3975Copyright date
2002Available date
2012-03-02Publisher DOI
Publisher version
http://www.journals.elsevier.com/theoretical-computer-science/Language
enAdministrator link
Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC