Co-Büching them all

U. Boker, O. Kupferman, in:, M. Hofmann (Ed.), Springer, 2011, pp. 184–198.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
;
Editor
Series Title
LNCS
Abstract
We solve the open problems of translating, when possible, all common classes of nondeterministic word automata to deterministic and nondeterministic co-Büchi word automata. The handled classes include Büchi, parity, Rabin, Streett and Muller automata. The translations follow a unified approach and are all asymptotically tight. The problem of translating Büchi automata to equivalent co-Büchi automata was solved in [2], leaving open the problems of translating automata with richer acceptance conditions. For these classes, one cannot easily extend or use the construction in [2]. In particular, going via an intermediate Büchi automaton is not optimal and might involve a blow-up exponentially higher than the known lower bound. Other known translations are also not optimal and involve a doubly exponential blow-up. We describe direct, simple, and asymptotically tight constructions, involving a 2Θ(n) blow-up. The constructions are variants of the subset construction, and allow for symbolic implementations. Beyond the theoretical importance of the results, the new constructions have various applications, among which is an improved algorithm for translating, when possible, LTL formulas to deterministic Büchi word automata.
Publishing Year
Date Published
2011-03-29
Volume
6604
Page
184 - 198
Conference
FoSSaCS: Foundations of Software Science and Computation Structures
Conference Location
Saarbrücken, Germany
Conference Date
2011-03-26 – 2011-04-03
IST-REx-ID

Cite this

Boker U, Kupferman O. Co-Büching them all. In: Hofmann M, ed. Vol 6604. Springer; 2011:184-198. doi:10.1007/978-3-642-19805-2_13
Boker, U., & Kupferman, O. (2011). Co-Büching them all. In M. Hofmann (Ed.) (Vol. 6604, pp. 184–198). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Saarbrücken, Germany: Springer. https://doi.org/10.1007/978-3-642-19805-2_13
Boker, Udi, and Orna Kupferman. “Co-Büching Them All.” edited by Martin Hofmann, 6604:184–98. Springer, 2011. https://doi.org/10.1007/978-3-642-19805-2_13.
U. Boker and O. Kupferman, “Co-Büching them all,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Saarbrücken, Germany, 2011, vol. 6604, pp. 184–198.
Boker U, Kupferman O. 2011. Co-Büching them all. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 6604. 184–198.
Boker, Udi, and Orna Kupferman. Co-Büching Them All. Edited by Martin Hofmann, vol. 6604, Springer, 2011, pp. 184–98, doi:10.1007/978-3-642-19805-2_13.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar