The Complexity of Transducer Synthesis from Multi-Sequential Specifications
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- The first reactive synthesis competition (SYNTCOMP 2014)International Journal on Software Tools for Technology Transfer, 2016
- Delay Games with WMSO+U Winning ConditionsRAIRO - Theoretical Informatics and Applications, 2016
- Multi-sequential Word Relations2015
- Exploiting structure in LTL synthesisInternational Journal on Software Tools for Technology Transfer, 2012
- Antichains and compositional algorithms for LTL synthesisFormal Methods in System Design, 2011
- Strategy logicInformation and Computation, 2010
- Squaring transducers: an efficient procedure for deciding functionality and sequentialityTheoretical Computer Science, 2003
- Symbolic Algorithms for Infinite-State Games2001
- The complexity of decision problems for finite-turn multicounter machinesJournal of Computer and System Sciences, 1981
- Classification of formal languages by functional binary transductionsInformation and Control, 1969