Semiring Provenance in Expressive Description Logics

Provenance refers to the task of identifying and tracing the axiomatic origins of a consequence from a knowledge base. Semiring provenance uses two operators to represent (i) axioms that together yield the consequence and (ii) the different possible derivations. To-date, most provenance approaches are limited to inexpressive logics mainly due to the difficulty in dealing with complex constructors like negations. We surpass this issue through a general notion of provenance for interpretation-based semantics. We then show how weighted automata can be exploited to compute this provenance, hence providing an effective method for computing the provenance of ALC consequences.