---
_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: <i>Proceedings of the 29th International Colloquium on Automata,
    Languages and Programming</i>. Vol 2380. Springer; 2002:644-656. doi:<a href="https://doi.org/10.1007/3-540-45465-9_55">10.1007/3-540-45465-9_55</a>'
  apa: 'Henzinger, T. A., Krishnan, S., Kupferman, O., &#38; Mang, F. (2002). Synthesis
    of uninitialized systems. In <i>Proceedings of the 29th International Colloquium
    on Automata, Languages and Programming</i> (Vol. 2380, pp. 644–656). Malaga, Spain:
    Springer. <a href="https://doi.org/10.1007/3-540-45465-9_55">https://doi.org/10.1007/3-540-45465-9_55</a>'
  chicago: Henzinger, Thomas A, Sriram Krishnan, Orna Kupferman, and Freddy Mang.
    “Synthesis of Uninitialized Systems.” In <i>Proceedings of the 29th International
    Colloquium on Automata, Languages and Programming</i>, 2380:644–56. Springer,
    2002. <a href="https://doi.org/10.1007/3-540-45465-9_55">https://doi.org/10.1007/3-540-45465-9_55</a>.
  ieee: T. A. Henzinger, S. Krishnan, O. Kupferman, and F. Mang, “Synthesis of uninitialized
    systems,” in <i>Proceedings of the 29th International Colloquium on Automata,
    Languages and Programming</i>, 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.” <i>Proceedings
    of the 29th International Colloquium on Automata, Languages and Programming</i>,
    vol. 2380, Springer, 2002, pp. 644–56, doi:<a href="https://doi.org/10.1007/3-540-45465-9_55">10.1007/3-540-45465-9_55</a>.
  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'
...