Multi-Sequentiality

The Complexity of Transducer Synthesis from Multi-Sequential Specifications (MFCS 2018)

Multi-sequential specifications are recognised by unions of sequential transducers. Their synthesis problem is PSpace-complete.

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