Chennai Mathematical Institute

Seminars




3:30 - 4:30 pm, Seminar Hall
Resynchronizers for Word Transducers with Origin Information

Sougata Bose
LaBRI, University of Bordeaux, France.
06-01-20


Abstract

Transducers are machines that transform input word to output word. Origin semantics for transducers annotates every symbol of the output with information about the input position responsible for producing it. Origin semantics allows to recover decidability for containment problem, which is known to be undecidable in the classical semantics. We consider a variant of the containment problem, where the origins of the transducers are allowed to be different up to some resynchronization relation. We look at different ways to define the resynchronization relation. Resynchronization for one-way transducers was introduced by Filiot et al. in 2016. We introduce MSO-resynchronizers for a more general class of transducers. We also consider the problem of synthesizing a resynchronization that makes two classically equivalent transducers origin-equivalent. We show decidability in the functional case. However the problem remains undecidable in general.

This talk is based on joint works with Anca Muscholl, Vincent Penelle, Gabriele Puppis and Krishna S.