On complementing unambiguous automata and graphs with many cliques and cocliques
Emil Indzhev, Stefan Kiefer · Information Processing Letters · 2022
We show that for any unambiguous finite automaton with n states there exists an unambiguous finite automaton with n+1⋅2n/2 states that recognizes the complement language. This builds and improves upon a similar result by Jirásek et al. (2018) [1]. Our improvement is based on a reduction to and an analysis of a problem from extremal graph theory: we show that for any graph with n vertices, the product of the number of its cliques with the number of its cocliques (independent sets) is bounded by (n+1)2n.