Decidability of MSO Reparameterization over Countable Chains

Alexander Rabinovich · 2026

Read Decidability of MSO Reparameterization over Countable Chains by Alexander Rabinovich (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18248.txt.

Introduction

Alexander Rabinovich's 2026 paper asks whether MSO encodings over countable chains can be cut to lower dimension. Encodings place one structure inside another by logical rules, with inner elements standing for tuples of host elements. Cutting one down means finding a reparameterization that lowers its dimension. The main result shows it is decidable whether a formula admits a d-dimensional reparameterization over countable labelled linear orders. Any encoding whose domain admits one thus equals a d-dimensional point encoding.

Catalog record

CREATORAlexander Rabinovich
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44120
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.18248

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Decidability of MSO Reparameterization over Countable Chains Alexander Rabinovich Abstract Interpretations are a fundamental tool in mathematical logic, allowing structures to be encoded within other structures via logical definitions. We study 𝑀𝑆𝑂 \mathit{MSO} multidimensional point interpretations , where elements of an interpreted structure are represented by tuples of elements of the host structure, and address the problem of simplifying such interpretations by reducing their representation dimension. To formalize simplification, we use the notion of reparameterization . Our main result shows that, over the class of countable labelled linear orders, it is decidable whether a given 𝑀𝑆𝑂 \mathit{MSO} formula admits a d d -dimensional reparameterization. As a consequence, every interpretation whose domain admits such a reparameterization is equivalent to a d d -dimensional point interpretation. 1 Introduction The notion of interpretation was first carefully defined and developed in the foundational work of Tarski, Mostowski, and Robinson [ 9 ] . Interpretations are a fundamental tool in mathematical logic, playing a central role in the foundations of mathematics, as well as in the philosophy of science. Consider Monadic Second-Order 1 1 1 Let us recall that monadic second-order logic is an extension of first-order logic by set variables (see Section 2.2 for a formal definition). ( \mathit{MSO} ) d -dimensional (point) interpretations of a structure \mathfrak{A} in a structure \mathfrak{B} . Under such an interpretation, each element of \mathfrak{A} is represented within \mathfrak{B} by a d -tuple of elements of \mathfrak{B} . A central problem is whether a given interpretation can be simplified, for instance by reducing the dimension of the representation. The domain of the interpreted structure is specified by an \mathit{MSO} formula \varphi({x_{1}},\dots,x_{m}) over \mathfrak{B} . To formalize this notion of simplification, we use the notion of reparameterization , introduced in [ 4 ] for \mathit{MSO} -definable relations. Throughout, \bar{x} and \bar{y} denote tuples of first-order variables. Definition 1 (Reparameterization) Let \varphi(\overline{x}) be an \mathit{MSO} formula and let \mathcal{C} be a class of structures. A formula G(\overline{x},\overline{y}) is a (functional) reparameterization of \varphi over \mathcal{C} if the following conditions hold: Same domain: Over \mathcal{C} , \varphi(\overline{x})\;\equiv\;\exists\overline{y}\,G(\overline{x},\overline{y}). Functional: G defines the graph of a partial function, that is, \forall\overline{x}\;\exists^{\leq 1}\,\overline{y}\;G(\overline{x},\overline{y}). Bounded preimage: There exists N\in\mathbb{N} such that, for every {\mathcal{M}}\in\mathcal{C} and every parameter tuple \overline{y} , \bigl|\{\,\overline{x}\mid{\mathcal{M}}\models G(\overline{x},\overline{y})\,\}\bigr|\;\leq\;N. We refer to \overline{x} as the domain variables and to \overline{y} as the image variables of G . The dimension of G is the number of variables in \overline{y} . Intuition. A reparameterization replaces the original parameters \overline{x} by auxiliary parameters \overline{y} , while preserving the interpreted domain. The bounded preimage condition ensures that each choice of \overline{y} corresponds to only a uniformly bounded number of \overline{x} . If \varphi(\bar{x}) admits a reparameterization with d image variables, then any interpretation whose domain is defined by \varphi can be reduced to a d -dimensional point interpretation (see Proposition 2 ). Bojańczyk [ 2 ] studied polyregular functions , namely string-to-string functions defined by MSO interpretations. He proved that it is decidable whether an \mathit{MSO} formula admits a d -dimensional reparameterization over finite words. In this work, we generalize this result to arbitrary countable labelled chains. The paper is organized as follows. In Section 2 we recall standard notions concerning chains and monadic second-order logic, and introduce the basic tools of the composition method used throughout the paper. In Section 3 we recall the notion of interpretation and motivate the reparameterization problem by showing how d -dimensional reparameterizations yield d -dimensional interpretations. Section 4 contains our main result, showing that it is decidable whether an \mathit{MSO} formula admits a d -dimensional reparameterization over the class of countable chains. In Section 5 , following Bojańczyk [ 2 ] , we study the growth rate of \mathit{MSO} interpretations. Extending results of [ 2 , 4 ] , we show that the growth rate is polynomial, with degree equal to the minimal reparameterization dimension. Due to space limitations, we provide only proof sketches. 2 Preliminaries Here we recall standard notions concerning chains and monadic second-order logic [ 6 , 5 , 10 ] , and introduce the basic tools of the composition method [ 8 , 5 ] used throughout the paper. 2.1 Chains A k -chain is a structure \mathcal{M}=(M,<,\overline{P}), where (M,<) is a linear order and \overline{P}=(P_{1},\dots,P_{k}) is a k -tuple of unary (monadic) predicates on M . When k is clear from the context, we simply refer to \mathcal{M} as a chain or a labelled chain . An interval I is a subset I\subseteq M such that if b,c\in I and b<d<c then d\in I . We denote by \mathcal{M}\!\upharpoonright I the induced substructure on I . 2.2 Monadic Second-Order Logic We work in monadic second-order logic ( \mathit{MSO} ) over the signature \{<,P_{1},\dots,P_{k}\} , where each P_{i} is a unary (monadic) predicate symbol. First-order variables x,y,\dots range over elements of the domain, and second-order variables X,Y,\dots range over subsets of the domain. The atomic formulas are x<y , x=y , P_{i}(x) , and X(x) . Formulas are built from atomic formulas using Boolean connectives and the quantifiers \exists x , \forall x , \exists X , and \forall X . Definition 2 (Definability) Let \psi(z_{1},\dots,z_{m}) be an \mathit{MSO} formula and let {\mathcal{M}} be a structure with domain D . The relation defined by \psi in {\mathcal{M}} is the set \psi^{{\mathcal{M}}}:=\{(a_{1},\dots,a_{m})\in D^{m}\mid{\mathcal{M}}\models\psi(a_{1},\dots,a_{m})\}. A relation R\subseteq D^{m} is said to be \mathit{MSO} -definable in {\mathcal{M}} if there exists an \mathit{MSO} formula \psi(z_{1},\dots,z_{m}) such that R=\psi^{{\mathcal{M}}} . We use standard abbreviations. In particular, \exists^{\geq N}x\,\varphi(x) expresses that there are at least N distinct elements satisfying \varphi(x) . 2.3 Types The quantifier rank {\mathrm{qr}}(\varphi) of an \mathit{MSO} formula \varphi is the maximal nesting depth of quantifiers. For r,k\in\mathbb{N} , let {\mathfrak{Form}^{r}_{k}} be the set of \mathit{MSO} sentences of quantifier rank at most r over the signature \sigma_{k}=\{<,P_{1},\dots,P_{k}\} . For chains \mathfrak{A} and \mathfrak{B} , write \mathfrak{A}\equiv^{r}_{k}\mathfrak{B} if \mathfrak{A} and \mathfrak{B} satisfy the same formulas in {\mathfrak{Form}^{r}_{k}} . This is an equivalence relation with finitely many classes. Lemma 1 (Hintikka) For every r,k\in\mathbb{N} there exists a finite, effectively computable set H^{r}_{k}\subseteq{\mathfrak{Form}^{r}_{k}} such that: 1. The disjunction \bigvee_{\tau\in H^{r}_{k}}\tau is valid. 2. If \tau,\tau^{\prime}\in H^{r}_{k} are distinct, then \tau\wedge\tau^{\prime} is unsatisfiable. 3. Moreover, given \varphi\in{\mathfrak{Form}^{r}_{k}} , one can effectively compute a set H_{\varphi}\subseteq H^{r}_{k} such that \varphi is equivalent to the disjunction of the formulas in H_{\varphi} . By (1) and (2), every \sigma_{k} -structure \mathfrak{A} satisfies a unique sentence \tau\in H^{r}_{k} . We denote this sentence by {\mathrm{type}^{r}_{k}}(\mathfrak{A}) and call it the (r,k) -type of \mathfrak{A} . Moreover, {\mathrm{type}^{r}_{k}}(\mathfrak{A}) effectively determines which sentences in {\mathfrak{Form}^{r}_{k}} are satisfied in \mathfrak{A} . When k is clear from the context, we write {\mathrm{type}^{r}}(\mathfrak{A}) and call it the r -type of \mathfrak{A} . For an interval I of a chain \mathfrak{A} , we write {\mathrm{type}^{r}}(I) for the r -type of the induced substructure \mathfrak{A}\!\upharpoonright I . 2.4 Concatenation of Chains and Sum of Types Given \ell -chains \mathfrak{A} and \mathfrak{B} , their sum (or concatenation ) \mathfrak{A}+\mathfrak{B} is obtained by placing \mathfrak{A} before \mathfrak{B} . More generally, for a finite sequence of \ell -chains \mathfrak{A}_{1},\dots,\mathfrak{A}_{n} , we write \sum_{i=1}^{n}\mathfrak{A}_{i} for their sum [ 8 ] . The next proposition implies that the r

Read the complete text