Lower Bounds for Unambiguous Automata via Communication Complexity

Mika Göös, Stefan Kiefer, Weiqiang Yuan

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. $\text{Complement:}$ The…