文章基本信息

标题：Decidable Logics with Associative Binary Modalities
本地全文：下载
作者：Joseph Boudou
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：82
页码：15:1-15:15
DOI：10.4230/LIPIcs.CSL.2017.15
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：modal logics; abstract separation logics; team semantics; resource logics; substructural logics