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

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.

Bookmark the permalink.