Congruence Relations for Büchi Automata

DOI10.1007/978-3-030-90870-6_25MaRDI QIDQ6488469zbMATH OpenFDO

Authors Yong Li, Yih-Kuen Tsay, Andrea Turrini, Moshe Y. Vardi, Lijun Zhang

Publication date 21 April 2023

Full work available at URL https://doi.org/10.1007/978-3-030-90870-6_25

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Büchi complementation made tight
• Co-Büching them all
• A simple and optimal complementation algorithm for Büchi automata
• BÜCHI COMPLEMENTATION MADE TIGHTER
• Automated Technology for Verification and Analysis

Cites work

• A novel learning algorithm for Büchi automata based on family of DFAs and classification trees
• Advanced Ramsey-based Büchi automata inclusion testing
• Coinductive algorithms for Büchi automata
• Complementation, Disambiguation, and Determinization of Büchi Automata Unified
• Efficient Büchi universality checking
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• Families of DFAs as acceptors of -regular languages
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• Improved Ramsey-based Büchi complementation
• Learning regular omega languages
• Linear Automaton Transformations
• Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
• Model checking of safety properties
• Profile trees for Büchi word automata, with application to determinization
• The complementation problem for Büchi automata with applications to temporal logic
• Ultimately periodic words of rational ω-languages
• Unifying Büchi complementation constructions
• Weak alternating automata are not that weak

Cited in

(6)

• scientific article; zbMATH DE number 1254099 (Why is no real title available?)
• Simulation relations for alternating Büchi automata
• On the power of finite ambiguity in Büchi complementation
• Towards a grand unification of Büchi complementation constructions
• FORQ-Based Language Inclusion Formal Testing
• From Nerode's congruence to suffix automata with mismatches

This page was built for publication: Congruence Relations for Büchi Automata

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