The Reaction Algebra: A Formal Language for Event Correlation

César Sánchez, Matteo Slanina, Henny Sipma, and Zohar Manna

Event-pattern reactive programs are small programs that process an input stream of events to detect and act upon given temporal patterns. These programs are used in distributed systems to notify components when they must react.

We present a \emph{reaction algebra}, a declarative language to define finite-state reactions. We prove that this reaction algebra is complete in the following sense: every event-pattern reactive system that can be described and implemented -- in any formalism -- using finite memory, can also be described in our reaction algebra.

In Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, vol 4800 of Lecture Notes in Computer Science, pp586-609. Springer-Verlag, Berlin, 2008.
Download: BIB PDF