Stochastic Game Logic

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

Abstract

Stochastic game logic (SGL) is a new temporal logic that combines features of alternating temporal logic (to formalize the individual views and cooperation and reaction facilities of agents in a multiplayer game), probabilistic computation tree logic and extended temporal logic (to reason about qualitative and quantitative, linear or branching time winning objectives). The paper presents the syntax and semantics of SGL and discusses its model checking problem. The model checking problem of SGL turns out to be undecidable when the strategies are history-dependent. We show PSPACE completeness for memoryless deterministic strategies and the EXPSPACE upper bound for memoryless randomized strategies. For the qualitative fragment of SGL we show PSPACE completeness for memoryless strategies.

Details

Original languageEnglish
Title of host publicationQEST'07: Proceedings of the Fourth International Conference on the Quantitative Evaluation of Systems
PublisherIEEE Computer Society, Washington
Pages227-236
Number of pages10
ISBN (print)978-0-7695-2883-0, 0-7695-2883-X
Publication statusPublished - 17 Sept 2007
Peer-reviewedYes

Conference

Title4th International Conference on the Quantitative Evaluation of SysTems
Abbreviated titleQEST 2007
Conference number4
Duration16 - 19 September 2007
Website
Degree of recognitionInternational event
LocationUniversity of Edinburgh
CityEdinburgh
CountryUnited Kingdom

External IDs

Scopus 47949130647
ORCID /0000-0002-5321-9343/work/205988096

Keywords

Keywords

  • Stochastic processes, Probabilistic logic, Stochastic systems, Informatics, Upper bound, Automata