Technical Report No. 228 - Abstract

C. Dax, J. Eisinger, F. Klaedtke
Mechanizing the Powerset Construction for Restricted Classes of omega-Automata

Automata over infinite words provide a powerful framework, which we can use to solve various decision problems. However, the automatized reasoning with restricted classes of automata over infinite words is often simpler and more efficient. For instance, weak deterministic Büchi automata (WDBAs), which recognize the ω-regular languages in the Borel class F_σ ∩ G_δ, can be handled algorithmically almost as efficient as deterministic automata over finite words. In this paper, we show how and when we can determinize automata over infinite words by the standard powerset construction for finite words. The presented construction is more efficient than all-purpose constructions for automata that recognize languages in F_σ ∩ G_δ. Further, based on the subset construction, we present an improved automata construction that handles the quantification in the automata-based approach for FO(ℝ,ℤ,+,<) much more efficiently.