We aim to determine which temporal instance queries can be uniquely characterised by a (polynomial-size) set of positive and negative temporal data examples. We start by considering queries formulated in fragments of propositional linear temporal logic LTL that correspond to conjunctive queries (CQs) or extensions thereof induced by the until operator. Not all of these queries admit polynomial characterisations but by restricting them further to path-shaped queries we identify natural classes that do. We then investigate how far the obtained characterisations can be lifted to temporal knowledge graphs queried by 2D languages combining LTL with concepts in description logics EL or ELI (i.e., tree-shaped CQs). While temporal operators in the scope of description logic constructors can destroy polynomial characterisability, we obtain general transfer results for the case when description logic constructors are within the scope of temporal operators. Finally, we apply our characterisations to establish (polynomial) learnability of temporal instance queries using membership queries in the active learning framework.
翻译:我们的目标是确定哪些时间实例查询能够以一组正和负时间数据实例(Polynomial size)来独具特征。 我们首先考虑以直线直线时间逻辑LTL的片段提出的询问,这些片段与连接查询(CQs)相对应,或由操作者引发的LTL的延伸。 所有这些查询并不都承认多语种特征,而是将其进一步限制在路径形查询之外,我们确定自然类别。然后我们调查获得的特征在多大程度上可以被提升到由2D语言将LTL与描述逻辑EL或ELI(树形CQs)中的概念相结合的时间知识图中。虽然描述逻辑构建器范围内的时间操作者可以摧毁多语种特性,但在描述逻辑构建者在时间操作范围之内时,我们为这个案例获得一般传输结果。 最后,我们运用我们的特性来利用积极学习框架中的成员查询来确定(Polynomial)可学习时间实例查询。