Distributed reactive systems are hard to synthesize
Top Cited Papers
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 746-757
- https://doi.org/10.1109/fscs.1990.89597
Abstract
The problem of synthesizing a finite-state distributed reactive system is considered. Given a distributed architecture A, which comprises several processors P/sub 1/, . . ., P/sub k/ and their interconnection scheme, and a propositional temporal specification phi , a solution to the synthesis problem consists of finite-state programs Pi /sub 1/, . . ., Pi /sub k/ (one for each processor), whose joint (synchronous) behavior maintains phi against all possible inputs from the environment. Such a solution is referred to as the realization of the specification phi over the architecture A. Specifically, it is shown that the problem of realizing a given propositional specification over a given architecture is undecidable, and it is nonelementarily decidable for the very restricted class of hierarchical architectures. An extensive characterization of architecture classes for which the realizability problem is elementarily decidable and of classes for which it is undecidable is given.Keywords
This publication has 9 references indexed in Scilit:
- On the synthesis of a reactive modulePublished by Association for Computing Machinery (ACM) ,1989
- A framework for the synthesis of reactive modulesPublished by Springer Nature ,1988
- The complexity of two-player games of incomplete informationJournal of Computer and System Sciences, 1984
- Synthesis of Communicating Processes from Temporal Logic SpecificationsACM Transactions on Programming Languages and Systems, 1984
- Using branching time temporal logic to synthesize synchronization skeletonsScience of Computer Programming, 1982
- A Deductive Approach to Program SynthesisACM Transactions on Programming Languages and Systems, 1980
- Multiple-person alternationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- The emptiness problem for automata on infinite treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1972
- Automata on Infinite Objects and Church’s ProblemCBMS Regional Conference Series in Mathematics, 1972