Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.120
URN: urn:nbn:de:0030-drops-28589
URL: https://drops.dagstuhl.de/opus/volltexte/2010/2858/
Da Costa, Arnaud ; Laroussinie, François ; Markey, Nicolas
ATL with Strategy Contexts: Expressiveness and Model Checking
| pdf-format: |
|
Abstract
We study the alternating-time temporal logics ATL and ATL* extended with strategy contexts: these make agents commit to their strategies during the evaluation of formulas, contrary to plain ATL and ATL* where strategy quantifiers reset previously selected strategies. We illustrate the important expressive power of strategy contexts by proving that they make the extended logics, namely ATLsc and ATLsc*, equally expressive: any formula in ATLsc* can be translated into an equivalent, linear-size ATLsc formula. Despite the high expressiveness of these logics, we~prove that their model-checking problems remain decidable by~designing a tree-automata-based algorithm for model-checking ATLsc* on the full class of $n$-player concurrent game structures.
BibTeX - Entry
@InProceedings{dacosta_et_al:LIPIcs:2010:2858,
author = {Arnaud Da Costa and Fran{\c{c}}ois Laroussinie and Nicolas Markey},
title = {{ATL with Strategy Contexts: Expressiveness and Model Checking}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
pages = {120--132},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-23-1},
ISSN = {1868-8969},
year = {2010},
volume = {8},
editor = {Kamal Lodaya and Meena Mahajan},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2858},
URN = {urn:nbn:de:0030-drops-28589},
doi = {10.4230/LIPIcs.FSTTCS.2010.120},
annote = {Keywords: alternating temporal logic, agent, strategy quantifier}
}
| Keywords: | alternating temporal logic, agent, strategy quantifier | |
| Seminar: | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) | |
| Issue date: | 2010 | |
| Date of publication: | 14.12.2010 |
