On the Complexity of Fragments of Horn Modal Logics

 

Abstract

Modal logic is a paradigm for several useful and applicable formal systems in computer science, and, in particular, for temporal logics of various kinds. It generally retains the low complexity of classical propositional logic, but notable exceptions exist that present higher complexity or are even undecidable. In search of computationally well-behaved fragments, clausal forms and other sub-propositional restrictions of temporal and description logics have been recently studied. It is known that the Horn fragments of the modal logics between K and S4 are PSPACE-complete, keeping the same complexity of the the full propositional versions. In this paper, inspired by similar results in the temporal case, we sharpen the above result by showing that if we allow only box modalities in the language the Horn fragments of the modal logics between K and S4 become P-complete. Exploring the innermost reasons for the tractability of sub-Horn modal logics is a necessary condition to understand the behaviour of more expressive temporal and spatial languages under similar restrictions.

Citation

Please, cite this work as:

[BMS16] D. Bresolin, E. Mu~noz-Velasco, and G. Sciavicco. “On the Complexity of Fragments of Horn Modal Logics”. In: 23rd International Symposium on Temporal Representation and Reasoning, TIME 2016, Kongens Lyngby, Denmark, October 17-19, 2016. Ed. by C. E. Dyreson, M. R. Hansen and L. Hunsberger. IEEE Computer Society, 2016, pp. 186-195. DOI: 10.1109/TIME.2016.27. URL: https://doi.org/10.1109/TIME.2016.27.

BibTeX

@InProceedings{Bresolin2016,
     author = {Davide Bresolin and Emilio Mu~noz-Velasco and Guido Sciavicco},
     booktitle = {23rd International Symposium on Temporal Representation and Reasoning, {TIME} 2016, Kongens Lyngby, Denmark, October 17-19, 2016},
     title = {On the Complexity of Fragments of Horn Modal Logics},
     year = {2016},
     editor = {Curtis E. Dyreson and Michael R. Hansen and Luke Hunsberger},
     pages = {186–195},
     publisher = {{IEEE} Computer Society},
     bibsource = {dblp computer science bibliography, https://dblp.org},
     biburl = {https://dblp.org/rec/conf/time/BresolinMS16.bib},
     doi = {10.1109/TIME.2016.27},
     timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
     url = {https://doi.org/10.1109/TIME.2016.27},
}

Bibliometric data

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

On the Complexity of Fragments of Horn Modal Logics

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.

[3] P. A. Wałęga. “Hybrid fragments of Halpern–Shoham logic and their expressive power”. In: Theoretical Computer Science 797 (Dec. 2019), p. 102–128. ISSN: 0304-3975. DOI: 10.1016/j.tcs.2019.01.014. URL: http://dx.doi.org/10.1016/j.tcs.2019.01.014.