Talk by Olivier Carton – Two-way transducers – 18/Jul – 17hs

Time: Wednesday 18 July, 17hs.
Place: Departamento de Computacion, (room to be determined)

Title: Two-way transducers
Speaker: Olivier Carton, Université Paris Diderot

Abstract:
In this talk, we consider two-way transducers with a two-way
output tape. To each cell of the input tape corresponds a cell of the
output tape where the transducer can write a finite word. At each
transition, the transducer reads one cell of the input tape and either
leave unchanged the corresponding cell of the output tape or write a new
word into it, overwriting the previous content. We show that each
relation realized by such a two-way transducer is rational. It can be
realized by a one-way transducer. We also show that any rational function
can be realized by a deterministic two-way transducer.

Olivier Carton is professor at the Université Paris Diderot and member of the
LIAFA and INFINIS (Association between CONICET-UBA/CNRS-Universite
Paris Diderot) laboratories. Olivier Carton is a renowned expert in
automata theory. http://www.liafa.univ-paris-diderot.fr/~carton/

Paper presented at RTA’2012

Eduardo Bonelli, Delia Kesner,  Carlos Lombardi and Alejandro Ríos, presented the paper “Normalisation for Dynamic Pattern Calculi”  in the 23rd International Conference on Rewriting Techniques and Applications (RTA) which was held in Nagoya, Japan, in May-June 2012.