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
|
(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 - Toulouse INP (FRANCE) French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE) Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (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 On: | 27 Nov 2017 10:32 |
Repository Staff Only: item control page
