Upper Bound for the Determinization of Emerson-Lei Automata: A One-Fin Approach

Abstract

Abstract Emerson-Lei automata, which allow arbitrary Boolean combinations of $$\texttt{Fin}$$ Fin and $$\texttt{Inf}$$ Inf acceptance conditions, provide a unifying framework for $$\omega $$ ω -automata but pose significant challenges for determinization. The previous best algorithm relies on a transformation that introduces an exponential blow-up in the state space before determinization even begins. We present a new determinization algorithm that completely bypasses this bottleneck. Our key insight is that each disjunct of an Emerson-Lei condition in DNF corresponds directly to a one-Fin automaton —a restricted form of Streett automaton whose structure enables more efficient determinization via H-Safra trees. By exploiting this connection, we establish an upper bound of $$ 2^{O\!\big (3^{|\alpha |/3} \cdot (n \log n + n|\alpha | \log |\alpha |)\big )} $$ 2 O ( 3 | α | / 3 · ( n log n + n | α | log | α | ) ) where n is the number of states and $$|\alpha |$$ | α | is the acceptance condition size. This improves the exponent over the previous best bound by a factor of $$2^{2|\alpha |}/3^{|\alpha |/3}$$ 2 2 | α | / 3 | α | / 3 , an exponential improvement in the acceptance condition complexity.