de Alfaro, Luca; Henzinger, Thomas AIST Austria ; Mang, Freddy Y
A controller is an environment for a system that achieves a particular control objective by providing inputs to the system without constraining the choices of the system. For synchronous systems, where system and controller make simultaneous and interdependent choices, the notion that a controller must not constrain the choices of the system can be formalized by type systems for composability. In a previous paper, we solved the control problem for static and dynamic types: a static type is a dependency relation between inputs and outputs, and composition is well-typed if it does not introduce cyclic dependencies; a dynamic type is a set of static types, one for each state. Static and dynamic types, however, cannot capture many important digital circuits, such as gated clocks, bidirectional buses, and random-access memory. We therefore introduce more general type systems, so-called dependent and bidirectional types, for modeling these situations, and we solve the corresponding control problems. In a system with a dependent type, the dependencies between inputs and outputs are determined gradually through a game of the system against the controller. In a system with a bidirectional type, also the distinction between inputs and outputs is resolved dynamically by such a game. The game proceeds in several rounds. In each round the system and the controller choose to update some variables dependent on variables that have already been updated. The solution of the control problem for dependent and bidirectional types is based on algorithms for solving these games.
This research was supported in part by the SRC contract 99-TJ-683.003, the DARPA SEC grant F33615-C-98-3614, the MARCO GSRC grant 98-DT-660, the AFOSR MURI grant F49620-00-1-0327, and the NSF Theory grant CCR-9988172.
566 - 581
CONCUR: Concurrency Theory
De Alfaro L, Henzinger TA, Mang F. The control of synchronous systems, Part II. In: Vol 2154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2001:566-581. doi:10.1007/3-540-44685-0_38
De Alfaro, L., Henzinger, T. A., & Mang, F. (2001). The control of synchronous systems, Part II (Vol. 2154, pp. 566–581). Presented at the CONCUR: Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/3-540-44685-0_38
De Alfaro, Luca, Thomas A Henzinger, and Freddy Mang. “The Control of Synchronous Systems, Part II,” 2154:566–81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2001. https://doi.org/10.1007/3-540-44685-0_38.
L. De Alfaro, T. A. Henzinger, and F. Mang, “The control of synchronous systems, Part II,” presented at the CONCUR: Concurrency Theory, 2001, vol. 2154, pp. 566–581.
De Alfaro L, Henzinger TA, Mang F. 2001. The control of synchronous systems, Part II. CONCUR: Concurrency Theory, LNCS, vol. 2154, 566–581.
De Alfaro, Luca, et al. The Control of Synchronous Systems, Part II. Vol. 2154, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2001, pp. 566–81, doi:10.1007/3-540-44685-0_38.