Complementation of finitely ambiguous Büchi automata (Q1623004)

The complementation of Büchi automata is a classical problem in the theory of automata on infinite words. A nondeterministic automaton on infinite words is called \textit{finitely ambiguous} if for each input there are at most finitely many accepting runs. The author proves that the complement of an \(\omega\)-language accepted by a finitely ambiguous Büchi automaton with \(n\) states is accepted by an unambiguous Büchi automaton with \(2\cdot 5^n\) states. This bound is lower than the tight \(\Omega((0.76n)^n)\) lower and upper bounds for complementation of arbitrary nondeterministic Büchi automata shown by \textit{Q. Yan} [Log. Methods Comput. Sci. 4, No. 1, Paper 5, 20 p. (2008; Zbl 1158.68022)] and \textit{S. Schewe} [LIPIcs -- Leibniz Int. Proc. Inform. 3, 661--672 (2009; Zbl 1236.68176)]. In the final section the author announces results on forbidden patterns for certain types of ambiguity (bounded, finite, or countable). For the entire collection see [Zbl 1398.68030].