Undecidability of Relation-Changing Modal Logics

C. Areces, R. Fervari, G. Hoffmann, and M. Martel. Undecidability of Relation-Changing Modal Logics. In Dynamic Logic. New Trends and Applications - First International Workshop, DALI 2017, Brasilia, Brazil, September 23-24, 2017, Proceedings, pp. 1–16, 2017.

Download

[pdf] 

Abstract

Relation-changing modal logics are extensions of the basic modal logic that allow to change the accessibility relation of a model during the evaluation of a formula. In particular, they are equipped with dynamic modalities that are able to delete, add and swap edges in the model, both locally and globally. We investigate the satisfiability problem of these logics. We define satisfiability-preserving translations from an undecidable memory logic to relation-changing modal logics. This way we show that their satisfiability problems are undecidable.

BibTeX

@InCollection{Areces2017,
  author =       "C. Areces and R. Fervari and G. Hoffmann and M.
                 Martel",
  booktitle =    "Dynamic Logic. New Trends and Applications - First
                 International Workshop, {DALI} 2017, Brasilia, Brazil,
                 September 23-24, 2017, Proceedings",
  title =        "Undecidability of Relation-Changing Modal Logics",
  year =         "2017",
  pages =        "1--16",
  abstract =     "Relation-changing modal logics are extensions of the
                 basic modal logic that allow to change the
                 accessibility relation of a model during the evaluation
                 of a formula. In particular, they are equipped with
                 dynamic modalities that are able to delete, add and
                 swap edges in the model, both locally and globally. We
                 investigate the satisfiability problem of these logics.
                 We define satisfiability-preserving translations from
                 an undecidable memory logic to relation-changing modal
                 logics. This way we show that their satisfiability
                 problems are undecidable.",
  bibsource =    "dblp computer science bibliography, https://dblp.org",
  biburl =       "https://dblp.org/rec/conf/tableaux/ArecesFHM17.bib",
  doi =          "10.1007/978-3-319-73579-5\_1",
  timestamp =    "Sat, 19 Oct 2019 20:06:19 +0200",
  URL =          "https://doi.org/10.1007/978-3-319-73579-5\_1",
  ISBN =         "978-3-319-73578-8",
}