Computing Weakest Strategies for Safety Games of Imperfect Information

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

    4 Citations (Scopus)
    56 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
    Kuijper, W. ; van de Pol, Jan Cornelis. / Computing Weakest Strategies for Safety Games of Imperfect Information. Tools and Algorithms for the Construction and Analysis of Systems. editor / S. Kowalewski ; A. Philippou. Berlin / Heidelberg : Springer, 2009. pp. 92-106 (Lecture Notes in Computer Science).
    @inproceedings{a54ac8507a3c4581afee7e4c45d41de8,
    title = "Computing Weakest Strategies for Safety Games of Imperfect Information",
    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.",
    keywords = "Controller synthesis, CR-D.2.2, safety games, CR-I.1.2, imperfect information",
    author = "W. Kuijper and {van de Pol}, {Jan Cornelis}",
    note = "10.1007/978-3-642-00768-2_10",
    year = "2009",
    month = "3",
    doi = "10.1007/978-3-642-00768-2_10",
    language = "Undefined",
    isbn = "978-3-642-00767-5",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "92--106",
    editor = "S. Kowalewski and A. Philippou",
    booktitle = "Tools and Algorithms for the Construction and Analysis of Systems",

    }

    Kuijper, W & van de Pol, JC 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., 10.1007/978-3-642-00768-2_10, Lecture Notes in Computer Science, vol. 5505, Springer, Berlin / Heidelberg, pp. 92-106. https://doi.org/10.1007/978-3-642-00768-2_10

    Computing Weakest Strategies for Safety Games of Imperfect Information. / Kuijper, W.; van de Pol, Jan Cornelis.

    Tools and Algorithms for the Construction and Analysis of Systems. ed. / S. Kowalewski; A. Philippou. Berlin / Heidelberg : Springer, 2009. p. 92-106 10.1007/978-3-642-00768-2_10 (Lecture Notes in Computer Science; Vol. 5505).

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

    TY - GEN

    T1 - Computing Weakest Strategies for Safety Games of Imperfect Information

    AU - Kuijper, W.

    AU - van de Pol, Jan Cornelis

    N1 - 10.1007/978-3-642-00768-2_10

    PY - 2009/3

    Y1 - 2009/3

    N2 - 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.

    AB - 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.

    KW - Controller synthesis

    KW - CR-D.2.2

    KW - safety games

    KW - CR-I.1.2

    KW - imperfect information

    U2 - 10.1007/978-3-642-00768-2_10

    DO - 10.1007/978-3-642-00768-2_10

    M3 - Conference contribution

    SN - 978-3-642-00767-5

    T3 - Lecture Notes in Computer Science

    SP - 92

    EP - 106

    BT - Tools and Algorithms for the Construction and Analysis of Systems

    A2 - Kowalewski, S.

    A2 - Philippou, A.

    PB - Springer

    CY - Berlin / Heidelberg

    ER -

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