Lower bounds for unambiguous automata via communication complexity - Göös, M; Kiefer, S; Yuan, W (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022)
We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1. Complement: There is a language L recognised by an n-state UFA such that the complement language L requires NFAs with n Ω(log ˜ n) states. This improves on a lower bound by Raskin. 2. Union: There are languages L1, L2 recognised by n-state UFAs such that the union L1 ∪ L2 requires UFAs with n Ω(log ˜ n) states. 3. Separation: There is a language L such that both L and L are recognised by n-state NFAs but such that L requires UFAs with n Ω(log n) states. This refutes a conjecture by Colcombet.