2026-07-23T06:06:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6249 2024-03-06T10:37:53Z ddc:004 open_access

Minimizing Resources of Sweeping and Streaming String Transducers Baschenis, Félix Gauwin, Olivier Muscholl, Anca Puppis, Gabriele word transducers streaming 2-way sweeping transducers minimization We consider minimization problems for natural parameters of word transducers: the number of passes performed by two-way transducers and the number of registers used by streaming transducers. We show how to compute in ExpSpace the minimum number of passes needed to implement a transduction given as sweeping transducer, and we provide effective constructions of transducers of (worst-case optimal) doubly exponential size. We then consider streaming transducers where concatenations of registers are forbidden in the register updates. Based on a correspondence between the number of passes of sweeping transducers and the number of registers of equivalent concatenation-free streaming transducers, we derive a minimization procedure for the number of registers of concatenation-free streaming transducers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Félix Baschenis and Olivier Gauwin and Anca Muscholl and Gabriele Puppis 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.114 urn:nbn:de:0030-drops-62496 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.114 eng https://creativecommons.org/licenses/by/3.0/legalcode