2026-07-22T22:18:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22894 2025-10-02T13:36:45Z ddc:004 open_access

A Dichotomy Theorem for Ordinal Ranks in MSO Niwiński, Damian Parys, Paweł Skrzypczak, Michał dichotomy result limit ordinal countable ordinals nondeterministic tree automata We focus on formulae ∃X.φ(Y, X) of monadic second-order logic over the full binary tree, such that the witness X is a well-founded set. The ordinal rank rank(X) < ω₁ of such a set X measures its depth and branching structure. We search for the least upper bound for these ranks, and discover the following dichotomy depending on the formula φ. Let η_φ be the minimal ordinal such that, whenever an instance Y satisfies the formula, there is a witness X with rank(X) ≤ η_φ. Then η_φ is either strictly smaller than ω² or it reaches the maximal possible value ω₁. Moreover, it is decidable which of the cases holds. The result has potential for applications in a variety of ordinal-related problems, in particular it entails a result about the closure ordinal of a fixed-point formula. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Damian Niwiński and Paweł Parys and Michał Skrzypczak 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.69 urn:nbn:de:0030-drops-228942 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.69 eng https://creativecommons.org/licenses/by/4.0/legalcode