License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2017.15
URN: urn:nbn:de:0030-drops-76863
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7686/
Go to the corresponding LIPIcs Volume Portal

Boudou, Joseph

Decidable Logics with Associative Binary Modalities

pdf-format:
LIPIcs-CSL-2017-15.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{boudou:LIPIcs:2017:7686,
  author =	{Joseph Boudou},
  title =	{{Decidable Logics with Associative Binary Modalities}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Valentin Goranko and Mads Dam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7686},
  URN =		{urn:nbn:de:0030-drops-76863},
  doi =		{10.4230/LIPIcs.CSL.2017.15},
  annote =	{Keywords: modal logics, abstract separation logics, team semantics, resource logics, substructural logics}
}

Keywords: modal logics, abstract separation logics, team semantics, resource logics, substructural logics
Collection: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Issue Date: 2017
Date of publication: 16.08.2017

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