A Hennessy-Milner theorem for ATL with imperfect information
OA Location
Author(s)
Belardinelli, Francesco
Dima, Catalin
Malvone, Vadim
Tiplea, Ferucio
Type
Conference Paper
Abstract
We show that a history-based variant of alternating bisimulation with imperfect information allows it to be related to a variant of Alternating-time Temporal Logic (ATL) with imperfect information by a full Hennessy-Milner theorem. The variant of ATL we consider has a common knowledge semantics, which requires that the uniform strategy available for a coalition to accomplish some goal must be common knowledge inside the coalition, while other semantic variants of ATL with imperfect information do not accomodate a Hennessy-Milner theorem. We also show that the existence of a history-based alternating bisimulation between two finite Concurrent Game Structures with imperfect information (iCGS) is undecidable.
Date Issued
2020-07-09
Date Acceptance
2020-07-08
Citation
PROCEEDINGS OF THE 35TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2020), 2020, pp.181-194
ISBN
9781450371049
ISSN
1043-6871
Publisher
ASSOC COMPUTING MACHINERY
Start Page
181
End Page
194
Journal / Book Title
PROCEEDINGS OF THE 35TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2020)
Copyright Statement
Copyright © 2020 ACM
Identifier
https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000665014900016&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=a2bf6146997ec60c407a63945d4e92bb
Source
35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Subjects
ATL
Bisimulation
Computer Science
Computer Science, Theory & Methods
Concurrent Game Structures with Imperfect Information
Gale-Stewart determinacy
Logic
Science & Technology
Science & Technology - Other Topics
Technology
Publication Status
Published
Start Date
2020-07-08
Finish Date
2020-07-11
Coverage Spatial
Online
Date Publish Online
2020-07-08