On Sub-Propositional Fragments of Modal Logic

 

Abstract

In this paper, we consider the well-known modal logics $\mathbf{K}$, $\mathbf{T}$, $\mathbf{K4}$, and $\mathbf{S4}$, and we study some of their sub-propositional fragments, namely the classical Horn fragment, the Krom fragment, the so-called core fragment, defined as the intersection of the Horn and the Krom fragments, plus their sub-fragments obtained by limiting the use of boxes and diamonds in clauses. We focus, first, on the relative expressive power of such languages: we introduce a suitable measure of expressive power, and we obtain a complex hierarchy that encompasses all fragments of the considered logics. Then, after observing the low expressive power, in particular, of the Horn fragments without diamonds, we study the computational complexity of their satisfiability problem, proving that, in general, it becomes polynomial.

Citation

Please, cite this work as:

[BMS18] D. Bresolin, E. Mu~noz-Velasco, and G. Sciavicco. “On Sub-Propositional Fragments of Modal Logic”. In: Log. Methods Comput. Sci. 14.2 (2018). DOI: 10.23638/LMCS-14(2:16)2018. URL: https://doi.org/10.23638/LMCS-14(2:16)2018.

BibTeX

@Article{Bresolin2018,
     author = {Davide Bresolin and Emilio Mu~noz-Velasco and Guido Sciavicco},
     journal = {Log. Methods Comput. Sci.},
     title = {On Sub-Propositional Fragments of Modal Logic},
     year = {2018},
     number = {2},
     volume = {14},
     bibsource = {dblp computer science bibliography, https://dblp.org},
     biburl = {https://dblp.org/rec/journals/lmcs/BresolinMS18.bib},
     doi = {10.23638/LMCS-14(2:16)2018},
     timestamp = {Wed, 07 Dec 2022 00:00:00 +0100},
     url = {https://doi.org/10.23638/LMCS-14(2:16)2018},
}

Bibliometric data

The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.

0

CITATIONS

0 Total citations

0 Recent citations

0 Field Citation Ratio

n/a Relative Citation Ratio

• Citations
• Scopus - Citation Indexes: 4

• Captures
• Mendeley - Readers: 5

-

see details

See more details

Posted by 3 X users

5 readers on Mendeley

Cites

The following graph plots the number of cites received by this work from its publication, on a yearly basis.

Papers citing this work

The following is a non-exhaustive list of papers that cite this work:

[1] M. Dziubiński. “Modal context restriction for multiagent BDI logics”. In: Artificial Intelligence Review 55.4 (Oct. 2021), p. 3075–3151. ISSN: 1573-7462. DOI: 10.1007/s10462-021-10064-6. URL: http://dx.doi.org/10.1007/s10462-021-10064-6.

[2] P. A. Wałęga. “Computational Complexity of Core Fragments of Modal Logics T, K4, and S4”. In: Logics in Artificial Intelligence. Springer International Publishing, 2019, p. 744–759. ISBN: 9783030195700. DOI: 10.1007/978-3-030-19570-0_48. URL: http://dx.doi.org/10.1007/978-3-030-19570-0_48.