2026-08-04T07:40:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23537 2025-10-02T12:58:07Z ddc:004 open_access

Using Games and Universal Trees to Characterise the Nondeterministic Index of Tree Languages Idir, Olivier Lehtinen, Karoliina Tree automata parity automata Mostowski index Strahler number attractor decomposition universal trees The parity index problem of tree automata asks, given a regular tree language L and a set of priorities J, is L J-feasible, that is, recognised by a nondeterministic parity automaton with priorities J? This is a long-standing open problem, of which only a few sub-cases and variations are known to be decidable. In a significant but technically difficult step, Colcombet and Löding reduced the problem to the uniform universality of distance-parity automata. In this article, we revisit the index problem using tools from the parity game literature. We add some counters to Lehtinen’s register game, originally used to solve parity games in quasipolynomial time, and use this novel game to characterise J-feasibility. This provides a alternative proof to Colcombet and Löding’s reduction. We then provide a second characterisation, based on the notion of attractor decompositions and the complexity of their structure, as measured by a parameterised version of their Strahler number, which we call n-Strahler number. Finally, we rephrase this result using the notion of universal tree extended to automata: a guidable automaton recognises a [1,2j]-feasible language if and only if it admits a universal tree with n-Strahler number j, for some n. In particular, a language recognised by a guidable automaton {A} is Büchi-feasible if and only if there is a uniform bound n ∈ ℕ such that all trees in the language admit an accepting run with an attractor decomposition of width bounded by n. Equivalently, the language is Büchi-feasible if and only if {A} admits a finite universal tree. While we do not solve the decidability of the index problem, our work makes the state-of-the-art more accessible and brings to light the deep relationships between the J-feasibility of a language and attractor decompositions, universal trees and Lehtinen’s register game. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Olivier Idir and Karoliina Lehtinen 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.160 urn:nbn:de:0030-drops-235377 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.160 eng https://creativecommons.org/licenses/by/4.0/legalcode