The beautiful and robust theory of regular l anguages is based on four fundamental pillars : expressions, automata, logic and algebra. The class of languages denoted by regular expressions corresponds to the class of languages recognized by finite state automata, to the class of languages definable in monadic second order logic (MSO) with one successor, and to the class of languages whose syntactic monoid is finite. Extensions of the pillars of language theory to transformations (functions or relations) from words has been an active area of research recently. The aim of this workshop is to bring together researchers and students interested in theory and applications of formal models of transformations.
In the past, we have had 2 editions of Trends as part of FSTTCS 2018 and FSTTCS 2019. This year, we bring you some interesting talks, which highlight the latest trends in this area, both from a theoretical as well as a practical perspective.
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.
13.30-13.40 : Introduction; 13.40-14.30- Sarah; 14.35-15.25-Olivier; 15.30-16.00 - Break; 16.00-16.50 - Nguyễn; 16.55-17.45 - Gaëtan; 17.50-18.00 - Closing