Word transducers extend finite-state automata with outputs and define binary relations over words. They were studied since the early stages of automata theory, but recent developments introduced more powerful models and new computational problems. In this thesis we focus on decision problems for word transducers with origin semantics, a semantics which was proposed recently and makes transducers better-behaved in terms of canonicity and decidability. In particular, we propose regular resynchronizers as a mean to compare word transducers in the origin semantics in a more relaxed way, and show that various problems remain decidable in this setting.

English
LaBRI (visioconférence ou présentiel suivant la situation sanitaire)