The complexity of finite model reasoning in description logics

DOI10.1016/j.ic.2004.11.002zbMath1097.03022OpenAlexW2080057244MaRDI QIDQ2486582

Ulrike Sattler, Carsten Lutz, Lidia Tendera

Publication date: 5 August 2005

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2004.11.002

zbMATH Keywords

Description logicNumber restrictionsFinite satisfiability

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Justifications for Description Logic Knowledge Bases Under the Fixed-Domain Semantics ⋮ Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots ⋮ Reasoning about graded strategy quantifiers ⋮ Query Answering in Description Logics: The Knots Approach

Uses Software

• Racer

Cites Work

• Attributive concept descriptions with complements
• Propositional dynamic logic of regular programs
• The logic of time. A model-theoretic investigation into the varieties of temporal ontology and temporal discourse
• Polynomial-time implication problems for unary inclusion dependencies
• On the complexity of integer programming
• Complexity Results for First-Order Two-Variable Logic with Counting
• Automated Deduction – CADE-19
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of finite model reasoning in description logics