Paper: Checking History Determinism for Parity Automata Is in NP (at LICS 2026)
Authors: Karoliina Lehtinen Keya Prakash Michał Skrzypczak
Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.64
Abstract
History-deterministic automata, often also called good-for-games, are an intermediate model between deterministic and nondeterministic automata, which are particularly well-suited for applications in verification and reactive synthesis. We show that deciding whether a parity automaton is history-deterministic is in NP. Our result matches an NP-hardness lower bound (Prakash 2024) and builds on insights from a fixed-parameter tractable algorithm (Lehtinen and Prakash 2025). This settles the complexity of the problem, which has been open since 2006.
BibTeX
@InProceedings{LehtinenPrakashSkrz-CheckingHistoryDete,
author = {Karoliina Lehtinen and Keya Prakash and Michał Skrzypczak},
title = {Checking History Determinism for Parity Automata Is in NP},
booktitle = {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
year = {2026},
month = {July},
pages = {64:1--64:24},
location = {Lisbon, Portugal},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
doi = {10.4230/LIPIcs.LICS.2026.64}
}
