论文标题
评估NFER的复杂性
The Complexity of Evaluating nfer
论文作者
论文摘要
NFER是一种基于规则的语言，用于将事件流将其抽象为与数据间隔的层次结构。 NFER具有多种实现，并已应用于航天器遥测和自动驾驶汽车日志的分析。这项工作提供了对NFER评估的首次复杂性分析，即确定是否通过应用规则生成给定间隔的问题。 我们表明，完整的语言是不可决定的，这取决于规则中的递归和无限的数据域。通过限制这两个功能，我们获得了严格的可决定性结果。我们还研究了对排他性规则和最小性的复杂性的影响。对于最实际的情况，即有限数据最小的情况，我们提供了多项式时间算法。
Nfer is a rule-based language for abstracting event streams into a hierarchy of intervals with data. Nfer has multiple implementations and has been applied in the analysis of spacecraft telemetry and autonomous vehicle logs. This work provides the first complexity analysis of nfer evaluation, i.e., the problem of deciding whether a given interval is generated by applying rules. We show that the full nfer language is undecidable and that this depends on both recursion in the rules and an infinite data domain. By restricting either or both of those capabilities, we obtain tight decidability results. We also examine the impact on complexity of exclusive rules and minimality. For the most practical case, which is minimality with finite data, we provide a polynomial-time algorithm.
