Exponential determinization for ω-automata with strong-fairness acceptance condition (extended abstract)
Muli Safra · 1992
In [Saf88] an exponential determination procedure for Bu¨chi automata was shown, yielding tight bounds for decision procedures of some logics ([EJ88, Saf88, SV89, KT89]). In [SV89] the complexity of determinization and complementation of ω-automata was further investigated, leaving as an open question the complexity of the determinization of a single class of ω-automata. For this class of ω-automata with strong fairness as acceptance condition (Street automata), [SV89] managed to show an exponential complementation procedure, but showed that the blow-up of the translation of these automata to any of the classes known to admit exponential determinization is inherently exponential. This might suggest that the blow-up of the determinization of Street automata is inherently doubly exponential.