Lics

ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Forty-First Annual Symposium on

Logic in Computer Science (LICS 2026)

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}
  }
   

Last modified: 2026-09-2114:25
Sam Staton