Pith Number

pith:G7NHMWM6

pith:2026:G7NHMWM6OK5RVAPHDTVO3V4S7J

not attested not anchored not stored refs resolved

Decidability of MSO Reparameterization over Countable Chains

Alexander Rabinovich

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

arxiv:2605.18248 v1 · 2026-05-18 · cs.LO

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{G7NHMWM6OK5RVAPHDTVO3V4S7J}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest 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.

C2weakest assumption

The host structures are restricted to countable labelled linear orders and the logic is full MSO; the decidability may fail outside this class or for other logics.

C3one line summary

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

References

12 extracted · 12 resolved · 0 Pith anchors

[1] Expressing cardinality quantifiers in monadic second-order logic over chains , journal = 2011

[2] On the Growth Rates of Polyregular Functions , booktitle = 2023

[3] The Structure of Polynomial Growth for Tree Automata/Transducers and

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

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

Receipt and verification

First computed	2026-05-20T00:05:52.092382Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

37da76599e72bb1a81e71ceaedd792fa71914d663bb53a9a645582109dbcec28

Aliases

arxiv: 2605.18248 · arxiv_version: 2605.18248v1 · doi: 10.48550/arxiv.2605.18248 · pith_short_12: G7NHMWM6OK5R · pith_short_16: G7NHMWM6OK5RVAPH · pith_short_8: G7NHMWM6

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/G7NHMWM6OK5RVAPHDTVO3V4S7J \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 37da76599e72bb1a81e71ceaedd792fa71914d663bb53a9a645582109dbcec28

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "4510401568b4f072e42270aa254f616537f365272ef1c78af08581958862c1d5",
    "cross_cats_sorted": [],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.LO",
    "submitted_at": "2026-05-18T11:48:23Z",
    "title_canon_sha256": "91e407978ea834e3f83c9843875a963ed4da31de38a69f283124562f1c7c54f1"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.18248",
    "kind": "arxiv",
    "version": 1
  }
}