On the Succinctness of Nondeterminism

DOI10.1007/11901914_12MaRDI QIDQ3522904zbMATH OpenOpenAlexFDO

Authors Benjamin Aminof, Orna Kupferman

Publication date 4 September 2008

Published in Automated Technology for Verification and Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11901914_12

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• On the Relative Succinctness of Nondeterministic Büchi and co-Büchi Word Automata
• Co-Büching them all
• The quest for a tight translation of Büchi to co-Büchi automata
• On the (in)succinctness of Muller automata
• Translating to co-Büchi made tight, unified, and useful

Cited in

(7)

• On Repetition Languages
• On the Relative Succinctness of Nondeterministic Büchi and co-Büchi Word Automata
• Towards separating nondeterminism from determinism
• On the (in)succinctness of Muller automata
• scientific article; zbMATH DE number 5917702 (Why is no real title available?)
• Nondeterminism through well-founded choice
• scientific article; zbMATH DE number 3846839 (Why is no real title available?)

This page was built for publication: On the Succinctness of Nondeterminism

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