  In runtime verification, the central problem is to decide if a given program
execution violates a given property. In online runtime verification, a monitor
observes a program's execution as it happens. If the program being observed has
hard real-time constraints, then the monitor inherits them. In the presence of
hard real-time constraints it becomes a challenge to maintain enough
information to produce error traces, should a property violation be observed.
In this paper we introduce a data structure, called tree buffer, that solves
this problem in the context of automata-based monitors: If the monitor itself
respects hard real-time constraints, then enriching it by tree buffers makes it
possible to provide error traces, which are essential for diagnosing defects.
We show that tree buffers are also useful in other application domains. For
example, they can be used to implement functionality of capturing groups in
regular expressions. We prove optimal asymptotic bounds for our data structure,
and validate them using empirical data from two sources: regular expression
searching through Wikipedia, and runtime verification of execution traces
obtained from the DaCapo test suite.
