On Complementing Unambiguous Automata and Graphs With Many Cliques and Cocliques

Emil Indzhev, Stefan Kiefer

We show that for any unambiguous finite automaton with $n$ states there exists an unambiguous finite automaton with $\sqrt{n+1}\cdot 2^{n/2}$ states that recognizes the complement…