Henzinger, Thomas AIST Austria ; Krishnan, Sriram C ; Kupferman, Orna ; Mang, Freddy Y
The sequential synthesis problem, which is closely related to Church’s solvability problem, asks, given a specification in the form of a binary relation between input and output streams, for the construction of a finite-state stream transducer that converts inputs to appropriate outputs. For efficiency reasons, practical sequential hardware is often designed to operate without prior initialization. Such hardware designs can be modeled by uninitialized state machines, which are required to satisfy their specification if started from any state. In this paper we solve the sequential synthesis problem for uninitialized systems, that is, we construct uninitialized finite-state stream transducers. We consider specifications given by LTL formulas, deterministic, nondeterministic, universal, and alternating Büchi automata. We solve this uninitialized synthesis problem by reducing it to the well-understood initialized synthesis problem. While our solution is straightforward, it leads, for some specification formalisms, to upper bounds that are exponentially worse than the complexity of the corresponding initialized problems. However, we prove lower bounds to show that our simple solutions are optimal for all considered specification formalisms. We also study the problem of deciding whether a given specification is uninitialized, that is, if its uninitialized and initialized synthesis problems coincide. We show that this problem has, for each specification formalism, the same complexity as the equivalence problem.
This research was supported in part by the SRC contract 99-TJ-683.003, the DARPA contract NAG2-1214, and the NSF grant CCR-9988172.
644 - 656
ICALP: Automata, Languages and Programming
Henzinger TA, Krishnan S, Kupferman O, Mang F. Synthesis of uninitialized systems. In: Vol 2380. Springer; 2002:644-656. doi:10.1007/3-540-45465-9_55
Henzinger, T. A., Krishnan, S., Kupferman, O., & Mang, F. (2002). Synthesis of uninitialized systems (Vol. 2380, pp. 644–656). Presented at the ICALP: Automata, Languages and Programming, Springer. https://doi.org/10.1007/3-540-45465-9_55
Henzinger, Thomas A, Sriram Krishnan, Orna Kupferman, and Freddy Mang. “Synthesis of Uninitialized Systems,” 2380:644–56. Springer, 2002. https://doi.org/10.1007/3-540-45465-9_55.
T. A. Henzinger, S. Krishnan, O. Kupferman, and F. Mang, “Synthesis of uninitialized systems,” presented at the ICALP: Automata, Languages and Programming, 2002, vol. 2380, pp. 644–656.
Henzinger TA, Krishnan S, Kupferman O, Mang F. 2002. Synthesis of uninitialized systems. ICALP: Automata, Languages and Programming, LNCS, vol. 2380. 644–656.
Henzinger, Thomas A., et al. Synthesis of Uninitialized Systems. Vol. 2380, Springer, 2002, pp. 644–56, doi:10.1007/3-540-45465-9_55.