  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 implementation $f: I \rightarrow O$ which (1) fulfils the
specification, i.e., $(i,f(i))\in S$ for all $i\in I$, and (2) can be defined
by some input-deterministic (aka sequential) transducer $\mathcal{T}_f$. If
such an implementation $f$ exists, the procedure should also output
$\mathcal{T}_f$. The realisability problem is the corresponding decision
problem.
  For specifications given by synchronous transducers (which read and write
alternately one symbol), this is the finite variant of the classical synthesis
problem on $\omega$-words, solved by B\"uchi and Landweber in 1969, and the
realisability problem is known to be ExpTime-c in both finite and $\omega$-word
settings. For specifications given by asynchronous transducers (which can write
a batch of symbols, or none, in a single step), the realisability problem is
known to be undecidable.
  We consider here the class of multi-sequential specifications, defined as
finite unions of sequential transducers over possibly incomparable domains. We
provide optimal decision procedures for the realisability problem in both the
synchronous and asynchronous setting, showing that it is PSpace-c. Moreover,
whenever the specification is realisable, we expose the construction of a
sequential transducer that realises it and has a size that is doubly
exponential, which we prove to be optimal.
