---
_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'
...