Complementation of finitely ambiguous Büchi automata (Q1623004)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complementation of finitely ambiguous Büchi automata |
scientific article |
Statements
Complementation of finitely ambiguous Büchi automata (English)
0 references
22 November 2018
0 references
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].
0 references
finite automata
0 references
infinite words
0 references
unambiguous Büchi automata
0 references
complementation
0 references