2026-07-21T20:03:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23526 2025-10-02T12:57:48Z ddc:004 open_access

The Memory of ω-Regular and BC(Σ⁰₂) Objectives Casares, Antonio Ohlmann, Pierre Infinite duration games Strategy complexity Omega-regular In the context of 2-player zero-sum infinite duration games played on (potentially infinite) graphs, the memory of an objective is the smallest integer k such that in any game won by Eve, she has a strategy with ≤ k states of memory. For ω-regular objectives, checking whether the memory equals a given number k was not known to be decidable. In this work, we focus on objectives in BC(Σ⁰₂), i.e. recognised by a potentially infinite deterministic parity automaton. We provide a class of automata that recognise objectives with memory ≤ k, leading to the following results: - for ω-regular objectives, the memory can be computed in NP; - given two objectives W₁ and W₂ in BC(Σ⁰₂) and assuming W₁ is prefix-independent, the memory of W₁ ∪ W₂ is at most the product of the memories of W₁ and W₂. Our results also apply to chromatic memory, the variant where strategies can update their memory state only depending on which colour is seen. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antonio Casares and Pierre Ohlmann 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.149 urn:nbn:de:0030-drops-235267 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.149 eng https://creativecommons.org/licenses/by/4.0/legalcode