Understanding the complexity of axiom pinpointing in lightweight description logics

DOI10.1016/j.artint.2017.06.002zbMath1419.68128OpenAlexW2639976559WikidataQ114016167 ScholiaQ114016167MaRDI QIDQ1680678

Rafael Peñaloza, Barış Sertkaya

Publication date: 16 November 2017

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2017.06.002

zbMATH Keywords

computational complexitydescription logicscounting complexityenumeration complexityaxiom pinpointing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Knowledge representation (68T30)

Related Items (7)

Justifications for Description Logic Knowledge Bases Under the Fixed-Domain Semantics ⋮ Pinpointing axioms in ontologies via ASP ⋮ Reasoning in the defeasible description logic \(\mathcal{EL}_{\bot}\) -- computing standard inferences under rational and relevant semantics ⋮ Strong inconsistency ⋮ On the complexity of inconsistency measurement ⋮ Query answering over inconsistent knowledge bases: a probabilistic approach ⋮ Hypergraph-based inference rules for computing \(\mathcal{EL}^+\)-ontology justifications

Uses Software

• BEACON
• Just
• BioPortal
• VoCol
• EL2MCS

Cites Work

• Unnamed Item
• Fast, flexible MUS enumeration
• SAT-based MaxSAT algorithms
• The complexity of computing the permanent
• Automata-based axiom pinpointing
• KI 2007: Advances in artificial intelligence. 30th annual German conference on AI, KI 2007, Osnabrück, Germany, September 10--13, 2007. Proceedings
• The complexity of facets (and some facets of complexity)
• On generating all maximal independent sets
• The complexity of facets resolved
• Complete sets and the polynomial-time hierarchy
• Finding the \(K\) shortest hyperpaths
• Complexity of generalized satisfiability counting problems
• Iterative and core-guided maxsat solving: a survey and assessment
• The Bayesian ontology language \(\mathcal {BEL}\)
• Redundancy in logic. I: CNF propositional formulae
• Debugging incoherent terminologies
• Algorithms for computing minimal unsatisfiable subsets of constraints
• Subtractive reductions and complete problems for counting complexity classes
• BEACON: An Efficient SAT-Based Tool for Debugging $${\mathcal {EL}}{^+}$$ Ontologies
• Efficient Reasoning for Inconsistent Horn Formulae
• Error-Tolerant Reasoning in the Description Logic $\mathcal{E{\kern-.1em}L}$
• Complexity of Axiom Pinpointing in the DL-Lite Family of Description Logics
• Towards efficient MUS extraction
• The Bayesian Description Logic ${\mathcal{BEL}}$
• The even-path problem for graphs and digraphs
• Axiom Pinpointing in General Tableaux
• The DL-Lite Family and Relations
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• The Complexity of Enumeration and Reliability Problems
• A New Algorithm for Generating All the Maximal Independent Sets
• Achieving new upper bounds for the hypergraph duality problem through logic
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Inconsistency-Tolerant Instance Checking in Tractable Description Logics
• Axiom Pinpointing in Lightweight Description Logics via Horn-SAT Encoding and Conflict Analysis
• Finding the K Shortest Loopless Paths in a Network

This page was built for publication: Understanding the complexity of axiom pinpointing in lightweight description logics