University of Leicester
Browse

Lossy Channel Games under Incomplete Information

Download (116.83 kB)
conference contribution
posted on 2018-06-06, 11:14 authored by Rayna Dimitrova, Bernd Finkbeiner
In this paper we investigate lossy channel games under incomplete information, where two players operate on a finite set of unbounded FIFO channels and one player, representing a system component under consideration operates under incomplete information, while the other player, representing the component's environment is allowed to lose messages from the channels. We argue that these games are a suitable model for synthesis of communication protocols where processes communicate over unreliable channels. We show that in the case of finite message alphabets, games with safety and reachability winning conditions are decidable and finite-state observation-based strategies for the component can be effectively computed. Undecidability for (weak) parity objectives follows from the undecidability of (weak) parity perfect information games where only one player can lose messages.

Funding

This work is partially supported by the DFG as part of SFB/TR 14 AVACS.

History

Citation

Proceedings 1st International Workshop on Strategic Reasoning SR 2013, Electronic Proceedings in Theoretical Computer Science (EPTCS) 2013, 112, pp. 43-51

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Informatics

Source

1st International Workshop on Strategic Reasoning SR 2013, Rome, Italy

Version

  • VoR (Version of Record)

Published in

Proceedings 1st International Workshop on Strategic Reasoning SR 2013

Publisher

Open Publishing Association

issn

2075-2180

Copyright date

2013

Available date

2018-06-06

Publisher version

https://arxiv.org/abs/1303.0790v1

Temporal coverage: start date

2013-03-16

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC