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...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριοι συγγραφείς: Göös, M, Kiefer, S, Yuan, W
Μορφή: Conference item
Γλώσσα:English
Έκδοση: Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022