论文标题
关于Büchi互补中不兼职的力量
On the Power of Unambiguity in Büchi Complementation
论文作者
论文摘要
在这项工作中，我们利用\ emph {unambiguity}的功率来为BüchiAutomata的补充问题利用\ emph {unambiguity}，通过利用降低运行的有向无环形图（dag）而不是无限词，而每个顶点最多都有一个前代表。然后，我们将如何将这种类型的简化运行DAG用作\ Emph {统一工具}来优化BüchiAutomata的基于\ emph {tot and}基于秩和基于切片的互补结构，并具有有限的模棱两可。结果，给定带有$ n $状态的Büchi自动机和有限程度的模棱两可，是由基于经典级别和基于切片的互补构造的补充Büchi自动机的数量，可以分别提高基于级别的互补构建体，从$ 2^{o（n）} $ $ 2^{o（n）} $从$ 2^{o（N）$ 2^{o（N）$ 2^{O（N）$ 2^{$ n \ n \ n）} $ o（ $ o（（3n）^n）$。
In this work, we exploit the power of \emph{unambiguity} for the complementation problem of Büchi 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ü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, respectively, to $2^{O(n)}$ from $2^{O(n\log n)}$ and to $O(4^n)$ from $O((3n)^n)$.
