Expressive Completeness of an Event-Pattern Reactive Programming Language

Abstract

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: every event-pattern reactive system that can be described and implemented—in any formalism—using finite memory can also be described in PAR.