We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Undecidability of the transitive graded modal logic with converse.
- Authors
ZOLIN, EVGENY
- Abstract
We extend the language of the modal logic K4 of transitive frames with two sorts of modalities. In addition to the usual possibility modality (which means that a formula holds in some successor of a given point), we consider graded modalities (a formula holds in at least n successors) and converse graded modalities (a formula holds in at least n predecessors). We show that the resulting logic, GrIK4, is both locally and globally undecidable. The same result is obtained for all logics between GrIK4 and its reflexive companion GrIS4 and for some other modal logics. As a consequence, for the 'unrestricted version' of the description logic 풮I풬, the problem of concept satisfiability (even with respect to the empty terminology) is undecidable. We also give a survey of results on the local and global decidability, complexity, and the finite model property for fragments of GrIK4.
- Subjects
MODAL logic; DESCRIPTION logics; TENSE (Logic); NONCLASSICAL mathematical logic; PREDICATE (Logic)
- Publication
Journal of Logic & Computation, 2017, Vol 27, Issue 5, p1399
- ISSN
0955-792X
- Publication type
Article
- DOI
10.1093/logcom/exw026