In this work, we exploit the power of 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. Given a   B\"uchi  automaton with n states and a finite degree of ambiguity, we show that 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^{ \mathcal{O (n)} from 2^{ \mathcal{O (n\log n)} and to \mathcal{O (4^n) from \mathcal{O ((3n)^n) , based on reduced run DAGs. To the best of our knowledge, the improved complexity is exponentially better than best known result of \mathcal{O 21%DIFDELCMD < ] %%% for complementing B\"uchi automata with a finite degree of ambiguity .
In this work, we exploit the power of 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 aunified tool to optimizeboth 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) %DIFDELCMD < ] %%% .
R
unambiguity
unambiguity
R
Given a
We then show how to use this type of reduced run DAGs as a
A
unified tool
A
to optimize
A
both
A
rank-based and slice-based complementation constructions for
A
automata with a finite degree of ambiguity. As a result, given a B\"uchi
D
we show that
R
Rank-based and Slice-based
rank-based and slice-based
R
\mathcal{O
O
R
\mathcal{O
O
R
\mathcal{O
O
R
\mathcal{O
O
D
, based on reduced run DAGs. To the best of our knowledge, the improved complexity is exponentially better than best known result of \mathcal{O
D
21
D
for complementing B\"uchi automata with a finite degree of ambiguity