On the Power of Finite Ambiguity in Büchi Complementation

Abstract

In this work, we exploit the power of \emph{finite ambiguity} for the complementation problem of Büchi automata by using reduced run directed acyclic graphs (DAGs) over infinite words, in which each vertex has at most one predecessor; these reduced run DAGs have only a finite number of infinite runs, thus obtaining the finite ambiguity in Büchi complementation. We show how to use this type of reduced run DAGs as a unified tool to optimize both rank-based and slice-based complementation constructions for Büchi automata with a finite degree of ambiguity. As a result, given a Büchi automaton with $n$ states and a finite degree of ambiguity, the number of states in the complementary Büchi automaton constructed by the classical rank-based and slice-based complementation constructions can be improved from $2^{\mathsf{O}(n\log n)}$ and $\mathsf{O}((3n{)}^n)$ to $\mathsf{O}(6^n)\subseteq 2^{\mathsf{O}(n)}$ and $\mathsf{O}(4^n)$, respectively. We further show how to construct such reduced run DAGs for limit deterministic Büchi automata and obtain a specialized complementation algorithm, thus demonstrating the generality of the power of finite ambiguity.