pith. sign in

arxiv: 2605.18248 · v2 · pith:G7NHMWM6new · submitted 2026-05-18 · 💻 cs.LO

Decidability of MSO Reparameterization over Countable Chains

Alexander Rabinovich This is my paper

Pith reviewed 2026-05-20 08:23 UTC · model grok-4.3

classification 💻 cs.LO
keywords MSOreparameterizationdecidabilitylinear ordersinterpretationsmonadic second-order logiccountable chainspoint interpretations
0
0 comments X

The pith

It is decidable whether a given MSO formula admits a d-dimensional reparameterization over countable labelled linear orders.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies multidimensional point interpretations in monadic second-order logic, where elements of a target structure are encoded as tuples from a host structure. It focuses on the problem of reducing the dimension of these encodings through reparameterization. The central result establishes that, when the host structures are countable labelled linear orders, there is an algorithm to decide if a given MSO formula permits such a dimension reduction. A sympathetic reader would care because this turns an otherwise open simplification question into a computable check, directly enabling equivalent but lower-dimensional logical definitions of interpretations.

Core claim

Our main result shows that, over the class of countable labelled linear orders, it is decidable whether a given MSO formula admits a d-dimensional reparameterization. As a consequence, every interpretation whose domain admits such a reparameterization is equivalent to a d-dimensional point interpretation.

What carries the argument

Reparameterization, the formal device that reduces the tuple dimension of an MSO-defined point interpretation while preserving the interpreted structure up to equivalence.

If this is right

  • Every interpretation whose domain admits a d-dimensional reparameterization is equivalent to a d-dimensional point interpretation.
  • The decidability result supplies an effective procedure for determining whether a given MSO interpretation on countable chains can be simplified.
  • Simplification preserves logical equivalence between the original and the reduced interpretations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same decision method could be tested on finite linear orders or on other fragments of MSO to see whether the restriction to countable chains is essential.
  • If reparameterization decisions are computable here, similar algorithmic questions may become tractable for interpretations defined by weaker logics such as FO.
  • Automated simplification of interpretations might reduce the state space in model-checking tools that rely on MSO encodings of data words or trees.

Load-bearing premise

The chosen definition of reparameterization together with the restriction to countable labelled linear orders is what makes a decision procedure possible.

What would settle it

An explicit MSO formula on a countable labelled linear order together with a dimension d for which the existence of a reparameterization is undecidable would falsify the main claim.

read the original abstract

Interpretations are a fundamental tool in mathematical logic, allowing structures to be encoded within other structures via logical definitions. We study $\MSO$ \emph{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 \emph{reparameterization}. Our main result shows that, over the class of countable labelled linear orders, it is decidable whether a given $\MSO$ formula admits a $d$-dimensional reparameterization. As a consequence, every interpretation whose domain admits such a reparameterization is equivalent to a $d$-dimensional point interpretation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that over countable labelled linear orders, it is decidable whether a given MSO formula admits a d-dimensional reparameterization. As a consequence, every interpretation whose domain admits such a reparameterization is equivalent to a d-dimensional point interpretation.

Significance. If the central decidability result holds, it supplies a concrete algorithmic tool for dimension reduction in MSO interpretations on chains, building on standard automata and composition techniques for MSO over linear orders. This could streamline proofs of equivalence between structures and aid classification results in the theory of interpretations.

major comments (2)
  1. [§4.2] §4.2, the reduction in the proof of Theorem 4.3: the construction of the automaton for reparameterization existence encodes the original formula but does not explicitly verify that the new d-tuples remain within the countable chain; the argument appears to assume without loss that the order type is preserved under the reparameterization map.
  2. [Definition 3.1] Definition 3.1: the notion of reparameterization is defined via an MSO formula φ' that relates the original and new parameters, yet the equivalence claim in Corollary 5.1 only shows domain equivalence; it is not shown that the interpreted relations are preserved when the dimension drops, which is load-bearing for the stated consequence.
minor comments (2)
  1. [Introduction] The introduction would benefit from a small concrete example (e.g., a 2-dimensional interpretation of (ℕ,+) that reduces to 1-dimensional) to illustrate the reparameterization notion before the general theorem.
  2. [§2.1] Notation for labelled linear orders in §2.1 leaves the alphabet size implicit; clarifying whether the alphabet is fixed or part of the input would make the decidability statement sharper.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below, providing clarifications where the existing arguments can be strengthened and indicating the revisions we will make.

read point-by-point responses

  1. Referee: [§4.2] §4.2, the reduction in the proof of Theorem 4.3: the construction of the automaton for reparameterization existence encodes the original formula but does not explicitly verify that the new d-tuples remain within the countable chain; the argument appears to assume without loss that the order type is preserved under the reparameterization map.

    Authors: We thank the referee for this observation. In the proof of Theorem 4.3 the automaton is constructed to recognize reparameterizations defined by an MSO formula φ' (per Definition 3.1) whose satisfying assignments are tuples drawn from the universe of the given countable labelled linear order. Because the semantics of MSO over linear orders evaluate all quantifiers inside the host structure, the new d-tuples are automatically elements of that same chain. Order-type preservation follows directly from the requirement in Definition 3.1 that φ' defines an order-preserving bijection between the original and reparameterized parameter tuples. We will insert a short clarifying paragraph immediately after the automaton construction to make this restriction explicit. revision: yes

  2. Referee: [Definition 3.1] Definition 3.1: the notion of reparameterization is defined via an MSO formula φ' that relates the original and new parameters, yet the equivalence claim in Corollary 5.1 only shows domain equivalence; it is not shown that the interpreted relations are preserved when the dimension drops, which is load-bearing for the stated consequence.

    Authors: We agree that the preservation of the interpreted relations must be stated explicitly for the consequence claimed in Corollary 5.1. Because every relation of the interpreted structure is itself defined by an MSO formula over the original parameters, one can uniformly substitute the reparameterizing formula φ' into those definitions; the resulting formulas remain MSO and define the same relations on the reparameterized domain. To make this step fully transparent we will add a brief lemma (Lemma 5.2) in Section 5 that records the composition and thereby establishes equivalence of the full interpretations, not merely of their domains. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes a decidability theorem for whether an MSO formula admits a d-dimensional reparameterization over countable labelled linear orders, with the consequence that qualifying interpretations are equivalent to d-dimensional point interpretations. This result is derived using standard techniques for MSO on chains (automata or composition methods) applied to the restricted class of structures, without any reduction of the central claim to fitted parameters, self-definitional constructs, or load-bearing self-citations. The derivation is self-contained against external logical benchmarks, and the restriction to countable labelled linear orders supplies independent decidability infrastructure rather than circularly presupposing the target property.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard background definitions of MSO logic and linear orders without introducing new free parameters or invented entities.

axioms (1)
  • standard math MSO logic and interpretations on labelled linear orders obey standard semantic definitions from mathematical logic.
    Invoked implicitly when defining reparameterization and equivalence of interpretations.

pith-pipeline@v0.9.0 · 5641 in / 1220 out tokens · 39631 ms · 2026-05-20T08:23:33.100766+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Expressing cardinality quantifiers in monadic second-order logic over chains , journal =

    Vince Barany and. Expressing cardinality quantifiers in monadic second-order logic over chains , journal =. 2011 , doi =

    work page 2011

  2. [2]

    On the Growth Rates of Polyregular Functions , booktitle =

    Miko. On the Growth Rates of Polyregular Functions , booktitle =. 2023 , doi =

    work page 2023

  3. [3]

    The Structure of Polynomial Growth for Tree Automata/Transducers and

    Paul Gallot and Nathan Lhote and L. The Structure of Polynomial Growth for Tree Automata/Transducers and. To appear in TheoretiCS , year =

    work page

  4. [4]

    2025 , eprint=

    The structure of polynomial growth for tree automata/transducers and MSO set queries , author=. 2025 , eprint=

    work page 2025

  5. [5]

    , title =

    Tarski, Alfred and Mostowski, Andrzej and Robinson, Raphael M. , title =

    work page

  6. [6]

    Notre Dame Journal of Formal Logic , volume =

    Friedman, Harvey , title =. Notre Dame Journal of Formal Logic , volume =. 1973 , url =

    work page 1973

  7. [7]

    2007 , note =

    Friedman, Harvey , title =. 2007 , note =

    work page 2007

  8. [8]

    Decidability of second-order theories and automata on infinite trees , volume =

    Rabin, Michael O , journal =. Decidability of second-order theories and automata on infinite trees , volume =

    work page

  9. [9]

    The monadic theory of order , volume =

    Shelah, Saharon , journal =. The monadic theory of order , volume =

    work page

  10. [10]

    Monadic second-order theories , year =

    Gurevich, Yuri , journal =. Monadic second-order theories , year =

    work page

  11. [11]

    Automata on infinite objects , year =

    Thomas, Wolfgang , booktitle =. Automata on infinite objects , year =

    work page

  12. [12]

    ICALP 2026 , series =

    Alexander Rabinovich , title =. ICALP 2026 , series =

    work page 2026