The beautiful and robust theory of regular languages 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.
I will describe a class of string-to-string transducers, which goes beyond
rational or regular functions, but still shares many of their good properties
(e.g. the inverse image of a regular language is regular). Unlike many
string-to-string transducer models (including sequential, rational and
regular transducers), which have linear size increase, the the new class
(called polyregular functions) has polynomial size increase.
The main selling point of the polyregular functions is that they admit
numerous equivalent descriptions: (a) automata with pebbles; (b) a fragment
of lambda calculus; (c) a fragment of for-programs; (d) compositions of
certain atomic functions, such as reverse or a form of string squaring;
(e) mso string-to-string interpretations.
Reversible Transducers Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms for composing two-way transducers cause a double exponential blow-up in the size of the inputs. In this talk, I will present the class of reversible transducers, which are machines that are both deterministic and co-deterministic. This class enjoys polynomial composition complexity, even in the two-way case. Although this class is not very expressive in the one-way scenario, I will show that any two-way transducer can be made reversible through a single exponential blow-up. As a consequence, the composition of two-way transducers can be done with a single exponential blow-up in the number of states, enhancing the known algorithm from the 60s.
A Ramsey Theorem for Finite Semigroups Pumping Lemmas are powerful tools in the study of abstract machines. They can be used, for instance, to prove that a language is not recognisable by some model of computation, or to guarantee the existence of small witnesses of non-emptiness. The usual way of proving such a lemma is to show a behaviour that (1) has good properties with respect to iteration, and (2) is guaranteed to appear in long enough computations. For example, for finite state automata, the notion of loop, i.e., repetition of state, satisfies these two conditions. In this talk, we will see that loops can be formalised as idempotent elements of finite semigroups, and that this notion can be adapted to more complicated models of computation while still satisfying both previously mentioned conditions, yielding new Pumping Lemmas. On one hand, idempotent elements allow the characterisation of iterable behaviours in diverse settings where loops fail to do so, for instance automata that use all of the runs over a given input to determine the corresponding outcome (e.g. alternating automata, weighted automata), or automata having more complex input or output structures (e.g. two-way automata, streaming string transducers, cost register automata). On the other hand, idempotent factors are guaranteed to occur in long enough sequences of elements of a finite semigroup. While this is an immediate consequence of Ramsey's theorem or Simon's factorisation forest theorem, we will see that a better bound can be obtained, using a parameter of semigroups called the regular J-length.
Combinatorics for transducers made easy Transducers are to automata as relations are to languages: they are devices that not only specify a set of valid inputs, but also associate with them some corresponding outputs. Despite similarities with automaton models, transducers are less well-behaved, both in terms of expressive power and in terms and algorithmic complexity. An additional complication lies in the combinatorics that emerge when analysing the recognized relations. The first part of the talk will survey some classical decidability results on transducers that feature simple enough combinatorics on words. The focus will then turn towards a few more complex results, that require handling systems of word equations. I will explain how one can take advantage of a standard encoding of words by polynomials and reduce the apparently difficult combinatorial problems to simple arguments based on commutative algebra.