We investigate the entailment problem in ELHrontologies 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.
Penaloza, R. (2021). An Upper Bound for Provenance in ELHr. In CEUR Workshop Proceedings. CEUR-WS.
An Upper Bound for Provenance in ELHr
Penaloza R.
2021
Abstract
We investigate the entailment problem in ELHrontologies 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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
DL21-WA.pdf
accesso aperto
Tipologia di allegato:
Submitted Version (Pre-print)
Dimensione
362.27 kB
Formato
Adobe PDF
|
362.27 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
