Paper: Layered Automata: A Canonical Model for Automata over Infinite Words (at LICS 2026)

Authors: Antonio Casares Christof Löding Igor Walukiewicz

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.24

Abstract

We introduce layered automata, a subclass of alternating parity automata that generalises deterministic automata. Assuming a consistency property, these automata are history deterministic and 0-1 probabilistic. We show that every omega-regular language is recognised by a unique minimal consistent layered automaton, and that this canonical form can be computed in polynomial time from every layered or deterministic automaton. We further establish that, for layered automata, both consistency checking and inclusion testing can be performed in polynomial time. Much like deterministic finite automata, minimal consistent layered automata admit a characterisation based on congruences.

BibTeX

  @InProceedings{CasaresLodingWaluki-LayeredAutomataACan,
    author = 	 {Antonio Casares and Christof Löding and Igor Walukiewicz},
    title = 	 {Layered Automata: A Canonical Model for Automata over Infinite Words},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {24:1--24:26},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.24}
  }