Piterman, Nir - From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata

lmcs:1199 - Logical Methods in Computer Science, August 14, 2007, Volume 3, Issue 3
From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata

Authors: Piterman, Nir

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).


Source : oai:arXiv.org:0705.2205
DOI : 10.2168/LMCS-3(3:5)2007
Volume: Volume 3, Issue 3
Published on: August 14, 2007
Submitted on: June 25, 2015
Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory,F.1.1,F.4.3


Share

Browsing statistics

This page has been seen 62 times.
This article's PDF has been downloaded 34 times.