  Nfer is a Runtime Verification language for the analysis of event traces that
applies rules to create hierarchies of time intervals. This work examines the
complexity of the evaluation and satisfiability problems for the data-free
fragment of nfer. The evaluation problem asks whether a given interval is
generated by applying rules to a known input, while the satisfiability problem
asks if an input exists that will generate a given interval. By excluding data
from the language, we obtain polynomial-time algorithms for the evaluation
problem and for satisfiability when only considering inclusive rules.
Furthermore, we show decidability for the satisfiability problem for cycle-free
specifications and undecidability for satisfiability of full data-free nfer.
