一句话：提出一种直接在状态子集上运行、结构简单的确定性 Büchi 自动机求补算法，并证明其达到最优上界。
Büchi 自动机通常是非确定性的，其求补问题复杂，最坏情况下状态空间增长下界 O((0.76n)^n) 不可回避。已有实验表明结构简单的求补算法平均表现更好。本文提出一种简单算法：直接操作状态子集，并将其组织为类似 slice 的状态集元组，最终构造确定性自动机；随后施加与确定性 Büchi 自动机直接求补相似的补集过程，后者成为该构造的特例。作者证明该构造最优，即具有 O((0.76n)^n) 上界，并以新颖方式精确计算 0.76 因子。
Complementation of Büchi automata is complex as Büchi automata in general are nondeterministic. A worst-case state-space growth of O((0.76n)n) cannot be avoided. Experiments suggest that complementation algorithms perform better on average when they are structurally simple. We present a simple algorithm for complementing Büchi automata, operating directly on subsets of states, structured into state-set tuples (similar to slices), and producing a deterministic automaton. Then a complementation procedure is applied that resembles the straightforward complementation algorithm for deterministic Büchi automata, the latter algorithm actually being a special case of our construction. Finally, we prove our construction to be optimal, i.e. having an upper bound in O((0.76n)n), and furthermore calculate the 0.76 factor in a novel exact way.
DOI 原文 ·
@inproceedings{paperbot4370,
title = {A Simple and Optimal Complementation Algorithm for Büchi Automata},
author = {Joel D. Allred and Ulrich Ultes-Nitsche},
booktitle = {LICS},
year = {2018},
doi = {10.1145/3209108.3209138}
}