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...
| Những tác giả chính: | , , |
|---|---|
| Định dạng: | Conference item |
| Ngôn ngữ: | English |
| Được phát hành: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2022
|