Henzinger, Thomas AIST Austria ; Jhala, Ranjit; Majumdar, Ritankar S
A major hurdle in the algorithmic verification and control of systems is the need to find suitable abstract models, which omit enough details to overcome the state-explosion problem, but retain enough details to exhibit satisfaction or controllability with respect to the specification. The paradigm of counterexample-guided abstraction refinement suggests a fully automatic way of finding suitable abstract models: one starts with a coarse abstraction, attempts to verify or control the abstract model, and if this attempt fails and the abstract counterexample does not correspond to a concrete counterexample, then one uses the spurious counterexample to guide the refinement of the abstract model. We present a counterexample-guided refinement algorithm for solving ω-regular control objectives. The main difficulty is that in control, unlike in verification, counterexamples are strategies in a game between system and controller. In the case that the controller has no choices, our scheme subsumes known counterexample-guided refinement algorithms for the verification of ω-regular specifications. Our algorithm is useful in all situations where ω-regular games need to be solved, such as supervisory control, sequential and program synthesis, and modular verification. The algorithm is fully symbolic, and therefore applicable also to infinite-state systems.
This research was supported in part by the DARPA SEC grant F33615-C-98-3614, the ONR grant N00014-02-1-0671, and the NSF grants CCR-9988172, CCR-0085949, and CCR-0225610.
886 - 902
ICALP: Automata, Languages and Programming
Henzinger TA, Jhala R, Majumdar R. Counterexample-guided control. In: Vol 2719. Springer; 2003:886-902. doi:10.1007/3-540-45061-0_69
Henzinger, T. A., Jhala, R., & Majumdar, R. (2003). Counterexample-guided control (Vol. 2719, pp. 886–902). Presented at the ICALP: Automata, Languages and Programming, Springer. https://doi.org/10.1007/3-540-45061-0_69
Henzinger, Thomas A, Ranjit Jhala, and Ritankar Majumdar. “Counterexample-Guided Control,” 2719:886–902. Springer, 2003. https://doi.org/10.1007/3-540-45061-0_69.
T. A. Henzinger, R. Jhala, and R. Majumdar, “Counterexample-guided control,” presented at the ICALP: Automata, Languages and Programming, 2003, vol. 2719, pp. 886–902.
Henzinger TA, Jhala R, Majumdar R. 2003. Counterexample-guided control. ICALP: Automata, Languages and Programming, LNCS, vol. 2719, 886–902.
Henzinger, Thomas A., et al. Counterexample-Guided Control. Vol. 2719, Springer, 2003, pp. 886–902, doi:10.1007/3-540-45061-0_69.