Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
From MaRDI portal
Publication:3518271
DOI10.2168/LMCS-4(1:5)2008zbMATH Open1158.68022OpenAlexW3104076899MaRDI QIDQ3518271FDOQ3518271
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
Recommendations
- Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
- scientific article
- 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
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (18)
- Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
- A tight lower bound for Streett complementation
- Title not available (Why is that?)
- On the power of finite ambiguity in Büchi complementation
- Modular mix-and-match complementation of Büchi automata
- State of Büchi complementation
- Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition
- Tighter Bounds for the Determinisation of Büchi Automata
- A tighter analysis of Piterman's Büchi determinization
- Congruence Relations for Büchi Automata
- Operations on weakly recognizing morphisms
- Rabin vs. Streett automata
- Bounded model checking of ETL cooperating with finite and looping automata connectives
- Title not available (Why is that?)
- Can nondeterminism help complementation?
- The complexity of weakly recognizing morphisms
- Towards a grand unification of Büchi complementation constructions
- Title not available (Why is that?)
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)
