Computing Weakest Strategies for Safety Games of Imperfect Information

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    4 Citations (Scopus)
    73 Downloads (Pure)

    Abstract

    CEDAR (Counter Example Driven Antichain Refinement) is a new symbolic algorithm for computing weakest strategies for safety games of imperfect information. The algorithm computes a fixed point over the lattice of contravariant antichains. Here contravariant antichains are antichains over pairs consisting of an information set and an allow set representing the associated move. We demonstrate how the richer structure of contravariant antichains for representing antitone functions, as opposed to standard antichains for representing sets of downward closed sets, allows CEDAR to apply a significantly less complex controllable predecessor step than previous algorithms.
    Original languageUndefined
    Title of host publicationTools and Algorithms for the Construction and Analysis of Systems
    EditorsS. Kowalewski, A. Philippou
    Place of PublicationBerlin / Heidelberg
    PublisherSpringer
    Pages92-106
    Number of pages15
    ISBN (Print)978-3-642-00767-5
    DOIs
    Publication statusPublished - Mar 2009

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    Volume5505
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Keywords

    • Controller synthesis
    • CR-D.2.2
    • safety games
    • CR-I.1.2
    • imperfect information

    Cite this

    Kuijper, W., & van de Pol, J. C. (2009). Computing Weakest Strategies for Safety Games of Imperfect Information. In S. Kowalewski, & A. Philippou (Eds.), Tools and Algorithms for the Construction and Analysis of Systems (pp. 92-106). [10.1007/978-3-642-00768-2_10] (Lecture Notes in Computer Science; Vol. 5505). Berlin / Heidelberg: Springer. https://doi.org/10.1007/978-3-642-00768-2_10