Translating to Co-Büchi made tight, unified, and useful

U. Boker, O. Kupferman, ACM Transactions on Computational Logic (TOCL) 13 (2012).

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English
Author
;
Department
Abstract
We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is 2o(nlog n) and the lower bound is 1.5n. We improve the upper bound to n2n and describe a matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We continue and solve the open problems of translating nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to DCW. Going via an intermediate NBW is not optimal and we describe direct, simple, and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions are variants of the subset construction, providing a unified approach for translating all common classes of automata to NCW and DCW. Beyond the theoretical importance of the results, we point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation, when possible, of LTL to deterministic Büchi word automata.
Publishing Year
Date Published
2012-10-01
Journal Title
ACM Transactions on Computational Logic (TOCL)
Volume
13
Issue
4
Article Number
29
IST-REx-ID

Cite this

Boker U, Kupferman O. Translating to Co-Büchi made tight, unified, and useful. ACM Transactions on Computational Logic (TOCL). 2012;13(4). doi:10.1145/2362355.2362357
Boker, U., & Kupferman, O. (2012). Translating to Co-Büchi made tight, unified, and useful. ACM Transactions on Computational Logic (TOCL), 13(4). https://doi.org/10.1145/2362355.2362357
Boker, Udi, and Orna Kupferman. “Translating to Co-Büchi Made Tight, Unified, and Useful.” ACM Transactions on Computational Logic (TOCL) 13, no. 4 (2012). https://doi.org/10.1145/2362355.2362357.
U. Boker and O. Kupferman, “Translating to Co-Büchi made tight, unified, and useful,” ACM Transactions on Computational Logic (TOCL), vol. 13, no. 4, 2012.
Boker U, Kupferman O. 2012. Translating to Co-Büchi made tight, unified, and useful. ACM Transactions on Computational Logic (TOCL). 13(4).
Boker, Udi, and Orna Kupferman. “Translating to Co-Büchi Made Tight, Unified, and Useful.” ACM Transactions on Computational Logic (TOCL), vol. 13, no. 4, 29, ACM, 2012, doi:10.1145/2362355.2362357.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar