An Upper Bound for Provenance in ELHr

08/29/2021
by   Rafael Penaloza, et al.
0

We investigate the entailment problem in ELHr ontologies annotated with provenance information. In more detail, we show that subsumption entailment is in NP if provenance is represented with polynomials from the Trio semiring and in PTime if the semiring is not commutative. The proof is based on the construction of a weighted tree automaton which recognises a language that matches with the corresponding provenance polynomial.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset