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.

翻译：Nfer是将事件流抽象成一个有数据间隔的等级的有章可循的语言。Nfer有多个执行,并被用于分析航天器遥测和自主车辆记录。这项工作对 nfer 评估提供了第一次复杂分析,即确定适用规则是否产生一个特定间隔的问题。我们表明,完整的 nfer 语言是不可变的,这取决于规则的重复和无限数据域。通过限制这两种能力中的一种或两种,我们获得了严格的变异性结果。我们还审查了对排他性规则和最小性的复杂性的影响。最实际的情况是,只有有限的数据,我们提供了一种多米时间算法。