Abstract: 
The task of a monitor is to watch, at runtime, the execution of a reactive system, and signal the occurrence of a safety violation in the observed sequence of events. While finitestate monitors have been studied extensively, in practice, monitoring software also makes use of unbounded memory. We define a model of automata equipped with integervalued registers which can execute only a bounded number of instructions between consecutive events, and thus can form the theoretical basis for the study of infinitestate monitors. We classify these register monitors according to the number k of available registers, and the type of register instructions. In stark contrast to the theory of computability for register machines, we prove that for every k 1, monitors with k + 1 counters (with instruction set 〈+1, =〉) are strictly more expressive than monitors with k counters. We also show that adder monitors (with instruction set 〈1, +, =〉) are strictly more expressive than counter monitors, but are complete for monitoring all computable safety languages for k = 6. Realtime monitors are further required to signal the occurrence of a safety violation as soon as it occurs. The expressiveness hierarchy for counter monitors carries over to realtime monitors. We then show that 2 adders cannot simulate 3 counters in realtime. Finally, we show that realtime adder monitors with inequalities are as expressive as realtime Turing machines.
