String-to-String Interpretations with Polynomial-Size Output

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 characterizations, one of which is that it consists of the string-to-string functions recognized by pebble transducers. Our main result implies the surprising fact that string-to-string MSO interpretations are closed under composition. This is joint work with Mikołaj Bojańczyk and Nathan Lhote and the corresponding paper was published at ICALP 2019. (It has not yet been presented at Highlights.)

Authors

• Sandra Kiefer

Keywords

No keywords are indexed for this paper.