On the Relative Succinctness of Nondeterministic Büchi and co-Büchi Word Automata

DOI10.1007/978-3-540-89439-1_14MaRDI QIDQ5505553zbMATH OpenOpenAlexFDO

Authors Benjamin Aminof, Orna Kupferman, Omer Lev

Publication date 27 January 2009

Published in Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-89439-1_14

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The quest for a tight translation of Büchi to co-Büchi automata
• Translating to co-Büchi made tight, unified, and useful
• Co-Büching them all
• On the Succinctness of Nondeterminism
• Weak alternating automata are not that weak

Cited in

(6)

• Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata
• A power-set construction for reducing Büchi automata to non-determinism degree two
• Co-Büching them all
• The quest for a tight translation of Büchi to co-Büchi automata
• Translating to co-Büchi made tight, unified, and useful
• On the Succinctness of Nondeterminism

This page was built for publication: On the Relative Succinctness of Nondeterministic Büchi and co-Büchi Word Automata

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