A tight lower bound for Streett complementation

DOI10.4230/LIPICS.FSTTCS.2011.339MaRDI QIDQ2911636zbMATH OpenFDO

Authors Yang Cai, Ting Zhang

Publication date 31 August 2012

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2011.339

zbMATH Keywords

lower boundscomplementationomega-automataStreett automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Tight upper bounds for Streett and parity complementation
• Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
• Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
• Determinization and Complementation of Streett Automata
• BÜCHI COMPLEMENTATION MADE TIGHTER

Cited in

(2)

• Tight upper bounds for Streett and parity complementation
• Rabin vs. Streett automata

This page was built for publication: A tight lower bound for Streett complementation

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