The Complexity of Transducer Synthesis from Multi-Sequential Specifications

Léo Exibard, Emmanuel Filiot, Ismaël Jecker

The transducer synthesis problem on finite words asks, given a specification $S\subseteq I\times O$, where $I$ and $O$ are sets of finite words, whether there exists an implement…