2026-07-21T23:34:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23964 2025-08-18T14:14:19Z ddc:004 open_access

Reversible Pebble Transducers Dartois, Luc Gastin, Paul Germerie Guizouarn, Loïc Krishna, Shankaranarayanan Transducers Polyregular functions Reversibility Composition Uniformization Deterministic two-way transducers with pebbles (aka pebble transducers) capture the class of polyregular functions, which extend the string-to-string regular functions allowing polynomial growth instead of linear growth. One of the most fundamental operations on functions is composition, and (poly)regular functions can be realized as a composition of several simpler functions. In general, composition of deterministic two-way transducers incur a doubly exponential blow-up in the size of the inputs. A major improvement in this direction comes from the fundamental result of Dartois et al. [Luc Dartois et al., 2017] showing a polynomial construction for the composition of reversible two-way transducers. A precise complexity analysis for existing composition techniques of pebble transducers is missing. But they rely on the classic composition of two-way transducers and inherit the double exponential complexity. To overcome this problem, we introduce reversible pebble transducers. Our main results are efficient uniformization techniques for non-deterministic pebble transducers to reversible ones and efficient composition for reversible pebble transducers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luc Dartois and Paul Gastin and Loïc Germerie Guizouarn and Shankaranarayanan Krishna 2025 Is Part Of LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2025.14 urn:nbn:de:0030-drops-239645 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.14 eng https://creativecommons.org/licenses/by/4.0/legalcode