Synthesis of uninitialized systems

T.A. Henzinger, S. Krishnan, O. Kupferman, F. Mang, in:, Springer, 2002, pp. 644–656.

No fulltext has been uploaded. References only!

Conference Paper | Published
Henzinger, Thomas AIST Austria ; Krishnan, Sriram C; Kupferman, Orna; Mang, Freddy Y
Series Title
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.
Publishing Year
Date Published
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

Cite this

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.
Henzinger, Thomas A, Sriram Krishnan, Orna Kupferman, and Freddy Mang. “Synthesis of Uninitialized Systems,” 2380:644–56. Springer, 2002.
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.


Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar