The complexity of finite model reasoning in description logics

DOI10.1016/J.IC.2004.11.002zbMATH Open1097.03022OpenAlexW2080057244MaRDI QIDQ2486582FDOQ2486582

Authors: Carsten Lutz, Ulrike Sattler, 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

Recommendations

• The complexity of finite model reasoning in description logics.
• scientific article; zbMATH DE number 1448975
• scientific article; zbMATH DE number 1424042
• On the complexity of (restricted) \(\mathcal{ALCI}r\)
• The Complexity of Conjunctive Query Answering in Expressive Description Logics

zbMATH Keywords

Description logicNumber restrictionsFinite satisfiability

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Propositional dynamic logic of regular programs
• Polynomial-time implication problems for unary inclusion dependencies
• Title not available (Why is that?)
• Attributive concept descriptions with complements
• Title not available (Why is that?)
• On the complexity of integer programming
• Title not available (Why is that?)
• The logic of time. A model-theoretic investigation into the varieties of temporal ontology and temporal discourse
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity Results for First-Order Two-Variable Logic with Counting
• Title not available (Why is that?)
• The complexity of finite model reasoning in description logics.

Cited In (15)

• Complexity of Axiom Pinpointing in the DL-Lite Family of Description Logics
• Datalog rewritability and data complexity of \(\mathcal{ALCHOIQ}\) with closed predicates
• Justifications for Description Logic Knowledge Bases Under the Fixed-Domain Semantics
• Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots
• The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
• The complexity of finite model reasoning in description logics.
• Title not available (Why is that?)
• Reasoning about graded strategy quantifiers
• Generalized satisfiability for the description logic \(\mathcal{ALC}\) (extended abstract)
• Finding Finite Models in Multi-sorted First-Order Logic
• Understanding the complexity of axiom pinpointing in lightweight description logics
• Extending \(\mathcal{ALCQIO}\) with trees
• Query Answering in Description Logics: The Knots Approach
• On representing concepts in finite models
• Exploring Finite Models in the Description Logic ${\mathcal {EL}}_{\rm gfp}$

Uses Software

• Racer

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2486582)