Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/18930
Title: From Nondeterministic Büchi and Streett Automata to Deterministic Parity Automata
Authors: Piterman, Nir
First Published: 14-Aug-2007
Publisher: TECH UNIV BRAUNSCHWEIG
Citation: Logical Methods in Computer Science, 2007, 3 (3), 5
Abstract: In this paper we revisit Safra's determinization constructions for automata on infinite words. We show how to construct deterministic automata with fewer states and, most importantly, parity acceptance conditions. Determinization is used in numerous applications, such as reasoning about tree automata, satisfiability of CTL*, and realizability and synthesis of logical specifications. The upper bounds for all these applications are reduced by using the smaller deterministic automata produced by our construction. In addition, the parity acceptance conditions allows to use more efficient algorithms (when compared to handling Rabin or Streett acceptance conditions).
DOI Link: 10.2168/LMCS-3(3:5)2007
ISSN: 1860-5974
Links: http://hdl.handle.net/2381/18930
http://www.lmcs-online.org/ojs/viewarticle.php?id=247
Version: Publisher Version
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © 2007, Nir Piterman, EPFL. This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/2.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford , California 94305, USA.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
0705.2205.pdfPublished (publisher PDF)289.97 kBAdobe PDFView/Open


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