  Complex Event Recognition (CER for short) refers to the activity of detecting
patterns in streams of continuously arriving data. This field has been
traditionally approached from a practical point of view, resulting in
heterogeneous implementations with fundamentally different capabilities. The
main reason behind this is that defining formal semantics for a CER language is
not trivial: they usually combine first-order variables for joining and
filtering events with regular operators like sequencing and Kleene closure.
Moreover, their semantics usually focus only on the detection of complex
events, leaving the concept of output mostly unattended.
  In this paper, we propose to unify the semantics and output of complex event
recognition languages by using second order objects. Specifically, we introduce
a CER language called Second Order Complex Event Logic (SO-CEL for short), that
uses second order variables for managing and outputting sequences of events.
This makes the definition of the main CER operators simple, allowing us to
develop the first steps in understanding its expressive power. We start by
comparing SO-CEL with a version that uses first-order variables called FO-CEL,
showing that they are equivalent in expressive power when restricted to unary
predicates but, surprisingly, incomparable in general. Nevertheless, we show
that if we restrict to sets of binary predicates, then SO-CEL is strictly more
expressive than FO-CEL. Then, we introduce a natural computational model called
Unary Complex Event Automata (UCEA) that provides a better understanding of
SO-CEL. We show that, under unary predicates, SO-CEL captures the subclass of
UCEA that satisfy the so-called *-property. Finally, we identify the operations
that SO-CEL is lacking to capture UCEA and introduce a natural extension of the
language that captures the complete class of UCEA under unary predicates.
