Transducers are an extension of automata. While automata read some input and in the end either accept or reject the input, transducers additionally produce some output along each transition that is taken. For example, finite transducers and pushdown transducers are an extension of finite (state) automata and pushdown automata, respectively, that additionally output a finite word on each transition. Transducers are used in many fields of computer science, e.g., natural language processing, compiler construction, and synthesis. In order to manipulate transducers, it is important to study their decision problems. Unlike finite automata which enjoy many desirable decidability and closure properties, finite transducers do not. Most notably, equivalence of finite transducers is undecidable. In this talk, we take a look at different kinds of transducers and explore some of their properties.

You can see the slides of the presentation here

Speaker

Sarah Winter is a post-doctoral researcher at Universite libre de Bruxelles (ULB).

Time and Place

Friday 16/12/2022 at 11:30am in M.A.143

Registration

Participation is free, but registration is compulsory. Make sure to fill in this form.

References and Related Reading