Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/10138
Title: From bidirectionality to alternation
Authors: Piterman, Nir
Vardi, M.Y.
First Published: 31-Dec-2002
Publisher: Elsevier
Citation: Theoretical computer science, 2003, 295 (1-3), pp. 295-321.
Abstract: 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.
DOI Link: 10.1016/S0304-3975(02)00410-3
ISSN: 0304-3975
Links: http://www.journals.elsevier.com/theoretical-computer-science/
http://hdl.handle.net/2381/10138
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: © 2002 Elsevier Science B.V. All rights reserved. Deposited with reference to the journal's archiving policy available on the SHERPA/RoMEO website and on the journal's website.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
Piterman_from bidirectionality to alternation_submission.pdf315.38 kBAdobe PDFView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.