2026-07-22T14:20:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10682 2024-03-06T10:46:27Z ddc:004 open_access

String-to-String Interpretations With Polynomial-Size Output (Track B: Automata, Logic, Semantics, and Theory of Programming) Bojańczyk, Mikołaj Kiefer, Sandra Lhote, Nathan MSO interpretations pebble transducers polyregular functions String-to-string MSO interpretations are like Courcelle’s MSO transductions, except that a single output position can be represented using a tuple of input positions instead of just a single input position. In particular, the output length is polynomial in the input length, as opposed to MSO transductions, which have output of linear length. We show that string-to-string MSO interpretations are exactly the polyregular functions. The latter class has various characterisations, one of which is that it consists of the string-to-string functions recognised by pebble transducers. Our main result implies the surprising fact that string-to-string MSO interpretations are closed under composition. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikołaj Bojańczyk and Sandra Kiefer and Nathan Lhote 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.106 urn:nbn:de:0030-drops-106821 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.106 eng https://creativecommons.org/licenses/by/3.0/legalcode