Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Lower Bounds for Unambiguous Automata via Communication Complexity
 
conference paper

Lower Bounds for Unambiguous Automata via Communication Complexity

Göös, Mika  
•
Kiefer, Stefan
•
Yuan, Weiqiang  
2022
[Proceedings of ICALP 2022]
49th EATCS International Colloquium on Automata, Languages and Programming (ICALP)

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 improves on a lower bound by Raskin. 2) Union: There are languages L₁, L₂ recognised by n-state UFAs such that the union L₁∪L₂ requires UFAs with n^Ω̃(log n) states. 3) Separation: There is a language L such that both L and ̅L are recognised by n-state NFAs but such that L requires UFAs with n^Ω(log n) states. This refutes a conjecture by Colcombet. LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 126:1-126:13

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

LIPIcs-ICALP-2022-126.pdf

Type

Publisher

Version

Published version

Access type

openaccess

License Condition

CC BY

Size

771.35 KB

Format

Adobe PDF

Checksum (MD5)

5ca16a269fc83247325621856c4dd2f4

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés