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
|