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

Büchi automatanondeterministic \(\omega \)-automataStreett automata

Mathematics Subject Classification ID

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

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
• scientific article; zbMATH DE number 1408338
• Complementation of finitely ambiguous Büchi automata

Cited in

(20)

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

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)