On the power of finite ambiguity in Büchi complementation
From MaRDI portal
Publication:6040669
DOI10.1016/j.ic.2023.105032arXiv2109.12828MaRDI QIDQ6040669
Li-jun Zhang, Moshe Y. Vardi, Andrea Turrini, Yong Li, Weizhi Feng
Publication date: 19 May 2023
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2109.12828
complementationBüchi automatafinite ambiguityfinitely ambiguous Büchi automatalimit deterministic Büchi automatarank-based algorithmslice-based algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Alternating finite automata on \(\omega\)-words
- Profile trees for Büchi word automata, with application to determinization
- The complementation problem for Büchi automata with applications to temporal logic
- Complementing deterministic Büchi automata in polynomial time
- Unambiguous Büchi automata.
- On finitely ambiguous Büchi automata
- Complementation of finitely ambiguous Büchi automata
- A novel learning algorithm for Büchi automata based on family of DFAs and classification trees
- Complementing semi-deterministic Büchi automata
- Relating word and tree automata
- Unambiguous Büchi Is Weak
- B\"uchi Complementation and Size-Change Termination
- Advanced automata minimization
- State of B\"uchi Complementation
- Advanced Ramsey-Based Büchi Automata Inclusion Testing
- From LTL and Limit-Deterministic Büchi Automata to Deterministic Parity Automata
- On Determinisation of Good-for-Games Automata
- Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
- Complementation, Disambiguation, and Determinization of Büchi Automata Unified
- Weak alternating automata are not that weak
- Solving Games Without Determinization
- Antichains for the Automata-Based Approach to Model-Checking
- The complexity of probabilistic verification
- Handbook of Model Checking
- Markov Chains and Unambiguous Büchi Automata
- Limit-Deterministic Büchi Automata for Linear Temporal Logic
- Unifying B\"uchi Complementation Constructions
- Good-for-MDPs Automata for Probabilistic Analysis and Reinforcement Learning
- Computer Aided Verification
- Lazy probabilistic model checking without determinisation
- Büchi Complementation Made Tight
- BÜCHI COMPLEMENTATION MADE TIGHTER
- Reducing (To) the Ranks: Efficient Rank-Based Büchi Automata Complementation
