Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition

DOI10.1007/978-3-031-13188-2_8zbMATH Open1514.68108MaRDI QIDQ6487334FDOQ6487334

Authors: Yong Li, Andrea Turrini, Weizhi Feng, Moshe Y. Vardi, Lijun Zhang 

Publication date: 7 December 2022

Recommendations

• Deternimization of Büchi automata as partitioned automata
• Determinization of Büchi-Automata
• Determinization of Büchi automata: unifying the approaches of Safra and Muller-Schupp
• Implementation and Application of Automata
• Observations on determinization of Büchi automata
• New optimizations and heuristics for determinization of Büchi automata
• Tighter Bounds for the Determinisation of Büchi Automata
• Minimising deterministic Büchi automata precisely using SAT solving
• Determinizing Büchi asynchronous automata
• Complementing deterministic Büchi automata in polynomial time

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• The complexity of probabilistic verification
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reasoning about infinite computations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Alternating finite automata on \(\omega\)-words
• Tighter Bounds for the Determinisation of Büchi Automata
• From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
• Modalities for model checking: Branching time logic strikes back
• Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
• Weak alternating automata are not that weak
• Büchi complementation made tight
• Complementation, Disambiguation, and Determinization of Büchi Automata Unified
• Alternating automata, the weak monadic theory of trees and its complexity
• A Unified Translation of Linear Temporal Logic to ω-Automata
• Title not available (Why is that?)
• A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata
• ω-Automata
• Owl: a library for \(\omega \)-words, automata, and LTL
• Profile trees for Büchi word automata, with application to determinization
• A modular approach for Büchi determinization
• A tighter analysis of Piterman's Büchi determinization
• Complementing semi-deterministic Büchi automata
• On-the-Fly Stuttering in the Construction of Deterministic ω-Automata
• An improved construction of deterministic omega-automaton using derivatives
• New optimizations and heuristics for determinization of Büchi automata
• From LTL and limit-deterministic Büchi automata to deterministic parity automata
• Title not available (Why is that?)
• State of Büchi complementation
• Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition

Cited In (3)

• On the power of finite ambiguity in Büchi complementation
• Modular mix-and-match complementation of Büchi automata
• Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition

This page was built for publication: Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition

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