Checking history-determinism is NP-hard for parity automata
From MaRDI portal
Publication:6629459
DOI10.1007/978-3-031-57228-9_11MaRDI QIDQ6629459FDOQ6629459
Authors: Aditya Prakash 
Publication date: 30 October 2024
Cites Work
- Borel determinacy
- Mathematical Foundations of Computer Science 2005
- The Complexity of Tree Automata and Logics of Programs
- Title not available (Why is that?)
- The Theory of Stabilisation Monoids and Regular Cost Functions
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Title not available (Why is that?)
- Theories of automata on \(\omega\)-tapes: a simplified approach
- Fair simulation
- Generalized Parity Games
- Solving Games Without Determinization
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- How deterministic are good-for-games automata?
- On Distributive Fixed-Point Expressions
- Büchi Good-for-Games Automata Are Efficiently Recognizable
- Title not available (Why is that?)
- On history-deterministic one-counter nets
- Title not available (Why is that?)
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)
