License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2022.14
URN: urn:nbn:de:0030-drops-172611
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17261/
Go to the corresponding LIPIcs Volume Portal

Benerecetti, Massimo ; Mogavero, Fabio ; Peron, Adriano

Taming Strategy Logic: Non-Recurrent Fragments

pdf-format:
LIPIcs-TIME-2022-14.pdf (0.8 MB)

Abstract

Strategy Logic (SL for short) is one of the prominent languages for reasoning about the strategic abilities of agents in a multi-agent setting. This logic extends LTL with first-order quantifiers over the agent strategies and encompasses other formalisms, such as ATL* and CTL*. The model-checking problem for SL and several of its fragments have been extensively studied. On the other hand, the picture is much less clear on the satisfiability front, where the problem is undecidable for the full logic. In this work, we study two fragments of One-Goal SL, where the nesting of sentences within temporal operators is constrained. We show that the satisfiability problem for these logics, and for the corresponding fragments of ATL* and CTL*, is ExpSpace and PSpace-Complete, respectively.

BibTeX - Entry

@InProceedings{benerecetti_et_al:LIPIcs.TIME.2022.14,
  author =	{Benerecetti, Massimo and Mogavero, Fabio and Peron, Adriano},
  title =	{{Taming Strategy Logic: Non-Recurrent Fragments}},
  booktitle =	{29th International Symposium on Temporal Representation and Reasoning (TIME 2022)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-262-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{247},
  editor =	{Artikis, Alexander and Posenato, Roberto and Tonetta, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17261},
  URN =		{urn:nbn:de:0030-drops-172611},
  doi =		{10.4230/LIPIcs.TIME.2022.14},
  annote =	{Keywords: Strategic Reasoning, Multi-Agent Systems, Temporal Logics, Satisfiability}
}

Keywords: Strategic Reasoning, Multi-Agent Systems, Temporal Logics, Satisfiability
Collection: 29th International Symposium on Temporal Representation and Reasoning (TIME 2022)
Issue Date: 2022
Date of publication: 29.10.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI