Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique

DOI10.2168/LMCS-4(1:5)2008zbMath1158.68022MaRDI QIDQ3518271

Qiqi Yan

Publication date: 7 August 2008

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

zbMATH Keywords

Büchi automata; Streett automata; nondeterministic \(\omega \)-automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)