On the Complexity of Graded Modal Logics with Converse.

Bartosz BednarczykBartosz Bednarczyk, Emanuel KierońskiEmanuel Kieroński, Piotr WitkowskiPiotr Witkowski

ISBN: 978-3-030-19569-4
Download
DOI Link

Bartosz Bednarczyk, Emanuel Kieroński, Piotr Witkowski
On the Complexity of Graded Modal Logics with Converse.
In Francesco Calimeri, Nicola Leone, Marco Manna, eds., Proceedings of Logics in Artificial Intelligence - 16th European Conference (JELIA 2019), volume 11468 of LNCS, 642--658, May 2019. Lecture Notes in Computer Science

Details
Bibtex

KurzfassungAbstract
A complete classification of the complexity of the local and global satisfiability problems for graded modal language over traditional classes of frames has already been established. By 'traditional' classes of frames we mean those characterized by any positive combination of reflexivity, seriality, symmetry, transitivity, and the Euclidean property. In this paper we fill the gaps remaining in an analogous classification of the graded modal language with graded converse modalities. In particular we show its NExpTime-completeness over the class of Euclidean frames, demonstrating this way that over this class the considered language is harder than the language without graded modalities or without converse modalities. We also consider its variation disallowing graded converse modalities, but still admitting basic converse modalities. Our most important result for this variation is confirming an earlier conjecture that it is decidable over transitive frames. This contrasts with the undecidability of the language with graded converse modalities.
Weitere Informationen unter:Further Information: Link
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{DBLP:conf/jelia/BednarczykK019,
  author    = {Bartosz Bednarczyk and
               Emanuel Kieronski and
               Piotr Witkowski},
  title     = {On the Complexity of Graded Modal Logics with Converse},
  booktitle = {Logics in Artificial Intelligence - 16th European Conference, {JELIA}
               2019, Rende, Italy, May 7-11, 2019, Proceedings},
  pages     = {642--658},
  year      = {2019},
  crossref  = {DBLP:conf/jelia/2019},
  url       = {https://doi.org/10.1007/978-3-030-19570-0\_42},
  doi       = {10.1007/978-3-030-19570-0\_42},
  timestamp = {Fri, 31 May 2019 09:51:35 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/jelia/BednarczykK019},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/jelia/2019,
  editor    = {Francesco Calimeri and
               Nicola Leone and
               Marco Manna},
  title     = {Logics in Artificial Intelligence - 16th European Conference, {JELIA}
               2019, Rende, Italy, May 7-11, 2019, Proceedings},
  series    = {Lecture Notes in Computer Science},
  volume    = {11468},
  publisher = {Springer},
  year      = {2019},
  url       = {https://doi.org/10.1007/978-3-030-19570-0},
  doi       = {10.1007/978-3-030-19570-0},
  isbn      = {978-3-030-19569-4},
  timestamp = {Tue, 14 May 2019 10:00:44 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/jelia/2019},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}