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.
paper
Description Logics, Provenance, Complexity Analysis
English
34th International Workshop on Description Logics, DL 2021
2021
CEUR Workshop Proceedings
2021
2954
open
Penaloza, R. (2021). An Upper Bound for Provenance in ELHr. In CEUR Workshop Proceedings. CEUR-WS.
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/336366
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
Social impact