Expressive Completeness of an Event-Pattern Reactive Programming Language

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

Event-pattern reactive programs serve reactive components by pre-processing the input event stream and generating notifications according to temporal patterns. Our general model of event-pattern reactions can express every reasonable'' model of message-passing reactive system, including input-output machines.

The declarative language \PAR allows the expression of complex event-pattern reactions. \PAR is a programming language and therefore is intrinsically deterministic. The main result of the paper is that despite its simplicity and deterministic nature, \PAR is expressively complete in the following sense: \emph{every event-pattern reactive system that can be described and implemented}---in any formalism---\emph{using finite memory can also be described in \PAR.}

In Formal Techniques for Networked and Distributed Systems (FORTE'05), vol. 3731 of Lecture Notes in Computer Science. Springer-Verlag, pp 529-532, 2005.