2026-07-18T05:22:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26558 2026-07-01T07:16:15Z ddc:004 open_access

Transducers on Compressed Strings Bojańczyk, Mikołaj Lohrey, Markus polyregular functions grammar compression We study string-to-string functions which are compatible with compression in the following sense: given a compressed representation of an input string, one can compute in polynomial time a compressed representation of the output string. As the compression formalism, we use straight-line programs (i.e. context-free grammars that produce only one string). As the functions, we use finite state transducers, with a focus on the regular and polyregular functions. We show that all regular functions are compatible with compression, but this is no longer true for the polyregular functions. We identify a subclass of the polyregular functions - the so-called rectangular polyregular functions - which is compatible with compression, and we characterise this subclass in terms of a functional programming language. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikołaj Bojańczyk and Markus Lohrey 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.170 urn:nbn:de:0030-drops-265580 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.170 eng https://creativecommons.org/licenses/by/4.0/legalcode