Separation in C2 and graded modal logic with inverses, nominals and the universal modality is undecidable; without inverses or nominals it is 2ExpTime- or coNExpTime-complete, while definability reduces to validity.
Living without beth and craig: Definitions and interpolants in description and modal logics with nominals and role inclusions
4 Pith papers cite this work, alongside 4 external citations. Polarity classification is still indexing.
4
Pith papers citing it
4
external citations · Crossref
fields
cs.LO 4representative citing papers
Craig interpolants for hybrid modal logics are computable in 4-EXPTIME when they exist, while uniform interpolant existence is undecidable.
Tabular modal logics admit propositionally sized interpolants and strongest implicates iff NP ⊆ P/poly, while non-tabular ones require exponential size unconditionally.
First elementary algorithms to construct ALC-interpolants under ALCH- and ALCQ-ontologies, with size and time bounds that are double and triple exponential.
citing papers explorer
-
Separation and Definability in Fragments of Two-Variable First-Order Logic with Counting
Separation in C2 and graded modal logic with inverses, nominals and the universal modality is undecidable; without inverses or nominals it is 2ExpTime- or coNExpTime-complete, while definability reduces to validity.
-
Computation and Size of Interpolants for Hybrid Modal Logics
Craig interpolants for hybrid modal logics are computable in 4-EXPTIME when they exist, while uniform interpolant existence is undecidable.
-
Computation of Interpolants for Description Logic Concepts in Hard Cases
First elementary algorithms to construct ALC-interpolants under ALCH- and ALCQ-ontologies, with size and time bounds that are double and triple exponential.