--- _id: '4471' abstract: - lang: eng text: 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. acknowledgement: 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. alternative_title: - LNCS article_processing_charge: No author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Sriram full_name: Krishnan, Sriram last_name: Krishnan - first_name: Orna full_name: Kupferman, Orna last_name: Kupferman - first_name: Freddy full_name: Mang, Freddy last_name: Mang citation: ama: 'Henzinger TA, Krishnan S, Kupferman O, Mang F. Synthesis of uninitialized systems. In: Proceedings of the 29th International Colloquium on Automata, Languages and Programming. Vol 2380. Springer; 2002:644-656. doi:10.1007/3-540-45465-9_55' apa: 'Henzinger, T. A., Krishnan, S., Kupferman, O., & Mang, F. (2002). Synthesis of uninitialized systems. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming (Vol. 2380, pp. 644–656). Malaga, Spain: Springer. https://doi.org/10.1007/3-540-45465-9_55' chicago: Henzinger, Thomas A, Sriram Krishnan, Orna Kupferman, and Freddy Mang. “Synthesis of Uninitialized Systems.” In Proceedings of the 29th International Colloquium on Automata, Languages and Programming, 2380:644–56. Springer, 2002. https://doi.org/10.1007/3-540-45465-9_55. ieee: T. A. Henzinger, S. Krishnan, O. Kupferman, and F. Mang, “Synthesis of uninitialized systems,” in Proceedings of the 29th International Colloquium on Automata, Languages and Programming, Malaga, Spain, 2002, vol. 2380, pp. 644–656. ista: 'Henzinger TA, Krishnan S, Kupferman O, Mang F. 2002. Synthesis of uninitialized systems. Proceedings of the 29th International Colloquium on Automata, Languages and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 2380, 644–656.' mla: Henzinger, Thomas A., et al. “Synthesis of Uninitialized Systems.” Proceedings of the 29th International Colloquium on Automata, Languages and Programming, vol. 2380, Springer, 2002, pp. 644–56, doi:10.1007/3-540-45465-9_55. short: T.A. Henzinger, S. Krishnan, O. Kupferman, F. Mang, in:, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, Springer, 2002, pp. 644–656. conference: end_date: 2002-07-13 location: Malaga, Spain name: 'ICALP: Automata, Languages and Programming' start_date: 2002-07-08 date_created: 2018-12-11T12:09:01Z date_published: 2002-06-26T00:00:00Z date_updated: 2023-06-05T08:05:13Z day: '26' doi: 10.1007/3-540-45465-9_55 extern: '1' intvolume: ' 2380' language: - iso: eng month: '06' oa_version: None page: 644 - 656 publication: Proceedings of the 29th International Colloquium on Automata, Languages and Programming publication_identifier: isbn: - '9783540438649' publication_status: published publisher: Springer publist_id: '257' quality_controlled: '1' scopus_import: '1' status: public title: Synthesis of uninitialized systems type: conference user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 2380 year: '2002' ...