2026-10-01T23:07:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26578 2026-09-24T00:11:13Z ddc:004 open_access

From Sets to Points: Simplifying MSO Interpretations via Reparameterizations Rabinovich, Alexander Monadic Second-Order Logic MSO interpretation interpretation simplification reparameterization decidability We study the conditions under which monadic second-order (MSO) interpretations can be simplified by replacing representations of elements as tuples of arbitrary sets with representations as tuples of finite sets or points. Using reparameterizations of MSO formulas, we prove that for formulas with free finite-set variables, it is decidable whether a point reparameterization exists, and that such a reparameterization can be effectively constructed over countable chains. Moreover, over countable Dedekind-complete labeled chains, a formula with free arbitrary set variables admits a finite-set reparameterization if and only if it has at most countably many satisfying assignments. These results yield effective simplification procedures for MSO interpretations over broad classes of countable linear orders. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Rabinovich 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.189 urn:nbn:de:0030-drops-265789 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.189 eng https://creativecommons.org/licenses/by/4.0/legalcode