← Research

On the Power of Unambiguity in B\"uchi Complementation

Yong Li (State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences), Moshe Y. Vardi (Rice University), Lijun Zhang (State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences)

In this work, we exploit the power of \emph{unambiguity} for the complementation problem of B\"uchi automata by utilizing reduced run directed acyclic graphs (DAGs) over infinite words, in which each vertex has at most one predecessor. We then show how to use this type of reduced run DAGs as a \emph{unified tool} to optimize \emph{both} rank-based and slice-based complementation constructions for B\"uchi automata with a finite degree of ambiguity. As a result, given a B\"uchi automaton with $n$ states and a finite degree of ambiguity, the number of states in the complementary B\"uchi automaton constructed by the classical rank-based and slice-based complementation constructions can be improved, respectively, to $2^{O(n)}$ from $2^{O(n\log n)}$ and to $O(4^n)$ from $O((3n)^n)$.

PDF ↗

Models

Loading
EVIDENCE / COMPARISON

Benchmarks

Explore every benchmark

Loading

These charts contain model-linked results. The charts above also include unlinked source profiles. Compare scores within each evaluation. Model quality, usage, transparency and system performance measure different things.

Install TensorTrace