Checking history-determinism is NP-hard for parity automata
From MaRDI portal
Publication:6629459
DOI10.1007/978-3-031-57228-9_11MaRDI QIDQ6629459FDOQ6629459
Publication date: 30 October 2024
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Borel determinacy
- Mathematical Foundations of Computer Science 2005
- The Complexity of Tree Automata and Logics of Programs
- The Theory of Stabilisation Monoids and Regular Cost Functions
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Theories of automata on \(\omega\)-tapes: a simplified approach
- Fair simulation
- Generalized Parity Games
- Solving Games Without Determinization
- Advanced Ramsey-Based Büchi Automata Inclusion Testing
- Beyond hyper-minimisation -- minimising DBAs and DPAs is NP-complete
- On Determinisation of Good-for-Games Automata
- Deciding Parity Games in Quasi-polynomial Time
- How Deterministic are Good-For-Games Automata?
- On Distributive Fixed-Point Expressions
- Büchi Good-for-Games Automata Are Efficiently Recognizable
- On history-deterministic one-counter nets
- A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
- Token Games and History-Deterministic Quantitative-Automata
This page was built for publication: Checking history-determinism is NP-hard for parity automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6629459)
