@inproceedings{4632,
  abstract     = {We present a compositional trace-based model for probabilistic systems. The behavior of a system with probabilistic choice is a stochastic process, namely, a probability distribution on traces, or “bundle.” Consequently, the semantics of a system with both nondeterministic and probabilistic choice is a set of bundles. The bundles of a composite system can be obtained by combining the bundles of the components in a simple mathematical way. Refinement between systems is bundle containment. We achieve assume-guarantee compositionality for bundle semantics by introducing two scoping mechanisms. The first mechanism, which is standard in compositional modeling, distinguishes inputs from outputs and hidden state. The second mechanism, which arises in probabilistic systems, partitions the state into probabilistically independent regions.},
  author       = {De Alfaro, Luca and Henzinger, Thomas A and Jhala, Ranjit},
  booktitle    = {Proceedings of the 12th International Conference on on Concurrency Theory},
  isbn         = {9783540424970},
  location     = {Aalborg, Denmark},
  pages        = {351 -- 365},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Compositional methods for probabilistic systems}},
  doi          = {10.1007/3-540-44685-0_24},
  volume       = {2154},
  year         = {2001},
}

@inproceedings{4633,
  abstract     = {A procedure for the analysis of state spaces is called symbolic if it manipulates not individual states, but sets of states that are represented by constraints. Such a procedure can be used for the analysis of infinite state spaces, provided termination is guaranteed. We present symbolic procedures, and corresponding termination criteria, for the solution of infinite-state games, which occur in the control and modular verification of infinite-state systems. To characterize the termination of symbolic procedures for solving infinite-state games, we classify these game structures into four increasingly restrictive categories:
1  	Class 1 consists of infinite-state structures for which all safety and reachability games can be solved.
2  	Class 2 consists of infinite-state structures for which all ω-regular games can be solved.
3  	Class 3 consists of infinite-state structures for which all nested positive boolean combinations of ω-regular games can be solved.
4  	Class 4 consists of infinite-state structures for which all nested boolean combinations of ω-regular games can be solved.
We give a structural characterization for each class, using equivalence relations on the state spaces of games which range from game versions of trace equivalence to a game version of bisimilarity. We provide infinite-state examples for all four classes of games from control problems for hybrid systems. We conclude by presenting symbolic algorithms for the synthesis of winning strategies (“controller synthesis”) for infinitestate games with arbitrary ω-regular objectives, and prove termination over all class-2 structures. This settles, in particular, the symbolic controller synthesis problem for rectangular hybrid systems.},
  author       = {De Alfaro, Luca and Henzinger, Thomas A and Majumdar, Ritankar},
  booktitle    = {Proceedings of the 12th International Conference on on Concurrency Theory},
  isbn         = {9783540424970},
  location     = {Aalborg, Denmark},
  pages        = {536 -- 550},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Symbolic algorithms for infinite-state games}},
  doi          = {10.1007/3-540-44685-0_36},
  volume       = {2154},
  year         = {2001},
}

@inproceedings{4634,
  abstract     = {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.},
  author       = {De Alfaro, Luca and Henzinger, Thomas A and Mang, Freddy},
  booktitle    = {Proceedings of the 12th International Conference on on Concurrency Theory},
  isbn         = {9783540424970},
  location     = {Aalborg, Denmark},
  pages        = {566 -- 581},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{The control of synchronous systems, Part II}},
  doi          = {10.1007/3-540-44685-0_38},
  volume       = {2154},
  year         = {2001},
}