Trends in Transformations

Speakers

Determinization of transducers over real numbers

We consider one-way transducers that realize real number functions. We show that if the real function is continuous, the transducer can be made input-deterministic up to a change of the digit set used in the output. This is very similar to Avižienis numeration system used to perform sequences of additions. This is joint work with Alexis Bès and Christian Choffrut.

Membership problems for Pebble Transducers

Deterministic pebble transducers are two-way transducers enhanced with the ability to drop a bounded number of pebbles on their input. They describe a robust class of string-to-string functions, named "polyregular functions". Two variants of the model have been recently investigated: marble transducers (where the transducer drops "marbles instead of "pebbles", with a slightly different semantics) and blind transducers (also named "comparison-free pebble transducers" in the literature). This talk surveys some of the recent results concerning these three models, with a focus on membership problems. Intuitively, such problems correspond to "program optimization" issues which given a "complex" program, ask whether there exist a "simpler" one which has the same behavior. We shall for instance ask if given a pebble transducer which uses k pebbles, there exists an equivalent transducer using only k-1 pebbles. Similar questions can be formulated for marble or blind transducers. We can also ask if a pebble transducer can be transformed in a blind or a marble transducer. Some of these problems have recently been solved, while others are still open.

Comparison-free polyregular functions

This talk is based on our ICALP 2021 paper, in which we introduced a new automata-theoretic class of string-to-string functions with polynomial growth. Several equivalent definitions are provided: a machine model which is a restricted variant of pebble transducers, and a few inductive definitions that close the class of regular functions under certain operations. As their name suggests, these "comparison-free polyregular functions" form a subclass of polyregular functions; we prove that the inclusion is strict. We also show that they are incomparable with HDT0L transductions, closed under usual function composition – but not under a certain "map" combinator – and satisfy a pebble minimization theorem. If time allows, I will also discuss connections with definable string-to-string functions in the simply-typed linear λ-calculus.

Unambiguity, Functionality, and Computability in Transducer Theory

In the first part of the talk, we survey some known results. In more detail, we show that (one-way) transducers have the uniformization property, that is, every relation recognized by a (one-way) transducer contains a function with equal domain that can be recognized by a functional - even unambiguous - (one way) transducer. Going into the setting of rational transducers over finite words, we show that unambiguity can be traded for determinism at the price of two-wayness. Uniformization is closely related to synthesis. The synthesis problem asks to automatically generate, if it exists, an implementation from a specification (aka. relation) of correct input-output pairs. We consider the synthesis of computable functions for a classical Turing computability notion from rational relations. The above uniformization result yields that from every rational transducer (over finite or infinite words) an unambiguous transducer can be synthesized. While for finite words unambiguity implies computability, this is no longer true for infinite words. In the second part of the talk, we show that synthesis of computable functions from rational relations over infinite words is undecidable. We provide a sound semi-decision procedure that is complete for a large subclass of rational relations, namely deterministic rational relations which contains the class of automatic (aka. synchronous) relations. The second part of the talk is based on work with Emmanuel Filiot.