  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.
