Computing Weakest Strategies for Safety Games of Imperfect Information

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

    4 Citations (Scopus)
    122 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 languageEnglish
    Title of host publicationTools and Algorithms for the Construction and Analysis of Systems
    Subtitle of host publication15th International Conference, TACAS 2009, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, York, UK, March 22-29, 2009, Proceedings
    EditorsStefan Kowalewski, Anna Philippou
    Place of PublicationBerlin, Heidelberg
    PublisherSpringer
    Pages92-106
    Number of pages15
    ISBN (Electronic)978-3-642-00768-2
    ISBN (Print)978-3-642-00767-5
    DOIs
    Publication statusPublished - Mar 2009
    Event15th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2009 - York, United Kingdom
    Duration: 22 Mar 200929 Mar 2009
    Conference number: 15

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    Volume5505
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349
    NameTheoretical Computer Science and General Issues
    PublisherSpringer
    ISSN (Print)2512-2010
    ISSN (Electronic)2512-2029

    Conference

    Conference15th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2009
    Abbreviated titleTACAS
    Country/TerritoryUnited Kingdom
    CityYork
    Period22/03/0929/03/09

    Keywords

    • Controller synthesis
    • Imperfect information
    • Safety games
    • CR-I.1.2
    • CR-D.2.2
    • n/a OA procedure

    Fingerprint

    Dive into the research topics of 'Computing Weakest Strategies for Safety Games of Imperfect Information'. Together they form a unique fingerprint.

    Cite this