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...
| Үндсэн зохиолчид: | , , |
|---|---|
| Формат: | Conference item |
| Хэл сонгох: | English |
| Хэвлэсэн: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2022
|