2026-07-21T21:12:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12697 2024-03-06T10:50:36Z ddc:004 open_access

Register Transducers Are Marble Transducers Douéneau-Tabot, Gaëtan Filiot, Emmanuel Gastin, Paul streaming string transducer two-way transducer marbles pebbles Deterministic two-way transducers define the class of regular functions from words to words. Alur and Cerný introduced an equivalent model of transducers with registers called copyless streaming string transducers. In this paper, we drop the "copyless" restriction on these machines and show that they are equivalent to two-way transducers enhanced with the ability to drop marks, named "marbles", on the input. We relate the maximal number of marbles used with the amount of register copies performed by the streaming string transducer. Finally, we show that the class membership problems associated with these models are decidable. Our results can be interpreted in terms of program optimization for simple recursive and iterative programs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gaëtan Douéneau-Tabot and Emmanuel Filiot and Paul Gastin 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.29 urn:nbn:de:0030-drops-126979 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.29 eng https://creativecommons.org/licenses/by/3.0/legalcode