Repository logo
  • Log In
    Log in via Symplectic to deposit your publication(s).
Repository logo
  • Communities & Collections
  • Research Outputs
  • Statistics
  • Log In
    Log in via Symplectic to deposit your publication(s).
  1. Home
  2. Faculty of Engineering
  3. Computing
  4. Computing
  5. A Hennessy-Milner theorem for ATL with imperfect information
 
  • Details
A Hennessy-Milner theorem for ATL with imperfect information
OA Location
https://arxiv.org/pdf/2006.15000
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
URI
http://hdl.handle.net/10044/1/112134
URL
https://dl.acm.org/doi/10.1145/3373718.3394784
DOI
https://www.dx.doi.org/10.1145/3373718.3394784
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
About
Spiral Depositing with Spiral Publishing with Spiral Symplectic
Contact us
Open access team Report an issue
Other Services
Scholarly Communications Library Services
logo

Imperial College London

South Kensington Campus

London SW7 2AZ, UK

tel: +44 (0)20 7589 5111

Accessibility Modern slavery statement Cookie Policy

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback