Lower Bounds on Unambiguous Automata Complementation and Separation via Communication Complexity.
Mika Göös, Stefan Kiefer · arXiv (Cornell University) · 2021
We use results from communication complexity, both new and old ones, to prove lower bounds for problems on unambiguous finite automata (UFAs). We show: (1) Complementing UFAs with $n$ states requires in general at least $n^{\tilde{\Omega}(\log n)}$ states, improving on a bound by Raskin. (2) There are languages $L_n$ such that both $L_n$ and its complement are recognized by NFAs with $n$ states but any UFA that recognizes $L_n$ requires $n^{\Omega(\log n)}$ states, refuting a conjecture by Colcombet on separation.