December 2, 2024
Lê Thành Dũng (Tito) Nguyễn (CNRS, Université Aix-Marseille)Polyregular functions are the class of string-to-string functions definable by pebble transducers, an extension of finite-state automata with outputs and multiple two-way reading heads (pebbles) with a stack discipline. If a polyregular function can be computed with k pebbles, then its output length is bounded by a polynomial of degree k in the input length. But Bojańczyk has shown that the converse fails.
In this talk, I will sketch an easier proof of a stronger statement: for every k, there exists some polyregular function with quadratic growth whose output language differs from that of any k-fold composition of macro tree transducers, i.e. of any safe order-k tree transducer, and which therefore cannot be computed by a k-pebble transducer. Actually there is no need to know what these tree transducers are: the proof uses as a black box a powerful “bridge theorem” of Engelfriet and Maneth.
In fact, the proof of the bridge theorem implicitly uses a linearity argument, in the sense of linear logic. If time allows, I will briefly mention some ongoing work with Paweł Parys to extend this theorem to unsafe higher-order transducers, using a variant of the Taylor expansion of λ-terms and semi-quantitative coherence spaces.
Joint work with Sandra Kiefer and Cécilia Pradic: https://arxiv.org/abs/2301.09234