Symbolic algorithms for infinite-state games

L. De Alfaro, T.A. Henzinger, R. Majumdar, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2001, pp. 536–550.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ;
Series Title
LNCS
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.
Publishing Year
Date Published
2001-08-13
Acknowledgement
This research was supported in part by the AFOSR MURI grant F49620-00-1-0327, the DARPA SEC grant F33615-C-98-3614, the MARCO GSRC grant 98-DT-660, the NSF Theory grant CCR-9988172, and the NSF ITR grant CCR-0085949.
Volume
2154
Page
536 - 550
Conference
CONCUR: Concurrency Theory
IST-REx-ID

Cite this

De Alfaro L, Henzinger TA, Majumdar R. Symbolic algorithms for infinite-state games. In: Vol 2154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2001:536-550. doi:10.1007/3-540-44685-0_36
De Alfaro, L., Henzinger, T. A., & Majumdar, R. (2001). Symbolic algorithms for infinite-state games (Vol. 2154, pp. 536–550). Presented at the CONCUR: Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/3-540-44685-0_36
De Alfaro, Luca, Thomas A Henzinger, and Ritankar Majumdar. “Symbolic Algorithms for Infinite-State Games,” 2154:536–50. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2001. https://doi.org/10.1007/3-540-44685-0_36.
L. De Alfaro, T. A. Henzinger, and R. Majumdar, “Symbolic algorithms for infinite-state games,” presented at the CONCUR: Concurrency Theory, 2001, vol. 2154, pp. 536–550.
De Alfaro L, Henzinger TA, Majumdar R. 2001. Symbolic algorithms for infinite-state games. CONCUR: Concurrency Theory, LNCS, vol. 2154. 536–550.
De Alfaro, Luca, et al. Symbolic Algorithms for Infinite-State Games. Vol. 2154, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2001, pp. 536–50, doi:10.1007/3-540-44685-0_36.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar