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.
翻译:我们用来源信息来调查ELHr 肿瘤学中的附带问题。 更详细地说, 我们证明如果源代码与三联半环的多数值代表在一起, 且如果半环不具有通融性, 而在PTime, 则源代码与多数值代表在一起, 则在 NP 中包含递增因素。 证据是基于一个加权树自动图的构造, 它承认一种与相应的源代码相匹配的语言 。