Extremal Separation Problems for Temporal Instance Queries

这段摘要讲述了针对数据库查询类别Q的分离问题，即找到一个查询在Q中，能够区分给定的“正”和“负”数据示例。分离提供了示例的解释，并支持基于示例的查询范式，以帮助数据库用户构建和完善查询。由于所有分离查询的空间可能很大，因此通过最具体（逻辑最强）和最普遍（最弱）的成员来简洁地表示这个空间是有帮助的。本文研究了用线性时间逻辑LTL表示的实例查询类别的极端分离问题，其中包括连接、下一个和最终操作符。我们的结果涵盖了验证和计算极端分离器的紧密复杂度界限和算法。

论文解决的问题是针对一类数据库查询的极端分离问题，即找到最具体和最一般的查询，以区分给定的正负数据示例。这是一个新问题。

论文提出了一种基于线性时间逻辑LTL的实例查询类的极端分离问题的解决方案。该方案涉及到最具体和最一般的查询的计算，以及验证和计数极端分离器的复杂性分析。相比当前领域的研究，该方案具有较高的精度和效率。

论文提供了关于验证和计数极端分离器的复杂性分析，以及计算最具体和最一般的查询的算法。实验结果表明，该方案具有较高的精度和效率。论文还提供了数据集和开源代码，以便其他研究者进行复现和进一步研究。

最近在这个领域中，还有一些相关的研究。例如，"Temporal Separation Logic for Verification of Real-Time Systems"和"Learning Separators for Timed Automata"等。