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

DOI10.2168/LMCS-4(1:5)2008MaRDI QIDQ3518271zbMATH OpenOpenAlexFDO

Authors Qiqi Yan

Publication date 7 August 2008

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

Full work available at URL https://doi.org/10.2168/lmcs-4(1:5)2008

zbMATH Keywords

Streett automataBüchi automatanondeterministic \(\omega \)-automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
• scientific article; zbMATH DE number 4179361
• scientific article; zbMATH DE number 1500643
• Tight bounds for complementing parity automata
• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• Tight Bounds for the Determinisation and Complementation of Generalised Büchi Automata
• On alternating \(\omega\)-automata
• On the minimization problem for \(\omega \)-automata
• Publication:4941152
• Complementation of finitely ambiguous Büchi automata

Cited in

(18)

• Can nondeterminism help complementation?
• On the power of finite ambiguity in Büchi complementation
• The complexity of weakly recognizing morphisms
• Towards a grand unification of Büchi complementation constructions
• A tight lower bound for Streett complementation
• State of Büchi complementation
• Congruence Relations for Büchi Automata
• Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
• Bounded model checking of ETL cooperating with finite and looping automata connectives
• scientific article; zbMATH DE number 7649926 (Why is no real title available?)
• scientific article; zbMATH DE number 7147442 (Why is no real title available?)
• Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition
• Operations on weakly recognizing morphisms
• Tighter Bounds for the Determinisation of Büchi Automata
• A tighter analysis of Piterman's Büchi determinization
• Rabin vs. Streett automata
• Modular mix-and-match complementation of Büchi automata
• scientific article; zbMATH DE number 7455748 (Why is no real title available?)

This page was built for publication: Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3518271)