2026-07-23T20:16:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1751 2024-03-06T10:33:04Z ddc:004 open_access

Abstraction Refinement for Games with Incomplete Information Dimitrova, Rayna Finkbeiner, Bernd Automatic abstraction refinement synthesis Counterexample-guided abstraction refinement (CEGAR) is used in automated software analysis to find suitable finite-state abstractions of infinite-state systems. In this paper, we extend CEGAR to games with incomplete information, as they commonly occur in controller synthesis and modular verification. The challenge is that, under incomplete information, one must carefully account for the knowledge available to the player: the strategy must not depend on information the player cannot see. We propose an abstraction mechanism for games under incomplete information that incorporates the approximation of the players\' moves into a knowledge-based subset construction on the abstract state space. This abstraction results in a perfect-information game over a finite graph. The concretizability of abstract strategies can be encoded as the satisfiability of strategy-tree formulas. Based on this encoding, we present an interpolation-based approach for selecting new predicates and provide sufficient conditions for the termination of the resulting refinement loop. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rayna Dimitrova and Bernd Finkbeiner 2008 Is Part Of LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2008.1751 urn:nbn:de:0030-drops-17510 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1751 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode