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 | Size | Format | |
---|---|---|---|---|
0705.2205.pdf | Published (publisher PDF) | 289.97 kB | Adobe PDF | View/Open |
Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.