2026-07-25T01:57:28Z https://drops.dagstuhl.de/oai

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

A Collapse of the Parity Index Hierarchy of Tree Automata, Based on Cantor-Bendixson Ranks Lehtinen, Karoliina Lhote, Nathan Parity tree automata alternating automata Cantor-Bendixson rank Over words, nondeterministic Büchi automata and alternating weak automata are as expressive as parity automata with any number of priorities. Over trees, the Büchi acceptance condition is strictly weaker and the more priorities we allow, the more languages parity automata can recognise. We say that on words, the parity-index hierarchies of nondeterministic and alternating automata collapse to the Büchi and weak level, respectively, while both are infinite over trees. We ask when is Büchi enough?, that is, on which classes of trees are nondeterministc Büchi automata as expressive as parity automata. Similarly for alternating weak automata. We work in the setting of unranked unordered trees, in which there is no order among the children of nodes. We find that for nondeterministic and alternating automata, the parity-index hierarchy collapses to the Büchi level and weak level, respectively, for any class of trees of finitely bounded Cantor-Bendixson rank, a topological measure of tree complexity. Over trees of countable Cantor-Bendixson rank, (a.k.a. thin trees) the parity-index hierarchy of both nondeterministic and alternating automata collapses to the level [1,2,3], as was already known for ordered trees. These results are in some sense optimal: on the class of trees of finite but unbounded Cantor-Bendixson rank, two priorities do not suffice to recognise all parity-recognisable languages, even for alternating automata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karoliina Lehtinen and Nathan Lhote 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.164 urn:nbn:de:0030-drops-235418 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.164 eng https://creativecommons.org/licenses/by/4.0/legalcode