Singly exponential translation of alternating weak Büchi automata to unambiguous Büchi automata

DOI10.1016/J.TCS.2024.114650MaRDI QIDQ6562457zbMATH OpenFDO

Authors Yong Li, Sven Schewe, Moshe Y. Vardi

Publication date 26 June 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114650

zbMATH Keywords

alternationBüchi automatadisambiguationunambiguous automataweak

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Alternating automata, the weak monadic theory of trees and its complexity
• Alternating finite automata on -words
• Alternation removal in Büchi automata
• An asymptotic equivalent for the number of total preorders on a finite set
• Büchi complementation made tight
• Complementation of finitely ambiguous Büchi automata
• Complementation, Disambiguation, and Determinization of Büchi Automata Unified
• Computer Aided Verification
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Foundations of software science and computation structures. 25th international conference, FOSSACS 2022, held as part of the European joint conferences on theory and practice of software, ETAPS 2022, Munich, Germany, April 2--7, 2022. Proceedings
• From LTL to unambiguous Büchi automata via disambiguation of alternating automata
• scientific article; zbMATH DE number 3983141 (Why is no real title available?)
• scientific article; zbMATH DE number 1796123 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• Improved upper and lower bounds for Büchi disambiguation
• LTL model checking of interval Markov chains
• Markov chains and unambiguous automata
• On complementing unambiguous automata and graphs with many cliques and cocliques
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• On the power of finite ambiguity in Büchi complementation
• Operations on Unambiguous Finite Automata
• Theoretical aspects of computing -- ICTAC 2019. 16th international colloquium, Hammamet, Tunisia, October 31 -- November 4, 2019. Proceedings
• Unambiguous Büchi automata.
• Weak alternating automata are not that weak

Cited in

(1)

• Alternating refinement relations for fuzzy concurrent game structures

This page was built for publication: Singly exponential translation of alternating weak Büchi automata to unambiguous Büchi automata

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