Lower bounds for unambiguous automata via communication complexity
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...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2022
|
| Summary: | 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.
|
|---|