Exibard, Léo ;
Filiot, Emmanuel ;
Jecker, Ismaël
The Complexity of Transducer Synthesis from MultiSequential Specifications
Abstract
The transducer synthesis problem on finite words asks, given a specification S subseteq I x O, where I and O are sets of finite words, whether there exists an implementation f: I  > 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 inputdeterministic (aka sequential) transducer T_f. If such an implementation f exists, the procedure should also output 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 omegawords, solved by Büchi and Landweber in 1969, and the realisability problem is known to be ExpTimec in both finite and omegaword 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 multisequential 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 PSpacec. 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.
BibTeX  Entry
@InProceedings{exibard_et_al:LIPIcs:2018:9628,
author = {L{\'e}o Exibard and Emmanuel Filiot and Isma{\"e}l Jecker},
title = {{The Complexity of Transducer Synthesis from MultiSequential Specifications}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {46:146:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9628},
URN = {urn:nbn:de:0030drops96286},
doi = {10.4230/LIPIcs.MFCS.2018.46},
annote = {Keywords: Transducers, MultiSequentiality, Synthesis}
}
27.08.2018
Keywords: 

Transducers, MultiSequentiality, Synthesis 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

27.08.2018 