2021/08/29 by Rafael Peñaloza, Peñaloza, Rafael
Biochemistry, Genetics and Molecular Biology · Computer Science · Decision Sciences · #Biomedical Text Mining and Ontologies #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Scientific Computing and Data Management #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2108.12774
openalex publication_date 2021/08/29 · openalex created_date 2021/09/13 · openalex updated_date 2026/07/28
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.