Open Systems in Reactive Environments: Control and Synthesis
Orna Kupferman5 
, P. Madhusudan6 , P. S. Thiagarajan7 and Moshe Y. Vardi8
| (5) |
Hebrew University, Israel |
| (6) |
The Institute of Mathematical Sciences, India |
| (7) |
Chennai Mathematical Institute, India |
Abstract
We study the problems of synthesizing open systems as well as controllers for them. The key aspect of our model is that it
caters to reactive environments, which can disable different sets of responses when reacting with the system. We deal with specifications given as formulas
in CTL* and its sub-logic CTL. We show that both these problems, with specifications in CTL (CTL*), are 2EXPTIME-complete
(resp. 3EXPTIME-complete). Thus, in a sense, reactive environments constitute a provably harder setting for the synthesis
of open systems and controllers for them.
For a full version of this extended abstract, see Technical Report TCS-2000-03, Chennai Mathematical Institute, available
at www.smi.ernet.in
On leave visiting Informatik VII, RWTH-Aachen, Germany
Supported in part by NSF grant CCR-9700061, and by a grant from the Intel Corporation.
References secured to subscribers.