OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

A Logic of Sights

Dégremont, Cédric and Paul, Soumya and Asher, Nicholas A Logic of Sights. (2017) Journal of Logic and Computation, 27 (4). 1225-1305. ISSN 0955-792X

[img]
Preview
(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
1MB

Official URL: https://doi.org/10.1093/logcom/exv077

Abstract

We study labeled transition systems where at each state an agent is aware of and hence reasons about only a part of the entire system (called the ‘sight’). We develop a logic for such systems: the ‘logic of sights’. We explore its model theory, give an axiomatization and prove its completeness. We show that the logic is a fragment of the loosely guarded fragment of first-order logic. We show that the satisfiability problem of the logic is PSPACE-complete and the combined complexity of its model-checking problem is in PTIME. Finally we discuss its relation to other logics as well as extensions.

Item Type:Article
Additional Information:Thanks to Oxford University Press. The original PDF is available at: https://academic.oup.com/logcom/article-abstract/27/4/1225/2917849?
HAL Id:hal-01659308
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - INPT (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UPS (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Funders:
ERC grant no 269427
Statistics:download
Deposited By: IRIT IRIT
Deposited On:27 Nov 2017 10:32

Repository Staff Only: item control page