Synchronized word relations

Diego Figueira
Friday, 11 May, 2018 - 14:00
ULB La Plaine NO, Salle Solvay
A natural approach to defining binary word relations over a finite alphabet A is through two-tape finite state automata, which can be seen as regular languages L over the alphabet {1,2} x A, where (i,a) is interpreted as reading letter a from tape i. Thus, a word w of the language L denotes the pair (u_1,u_2) in A* x A* in which u_i is the projection of w onto i-labelled letters. While this formalism defines the well-studied class of Rational relations due to Nivat’s Theorem (a.k.a. non-deterministic finite state transducers), enforcing restrictions on the reading regime from the tapes, that we call synchronization, yields various sub-classes of relations. Such synchronization restrictions are imposed through regular properties on the projection of the language onto {1,2}. In this way, for each regular language C contained in {1,2}*, one obtains a class Rel(C) of relations, such as the classes of Regular, Recognizable, or length-preserving rational relations, as well as (infinitely) many other classes. I will show some recent results on this collection of classes of relations, based on joint work with Leonid Libkin, María Emilia Descotte, Gabriele Puppis and Santiago Figueira.