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.
Copyless Cost Register Automata: Bounded Ambiguity vs Determinism Cost register automata (CRA) are machines reading an input word while computing values using write-only registers: values from registers are combined using the two operations, as well as the constants, of a semiring. As special case of semirings is the one of languages over an output alphabet: then, CRAs are able to model relations (or functions) between words. These are a generalization of the streaming string transducers (where only the concatenation operation, the multiplication operation of the semiring, is used). Particularly interesting is the subclass of copyless CRAs where the content of a register cannot be used twice for updating the registers. Originally deterministic, non-deterministic variant of CRAs may also be defined: the semantics is then obtained by combining the values of all accepting runs with the additive operation of the semiring (as for weighted automata). The talk will show how finitely-ambiguous copyless non-deterministic CRAs (i.e. the ones that admit a bounded number of accepting runs on every input word) can be effectively transformed into an equivalent copyless (deterministic) CRA, without requiring any specific property on the semiring. As a corollary, this also shows that regular look-ahead can effectively be removed from copyless CRAs.
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.
|Janusz Schmude and Rafał Stefański||16.10-17.10|