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

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.