Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Publication
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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 L₁, L₂ recognised by n-state UFAs such that the union L₁∪L₂ 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. LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 126:1-126:13
,
Mika Tapani Göös, Dmitrii Sokolov