The complexity of finite model reasoning in description logics

DOI10.1016/J.IC.2004.11.002MaRDI QIDQ2486582zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1696774 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 67503 (Why is no real title available?)
• scientific article; zbMATH DE number 1223729 (Why is no real title available?)
• scientific article; zbMATH DE number 1182733 (Why is no real title available?)
• scientific article; zbMATH DE number 1936671 (Why is no real title available?)
• scientific article; zbMATH DE number 2086675 (Why is no real title available?)
• Attributive concept descriptions with complements
• Complexity Results for First-Order Two-Variable Logic with Counting
• On the complexity of integer programming
• Polynomial-time implication problems for unary inclusion dependencies
• Propositional dynamic logic of regular programs
• The complexity of finite model reasoning in description logics.
• The logic of time. A model-theoretic investigation into the varieties of temporal ontology and temporal discourse

Cited in

(15)

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

Describes a project that uses

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)