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
|