OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Decidable Logics with Associative Binary Modalities

Boudou, Joseph Decidable Logics with Associative Binary Modalities. (2017) In: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), 20 August 2017 - 24 August 2017 (Stockholm, Sweden).

(Document in English)

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

Official URL: https://doi.org/10.4230/LIPIcs.CSL.2017.15


A new family of modal logics with an associative binary modality, called counting logics is proposed. These propositional logics allow to express finite cardinalities of sets and more generally to count the number of subsets satisfying some properties. We show that these logics can be seen both as specializations of the Boolean logic of bunched implications and as generalizations of the propositional dependence logic. Moreover, whereas most logics with an associative binary modality are undecidable, we prove that some counting logics are decidable, in particular the basic counting logic bCL. We conjecture that this interesting result is due to the valuation constraints in counting logics' semantics and prove that the logic corresponding to bCL without these constraints is undecidable. Finally, we give lower and upper bounds for the complexity of bCL's validity problem.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Dagstuhl Research Online Publication Server (DROPS). Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. This papers appears in Leibniz International Proceedings in Informatics : proceedings of CSL 2017 ISBN 978-3-95977-045-3 ESSN: 1868-8969 The definitive version is available at: https://drops.dagstuhl.de/opus/volltexte/2017/7686/
HAL Id:hal-02559759
Audience (conference):International conference proceedings
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:
Deposited On:22 Apr 2020 09:42

Repository Staff Only: item control page