A Dichotomy Theorem for Ordinal Ranks in MSO

Prelegent(ci)

Paweł Parys

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

4 grudnia 2024 14:15

Pokój

p. 5440

Tytuł w języku polskim

A Dichotomy Theorem for Ordinal Ranks in MSO

Seminarium

Seminarium „Teoria automatów”

---

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) < ω_1 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 ω^2 or it reaches the maximal possible value ω_1. 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.

The talk will be based on a joint work with Damian Niwiński and Michał 
Skrzypczak. Last week Michał presented some motivation for the result that 
I will present. However, I will introduce all necessary definitions, so no 
knowledge from the previous week is needed to understand my talk.

---