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

DOI10.1007/978-3-540-89439-1_14zbMATH Open1182.68098OpenAlexW1536608616MaRDI QIDQ5505553FDOQ5505553

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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)