11institutetext: Department of Computer Science, University of Liverpool
11email<EMAIL_ADDRESS>
# Representation and Processing of Instantaneous and Durative Temporal
Phenomena††thanks: This work has been funded by the Engineering and Physical
Sciences Research Council (EPSRC) Centre for Doctoral Training in Distributed
Algorithms at the University of Liverpool, and Denbridge Marine Limited,
United Kingdom.

Manolis Pitsikalis  0000-0003-2959-2022 Alexei Lisitsa  0000-0002-3820-643X
Shan Luo  0000-0003-4760-0372

###### Abstract

Event definitions in Complex Event Processing systems are constrained by the
expressiveness of each system’s language. Some systems allow the definition of
instantaneous complex events, while others allow the definition of durative
complex events. While there are exceptions that offer both options, they often
lack of intervals relations such as those specified by the Allen’s interval
algebra. In this paper, we propose a new logic based temporal phenomena
definition language, specifically tailored for Complex Event Processing, that
allows the representation of both instantaneous and durative phenomena and the
temporal relations between them. Moreover, we demonstrate the expressiveness
of our proposed language by employing a maritime use case where we define
maritime events of interest. Finally, we analyse the execution semantics of
our proposed language for stream processing and introduce the ‘Phenesthe’
implementation prototype.

###### Keywords:

Event definition language, temporal logic, stream processing, event
recognition

##  1 Introduction

There are numerous event description languages, each with its own formal
description and expressiveness. Event description languages allow the
representation and the specification of temporal phenomena. They have been
used widely in, among others, complex event processing and recognition [12, 3,
5, 7], system analysis and verification [14, 8]. In the case of Complex Event
Processing, which is the focus of this paper, users with expert knowledge, or
machine learning algorithms, provide definitions of events of interest i.e.,
complex events that are represented in an event definition language. The
Complex Event Processing system accepts as input a single or multiple streams
of low level events, such as the timestamped transmitted values of a sensor
and by continuously applying temporal queries that involve the provided event
definitions, it will produce a stream of complex events associated with some
temporal information.

However, the set of events that can be represented in the language of a
Complex Event Processing system is constrained by the expressiveness of its
event definition language. For example, languages with a point-based temporal
model associate facts to instants of time while languages with an interval-
based temporal model associate facts with intervals [11], therefore the
representation of durative and instantaneous entities in each case
respectively is sometimes impossible or not straightforward. Event Calculus
[16] approaches [5, 10, 15] allow the representation of both instantaneous and
durative entities, however they lack of interval relations such as those
specified by the Allen’s interval algebra [2].

In this paper, we formally present a logic based language for Complex Event
Processing that allows the description of both instantaneous and durative
temporal phenomena and the relations between them. Moreover, we present the
execution semantics for stream processing and demonstrate the expressiveness
of the language by employing a maritime use-case scenario where the goal is to
describe maritime activities of interest. Thus, the contributions of this
paper are the following:

  * •

a formally described language for the representation of both instantaneous and
durative temporal phenomena and their relations,

  * •

the execution semantics for stream processing along with an implementation
prototype,

  * •

a demonstration of the expressiveness of the language in a maritime use case.

The paper is organised as follows, in Section 2 we present the syntax, the
grammar and the semantics of our language. Next, in Section 3 we demonstrate
its expressiveness by formalising a set of maritime activities. In Section 4
we present the execution semantics for stream processing, while in Section 5
we compare our language with relevant works. Finally, in Section 6 we
summarise our approach and discuss our future directions.

##  2 Language

The key components of our language are events, states and dynamic temporal
phenomena. In what follows, ‘temporal phenomena’ includes all of the three
aforementioned entities. Events are true at instants of time, while states and
dynamic temporal phenomena hold on intervals. Events are defined in terms of
logical operations between instantaneous temporal phenomena, states are
defined using the operators of maximal range, temporal union, temporal
intersection and temporal complement; finally, dynamic temporal phenomena are
defined in terms of temporal relations that involve the basic seven of Allen’s
interval algebra [2]. In this Section, we present the syntax, the semantics
and the grammar of our language.

###  2.1 Syntax

Formally, our language is described by the triplet
$\langle\mathcal{P},L,\Phi\rangle$, where

  * •

$\mathcal{P}$ is a set of Predicates (atomic formulae), that may be of three
types, event, state or dynamic temporal phenomenon predicates;

  * •

$L$ is a set defined by the union of the set of logical connectives
$\\{\wedge,\vee,\neg\\}$, the set of temporal operators,
$\\{\rightarrowtail,\sqcup,\sqcap,\setminus\\}$, the set of temporal relations
$\\{\textsf{\small before}$, meets, overlaps, finishes, starts, equals,
$\textsf{\small contains}\\}$ and finally the set of the $\\{\textsf{\small
start},\textsf{\small end}\\}$ operators.

  * •

$\Phi$ is the set of formulae defined by the union of the formulae sets
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$,
$\Phi^{-}$ and $\Phi^{=}$, that we will present below.

Formulae of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
describe instantaneous temporal phenomena, formulae of $\Phi^{-}$ describe
durative temporal phenomena that hold (are true) in disjoint maximal
intervals, finally formulae of $\Phi^{=}$ describe durative temporal phenomena
that may hold in non-disjoint intervals. Atomic formulae of $\Phi^{\square}$
where
$\square\in\\{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}},-,=\\}$
are denoted as $\Phi^{\square}_{o}$. Terms are defined as follows:

  * •

Each variable is a term.

  * •

Each constant is a term.

Events, states and dynamic temporal phenomena are expressed as n-ary predicate
symbols, of the corresponding type (event, state or dynamic temporal
phenomenon), $\mathit{P(a_{1},...,a_{n})}$, where $P$ is the associated name
and $a_{1},...,a_{n}$ are terms corresponding to atemporal properties.
Moreover, we assume that the set of predicate symbols includes those with
atemporal and fixed semantics, such as arithmetic comparison operators etc.,
however for simplification reasons in what follows we omit their presentation.
The set of formulae
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
is defined as follows:

  * •

(Event predicate) If P is an n-ary event predicate and $a_{1},...,a_{n}$ are
terms then $P(a_{1},...,a_{n})$ is a formula of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
.

  * •

(Negation) If $\phi$ is a formula of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
then $\neg\phi$ is a formula of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
.

  * •

(Conjunction/disjunction) If $\phi$ and $\psi$ are formulae of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
then $\phi\ op\ \psi$, where $op$ is the conjunction ($\wedge$) or disjunction
($\vee$) connective, is a formula of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$.

  * •

(start/end) If $\phi$ is a formula of $\Phi^{-}$ then $\textsf{\small
start}(\phi)$ and $\textsf{\small end}(\phi)$ are formulae of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$.

Following, we define the set of formulae $\Phi^{-}$:

  * •

(State predicate) If P is an n-ary state predicate and $a_{1},...,a_{n}$ are
terms then $P(a_{1},...,a_{n})$ is a formula of $\Phi^{-}$.

  * •

(Maximal range) If $\phi$ and $\psi$ are formulae of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
then $\phi\rightarrowtail\psi$ is a formula of $\Phi^{-}$.

  * •

(Temporal union, intersection & complement) If $\phi$ and $\psi$ are formulae
of $\Phi^{-}$ then $\phi\ \square\ \psi$, where
$\square\in\\{\sqcup,\sqcap,\setminus\\}$, is a formula of $\Phi^{-}$. The
temporal operators $\sqcup,\sqcap$ and $\setminus$ correspond to temporal
union, intersection and complement respectively.

Finally we define the set of formulae $\Phi^{=}$ as follows:

  * •

(Dynamic temporal phenomenon predicate) If P is an n-ary dynamic temporal
phenomenon predicate and $a_{1},...,a_{n}$ are terms then $P(a_{1},...,a_{n})$
is a formula of $\Phi^{=}$.

  * •

(Temporal relation)

    * –

If $\phi$ and $\psi$ are formulae of $\Phi^{-}\cup\ \Phi^{=}$ then $\phi\
{\mathit{tr}}\ \psi$, where ${\mathit{tr}}\in\\{\textsf{\small meets},$
$\textsf{\small overlaps},$ $\textsf{\small equals}\\}$, is a formula of
$\Phi^{=}$.

    * –

If $\phi$ is a formula of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}\cup\Phi^{-}\cup\Phi^{=}$
and $\psi$ is a formula of $\Phi^{-}\cup\Phi^{=}$ then $\phi\ {\mathit{tr}}\
\psi$, where ${\mathit{tr}}\in\\{\textsf{\small finishes},\textsf{\small
starts}\\}$, is a formula of $\Phi^{=}$.

    * –

If $\phi$ is a formula of $\Phi^{-}\cup\Phi^{=}$ and $\psi$ is a formula of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}\cup\Phi^{-}\cup\Phi^{=}$
then $\phi\ \textsf{\small contains}\ \psi$ is a formula of $\Phi^{=}$.

    * –

If $\phi$ is a formula of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}\cup\Phi^{-}\cup\Phi^{=}$
and $\psi$ is a formula of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}\cup\Phi^{-}\cup\Phi^{=}$
then $\phi\ \textsf{\small before}\ \psi$ is a formula of $\Phi^{=}$.

###  2.2 Grammar

In addition to the elements described above, our language includes temporal
phenomena definitions that specify new event, state and dynamic temporal
phenomena predicates. The production rule-set (26) presents the complete
grammar of the language in the Extended Backus-Naur form (EBNF).

$\displaystyle\begin{array}[]{l}\langle{\mathit{event}}\rangle\ ::=\
{\mathit{eventName}}(...);\\\ \langle{\mathit{state}}\rangle\ ::=\
{\mathit{stateName}}(...);\\\ \langle{\mathit{dynamic}}\rangle\ ::=\
{\mathit{dynamicPhenomenonName}}(...);\\\\[2.5pt]
\langle{\mathit{temporalExpression}}\rangle\ ::=\
\langle{\mathit{instantExpression}}\rangle\ |\
\langle{\mathit{intervalExpression}}\rangle;\\\\[2.5pt]
\langle{\mathit{instantExpression}}\rangle\ ::=\
\mlq(\mrq\langle{\mathit{instantExpresstion}}\rangle\mlq)\mrq\ |\ \neg\
\langle{\mathit{instantExpression}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\qquad|\
\langle{\mathit{instantExpression}}\rangle\ (\mlq\wedge\mrq\ |\ \mlq\vee\mrq)\
\langle{\mathit{instantExpression}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\qquad|\ \langle{\mathit{startEndOp}}\rangle\ |\
\langle{\mathit{event}}\rangle;\\\\[2.5pt]
\langle{\mathit{intervalExpression}}\rangle\ ::=\
\langle{\mathit{intervalOperation}}\rangle\ |\
\langle{\mathit{intervalRelation}}\rangle;\\\\[2.5pt]
\langle{\mathit{intervalOperation}}\rangle\ ::=\
\langle{\mathit{intervalOperation}}\rangle\ (\mlq\sqcup\mrq\ |\
\mlq\sqcap\mrq\ |\ \mlq\setminus\mrq)\
\langle{\mathit{intervalOperation}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\qquad|\
\langle{\mathit{instantExpression}}\rangle\ \mlq\rightarrowtail\mrq\
\langle{\mathit{instantExpression}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\qquad|\ \
\mlq(\mrq\langle{\mathit{intervalOperation}}\rangle\mlq)\mrq\ |\ \langle
state\rangle;\\\\[2.5pt] \langle{\mathit{intervalRelation}}\rangle\ ::=\
\langle{\mathit{temporalExpression}}\rangle\ \mlq\texttt{before}\mrq\
\langle{\mathit{temporalExpression}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\quad|\
\langle{\mathit{intervalExpression}}\rangle\ \mlq\texttt{overlaps}\mrq\
\langle{\mathit{intervalExpression}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\quad|\
\langle{\mathit{intervalExpression}}\rangle\ \mlq\texttt{meets}\mrq\
\langle{\mathit{intervalExpression}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\quad|\
\langle{\mathit{temporalExpression}}\rangle\ \mlq\texttt{finishes}\mrq\
\langle{\mathit{intervalExpression}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\quad|\
\langle{\mathit{temporalExpression}}\rangle\ \mlq\texttt{starts}\mrq\
\langle{\mathit{intervalExpression}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\quad|\
\langle{\mathit{intervalExpression}}\rangle\ \mlq\texttt{contains}\mrq\
\langle{\mathit{temporalExpression}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\quad|\
\langle{\mathit{intervalExpression}}\rangle\ \mlq\texttt{equals}\mrq\
\langle{\mathit{intervalExpression}}\rangle\\\
\qquad\qquad\qquad\qquad\qquad\quad|\
\mlq(\mrq\langle{\mathit{intervalRelation}}\rangle\mlq)\mrq\ |\
\langle{\mathit{dynamic}}\rangle;\\\\[2.5pt]
\langle{\mathit{startEndOp}}\rangle\ ::=\ (\mlq\texttt{start}\mrq\ |\
\mlq\texttt{end}\mrq)\mlq(\mrq\langle{\mathit{intervalOperation}}\rangle\mlq)\mrq;\\\\[2.5pt]
\langle{\mathit{definitions}}\rangle\ ::=\
\langle{\mathit{eventDefinition}}\rangle\ |\
\langle{\mathit{stateDefinition}}\rangle\\\ \qquad\qquad\qquad\qquad\quad|\
\langle{\mathit{dynamicDefinition}}\rangle;\\\\[2.5pt]
\langle{\mathit{eventDefinition}}\rangle\ ::=\ \mlq\texttt{event}\mrq\ \langle
event\rangle\mlq:\mrq\ \langle{\mathit{instantExpression}}\rangle\mlq.\mrq;\\\
\langle{\mathit{stateDefinition}}\rangle::=\mlq\texttt{state}\mrq\ \langle
state\rangle\mlq:\mrq\langle{\mathit{intervalOperation}}\rangle\mlq.\mrq;\\\
\langle{\mathit{dynamicDefinition}}\rangle::=\mlq\texttt{dynamic}\mrq\ \langle
dynamic\rangle\mlq:\mrq\langle{\mathit{intervalRelation}}\rangle\mlq.\mrq;\end{array}$
(26)

Phenomena definitions are specified by the production rule
$\langle\textit{definitions}\rangle$ of the grammar. Event predicates are
defined using expressions on instants of time, expressed via formulae of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$,
while state predicates are defined in terms of formulae of $\Phi^{-}$.
Finally, dynamic temporal phenomena predicates are defined in terms of
temporal relations on intervals and instants, therefore specified via formulae
of $\Phi^{=}$. Note, that the set of definitions allowed in the language is
subject to an additional constraint: no cyclic dependencies in the definitions
of temporal phenomena are allowed. A temporal phenomenon $A$ depends from
phenomenon $B$ if $B$ is a sub-formula of the definition of $A$.

###  2.3 Semantics

We assume time is represented by an infinite non empty set
$T=\mathbb{Z}^{+}_{0}$ of non-negative integers ordered via the ‘$<$’
relation, formally $\mathcal{T}=\langle T,<\rangle$. For the formulae sets
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}},\Phi^{-}$
and $\Phi^{=}$ we define the model $\mathcal{M}=\langle
T,I,<,V^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}},V^{-},V^{=}\rangle$
where $V^{.}:\Phi_{o}^{.}\rightarrow 2^{T}$, $V^{-}:\Phi_{o}^{-}\rightarrow
2^{I}$, $V^{=}:\Phi_{o}^{=}\rightarrow 2^{I}$ are valuations of atomic
formulae and $I=\\{[ts,te]:ts<te\ \text{and}\ ts,te\in
T\\}\cup\\{[ts,\infty):ts\in T\\}$ is the set of the accepted time intervals
of $T$. Given a model $\mathcal{M}$, the validity of a formula
$\phi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
at a timepoint $t\in T$ (in symbols $\mathcal{M},t\models\phi$) is determined
by the rules below:

  * •

$\mathcal{M},t\models P(a_{1},...,a_{n})$ where $P$ is an n-ary event
predicate symbol iff $t\in$ $V^{.}(P(a_{1},...,a_{n}))$;

  * •

$\mathcal{M},t\models\neg\phi$ where
$\phi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
iff $\mathcal{M},t\not\models\phi$;

  * •

$\mathcal{M},t\models\phi\wedge\psi$ where
$\phi,\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
iff $\mathcal{M},t\models\phi$ and $\mathcal{M},t\models\psi$;

  * •

$\mathcal{M},t\models\phi\vee\psi$ where
$\phi,\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
iff $\mathcal{M},t\models\phi$ or $\mathcal{M},t\models\psi$;

  * •

$\mathcal{M},t\models\textsf{\small start}(\phi)$ where $\phi\in\Phi^{-}$ iff
$\exists te\in T$ and $\mathcal{M},[t,te]\models\phi$, where
$\mathcal{M},[t,te]\models\phi$ denotes the validity of formula
$\phi\in\Phi^{-}$ at an interval $[t,te]$ as defined below;

  * •

$\mathcal{M},t\models\textsf{\small end}(\phi)$ where $\phi\in\Phi^{-}$ iff
$\exists ts\in T$ and $\mathcal{M},[ts,t]\models\phi$;

Given a model $\mathcal{M}$, the validity of a formula $\phi\in\Phi^{-}$ at a
time interval $[ts,te]\in I$ (in symbols $\mathcal{M},[ts,te]\models\phi$) is
defined as follows:

  * •

$\mathcal{M},[ts,te]\models P(a_{1},...,a_{n})$ where $P$ is an n-ary state
predicate symbol iff $[ts,te]\in$ $V^{-}(P(a_{1},...,a_{n}))$;

  * •

$\mathcal{M},[ts,te]\models\phi\rightarrowtail\psi$ where
$\phi,\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
iff:

    1. 1.

$ts\in T$ and $\mathcal{M},ts\models\phi$,

    2. 2.

$te\in(ts,\infty)\subset T$ and $\mathcal{M},te\models\psi\wedge\neg\phi$,

    3. 3.

$\forall ts^{\prime}\in[0,ts)\subset T,\exists te^{\prime}\in(ts^{\prime},ts)$
where $\mathcal{M},ts^{\prime}\models\phi\ \text{and}\
\mathcal{M},te^{\prime}\models\psi\wedge\neg\phi$,

    4. 4.

and finally, $\nexists te^{\prime\prime}\in(ts,te)\subset T$ where
$\mathcal{M},te^{\prime\prime}\models\psi\wedge\neg\phi$.

Essentially, $\phi\rightarrowtail\psi$ holds for the disjoint maximal
intervals that start at the earliest instant $ts$ where $\phi$ is true
(conditions 1,3) and end at the earliest instant $te,te>ts$ (condition 4)
where $\psi$ is true and $\phi$ is false (condition 2,4).

  * •

$\mathcal{M},[ts,\infty)\models\phi\rightarrowtail\psi$ where
$\phi,\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
iff conditions (1) and (3) from above hold and $\nexists
te\in(ts,\infty)\subset T$ such that
$\mathcal{M},te\models\psi\wedge\neg\phi$. Therefore a formula
$\phi\rightarrowtail\psi$ may hold indefinitely if there does not exist an
appropriate instant after $ts$ at which $\phi\wedge\neg\psi$ is satisfied.
This effectively implements the commonsense law of inertia [19]. For
simplification reasons in the semantics below we omit intervals open at the
right to infinity since they can be treated in a similar manner.

  * •

$\mathcal{M},[ts,te]\models\phi\ \sqcup\ \psi$ where $\phi,\psi\in\Phi^{-}$
iff one of the cases below holds:

    * –

$\exists$ a sequence of length $k>1$ of intervals $i_{1},...,i_{k}\in I$ where
$i_{k}=[ts_{k},te_{k}]$, $ts=ts_{1}$ and $te=te_{k}$ s.t.:

      1. 1.

$\forall\alpha\in[1,k-1]$: $te_{\alpha}\in i_{\alpha+1}$ and
$ts_{\alpha}<ts_{\alpha+1}$ and $te_{\alpha}<te_{\alpha+1}$ ,

      2. 2.

$\forall\beta\in[1,k]$: $\mathcal{M},[ts_{\beta},te_{\beta}]\models\phi$ or
$\mathcal{M},[ts_{\beta},te_{\beta}]\models\psi$, and

      3. 3.

$\nexists i_{\gamma}=[ts_{\gamma},te_{\gamma}]\in I$ where
$\mathcal{M},[ts_{\gamma},te_{\gamma}]\models\phi$ or
$\mathcal{M},[ts_{\gamma},te_{\gamma}]\models\psi$ and $ts_{1}\in i_{\gamma}$
or $te_{k}\in i_{\gamma}$

    * –

$\mathcal{M},[ts,te]\models\phi$ or $\mathcal{M},[ts,te]\models\psi$ and
$\nexists i_{\gamma}=[ts_{\gamma},te_{\gamma}]\in I$ where
$\mathcal{M},[ts_{\gamma},te_{\gamma}]\models\phi$ or
$\mathcal{M},[ts_{\gamma},te_{\gamma}]\models\psi$ and $ts\in i_{\gamma}$ or
$te\in i_{\gamma}$.

For a sequence of intervals, conditions (1-2) ensure that intervals, at which
$\phi$ or $\psi$ are valid, overlap or touch will coalesce, while condition
(3) ensures that the resulting interval is maximal. In the case of a single
interval, the conditions ensure that at the interval $[ts,te]$ $\phi$ or
$\psi$ is valid, and that $[ts,te]$ is maximal. In simple terms, the temporal
union $\phi\ \sqcup\ \psi$ holds for the intervals where at least one of
$\phi$ or $\psi$ hold. The above definition of temporal union follows the
definitions of temporal coalescing presented in [9, 13].

  * •

$\mathcal{M},[ts,te]\models\phi\ \setminus\ \psi$ where $\phi,\psi\in\Phi^{-}$
iff $\exists[ts^{\prime},te^{\prime}]\in I$ where
$\mathcal{M},[ts^{\prime},te^{\prime}]\models\phi$,
$[ts,te]\subseteq[ts^{\prime},te^{\prime}]$ (i.e. $[ts,te]$ subinterval of
$[ts^{\prime},te^{\prime}]$), $\forall[ts_{\psi},te_{\psi}]\in I$ where
$\mathcal{M},[ts_{\psi},te_{\psi}]\models\psi$,
$[ts,te]\cap[ts_{\psi},te_{\psi}]=\varnothing$ and finally $[ts,te]$ is
maximal. In plain language, the temporal difference of formulae $\phi,\psi$
holds for the maximal subintervals of the intervals at which $\phi$ holds but
$\psi$ doesn’t hold.

  * •

$\mathcal{M},[ts,te]\models\phi\ \sqcap\ \psi$ where $\phi,\psi\in\Phi^{-}$
iff $\exists[ts_{\phi},te_{\phi}],[ts_{\psi},te_{\psi}]\in I$ where
$\mathcal{M},[ts_{\phi},te_{\phi}]\models\phi$,
$\mathcal{M},[ts_{\psi},te_{\psi}]\models\psi$ and $\exists[ts,te]\in I$ where
$[ts,te]\subseteq[ts_{\phi},te_{\phi}]$,
$[ts,te]\subseteq[ts_{\psi},te_{\psi}]$ and $[ts,te]$ is maximal. In other
words, the temporal intersection of two formulae of $\Phi^{-}$ holds for the
intervals at which both formulae hold.

Given a model $\mathcal{M}$, the validity of a formula $\phi\in\Phi^{=}$ at a
time interval $[ts,te]\in I$ (in symbols $\mathcal{M},[ts,te]\models\phi$) is
defined as follows:

  * •

$\mathcal{M},[ts,te]\models P(a_{1},...,a_{n})$ where $P$ is n-ary dynamic
temporal phenomenon predicate symbol iff $[ts,te]\in
V^{=}(P(a_{1},...,a_{n}))$;

  * •

$\mathcal{M},[ts,te]\models\phi\ \textsf{\small before}\ \psi$ iff:

    * –

(interval - interval) for $\phi,\psi\in\Phi^{-}\cup\Phi^{=}$, $\exists a,b\in
T$, $a<b$, $\mathcal{M},[ts,a]\models\phi$, $\mathcal{M},[b,te]\models\psi$
and all of the conditions below hold:

      * *

$\nexists[ts^{\prime},a^{\prime}]\in I$ where
$\mathcal{M},[ts^{\prime},a^{\prime}]\models\phi$ and $a<a^{\prime}<b$,

      * *

$\nexists[b^{\prime},te^{\prime}]\in I$ where
$\mathcal{M},[b^{\prime},te^{\prime}]\models\psi$ and $a<b^{\prime}<b$.

    * –

(instant - interval) for
$\phi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$,
$\psi\in\Phi^{-}\cup\Phi^{=}$, $\mathcal{M},ts\models\phi$, $\exists a\in
T,a>ts$, $\mathcal{M},[a,te]\models\psi$ and all the conditions below hold:

      * *

$\nexists ts^{\prime}\in T$ where $\mathcal{M},ts^{\prime}\models\phi$ and
$ts<ts^{\prime}<a$,

      * *

$\nexists[a^{\prime},te^{\prime}]\in I$ where
$\mathcal{M},[a^{\prime},te^{\prime}]\models\psi$ and $ts<a^{\prime}<a$.

    * –

(interval - instant) for $\phi\in\Phi^{-}\cup\Phi^{=}$ and
$\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$,
$\exists a\in T$, $a<te$, $\mathcal{M},[ts,a]\models\phi$,
$\mathcal{M},te\models\psi$ and all the conditions below hold:

      * *

$\nexists[ts^{\prime},a^{\prime}]\in I$ where
$\mathcal{M},[ts^{\prime},a^{\prime}]\models\phi$ and $a<a^{\prime}<te$,

      * *

$\nexists te^{\prime}\in T$ where $\mathcal{M},te^{\prime}\models\psi$ and
$a<te^{\prime}<te$.

    * –

(instant - instant) for
$\phi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
and
$\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$,
$\mathcal{M},ts\models\phi$, $\mathcal{M},te\models\psi$ and all the
conditions below hold:

      * *

$\nexists ts^{\prime}$ where $\mathcal{M},ts^{\prime}\models\phi$ and
$ts<ts^{\prime}<te$,

      * *

$\nexists te^{\prime}$ where $\mathcal{M},te^{\prime}\models\psi$ and
$ts<te^{\prime}<te$.

In our approach the ‘before’ relation holds only for intervals where the pair
of instants or intervals at which the participating formulae are true or hold
are contiguous. For example for the intervals $[1,2]$,$[1,3]$ and $[5,6]$ only
$[1,3]$ is before $[5,6]$.

  * •

$\mathcal{M},[ts,te]\models\phi\ \textsf{\small meets}\ \psi$ iff
$\phi,\psi\in\Phi^{-}\cup\Phi^{=}$, $\exists a\in T$,
$\mathcal{M},[ts,a]\models\phi$ and $\mathcal{M},[a,te]\models\psi$.

  * •

$\mathcal{M},[ts,te]\models\phi\ \textsf{\small overlaps}\ \psi$ iff
$\phi,\psi\in\Phi^{-}\cup\Phi^{=}$, $\exists a,b\in T$, $ts<b<a<te$,
$\mathcal{M},[ts,a]\models\phi$ and $\mathcal{M},[b,te]\models\psi$.

  * •

$\mathcal{M},[ts,te]\models\phi\ \textsf{\small finishes}\ \psi$ iff:

    * –

(interval - interval) for $\phi,\psi\in\Phi^{-}\cup\Phi^{=}$, $\exists a\in
T$, $ts<a$, $\mathcal{M},[a,te]\models\phi$ and
$\mathcal{M},[ts,te]\models\psi$,

    * –

(instant - interval) for
$\phi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
and $\psi\in\Phi^{-}\cup\Phi^{=}$, $\mathcal{M},te\models\phi$ and
$\mathcal{M},[ts,te]\models\psi$.

  * •

$\mathcal{M},[ts,te]\models\phi\ \textsf{\small starts}\ \psi$ iff:

    * –

(interval - interval) for $\phi,\psi\in\Phi^{-}\cup\Phi^{=}$, $\exists a\in
T$, $a<te$, $\mathcal{M},[ts,a]\models\phi$ and
$\mathcal{M},[ts,te]\models\psi$,

    * –

(instant - interval) for
$\phi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$,
$\psi\in\Phi^{-}\cup\Phi^{=}$, $\mathcal{M},ts\models\phi$ and
$\mathcal{M},[ts,te]\models\psi$.

  * •

$\mathcal{M},[ts,te]\models\phi\ \textsf{\small equals}\ \psi$ iff for
$\phi,\psi\in\Phi^{-}\cup\Phi^{=}$, $\mathcal{M},[ts,te]\models\phi$ and
$\mathcal{M},[ts,te]\models\psi$.

  * •

$\mathcal{M},[ts,te]\models\phi\ \textsf{\small contains}\ \psi$ iff:

    * –

(interval - interval) for $\phi,\psi\in\Phi^{-}\cup\Phi^{=}$,
$\mathcal{M},[ts,te]\models\phi$, $\exists[a,b]\in I$, $ts<a<b<te$ and
$\mathcal{M},[a,b]\models\psi$,

    * –

(interval - instant) for $\phi\in\Phi^{-}\cup\Phi^{=}$,
$\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$,
$\mathcal{M},[ts,te]\models\phi$, $\exists a\in T$, $ts<a<te$ and
$\mathcal{M},a\models\psi$.

##  3 Maritime use case examples

Maritime situational awareness (MSA) is of major importance for environmental
and safety reasons. Maritime monitoring systems contribute in MSA by allowing
the detection of possibly dangerous, or unlawful activities while also
monitoring normal activities. Typically, maritime monitoring systems—as in the
case of this paper—use data from the Automatic Identification System (AIS) a
system that allows the transmission of timestamped positional and vessel
identity data from transceivers on vessels. Additionally, they may use
contextual static information such as areas of interest or historical vessel
information. Logic based approaches have already been used for Maritime
Monitoring. Works such as [20, 22] demonstrate that maritime activities can be
expressed as patterns written in some form of an event definition language and
be efficiently recognised. However, as mentioned earlier the definitions of
temporal phenomena are constrained by the expressiveness of each language. In
this section, we present definitions of maritime situations of interest
written in our temporal phenomena definition language.

###  3.1 Stopped vessels

A vessel is stopped when its speed is between a range e.g., $0-0.5$ knots.
Consider the definition for stopped vessels below:

$\displaystyle\begin{array}[]{l}\textsf{\small event}\
{\mathit{stop\\_start(Vessel)}}:\\\
\quad{\mathit{ais(Vessel,Speed,...)}}\wedge{\mathit{Speed}}\leq 0.5\
.\\\\[4.0pt] \textsf{\small event}\ {\mathit{stop\\_end(Vessel)}}:\\\
\quad{\mathit{ais(Vessel,Speed,...)}}\wedge{\mathit{Speed}}>0.5\ .\\\
\textsf{\small state}\ {\mathit{stopped(Vessel)}}:\\\
\quad{\mathit{stop\\_start(Vessel)}}\rightarrowtail{\mathit{stop\\_end(Vessel)}}.\end{array}$
(33)

${\mathit{ais(Vessel,Speed,...)}}$ is an input event that contains the vessel
id (Maritime Mobile Service Identity), its speed, its longitude and latitude
and other AIS information, while ${\mathit{stop\\_start}}$ and
${\mathit{stop\\_end}}$ are events that happen when an AIS message is received
for a ${\mathit{Vessel}}$ and its speed is either $\leq 0.5$ or $>0.5$
respectively. ${\mathit{stopped/1}}$ is a state defined using the maximal
range operator ($\rightarrowtail$) between the events
${\mathit{stop\\_start}}$ and ${\mathit{stop\\_end}}$, that holds true for the
maximal intervals a vessel’s speed is continuously $\leq$ 0.5 knots. Note that
the ${\mathit{stop\\_start}}$ and ${\mathit{stop\\_end}}$ events are optional,
since their definition could be integrated in the definition of the
${\mathit{stopped}}$ state directly.

###  3.2 Moored vessel

A vessel is considered moored when it is stopped near a port. The knowledge of
the times and the locations vessels are moored is especially important in
historical track analyses, law enforcement, etc. Below we provide the
definition for moored vessels:

$\displaystyle\begin{array}[]{l}\textsf{\small state}\
{\mathit{moored(Vessel,Port)}}:\\\ \quad{\mathit{stopped(Vessel)}}\
\sqcap{\mathit{in\\_port(Vessel,Port)}}.\\\ \end{array}$ (36)

${\mathit{moored/2}}$ is a state defined using the interval operator of
intersection between the ${\mathit{stopped/2}}$ and the
${\mathit{in\\_port(Vessel,Port)}}$ states where the latter is an input state
that holds when a ${\mathit{Vessel}}$ is inside a $Port$. Therefore, according
to the definition $\eqref{eq:moored}$, ${\mathit{moored}}$ holds for the
maximal sub-intervals of the intervals at which a vessel is stopped and inside
a port (recall the semantics of the intersection operator as defined in
Section 2.3).

###  3.3 Fishing trips

Monitoring of the fishing areas a fishing vessel has been through is important
for sustainability and safety reasons. A fishing trip can be described as a
series of certain maritime activities that are arranged over a long period of
time as follows. Fishing vessels leave from a port, then they are under-way,
they start a fishing activity in a fishing area, and then they return to the
same or another port. A definition of the fishing trip temporal phenomenon is
the following:

$\displaystyle\begin{array}[]{l}\textsf{\small dynamic}\
{\mathit{fishing\\_trip(Vessel,PortA,AreaID,PortB)}}:\\\
\quad{\mathit{\textsf{\small end}(moored(Vessel,PortA))}}\wedge\
type(Vessel,Fishing)\ \textsf{\small before}\\\
\quad({\mathit{underway(Vessel)}}\ \textsf{\small contains}\
{\mathit{in\\_fishing\\_area(Vessel,AreaID))}}\\\ \quad\ \textsf{\small
before}\ {\mathit{\textsf{\small start}(moored(Vessel,PortB))}}.\\\
\end{array}$ (41)

${\mathit{in\\_fishing\\_area(Vessel,AreaID)}}$ is an input state that holds
for the intervals a ${\mathit{Vessel}}$ is within a fishing area with id
${\mathit{AreaID}}$. ${\mathit{underway}}$ is a user defined state that holds
for the intervals a vessel’s speed is greater than 2.7 knots. We omit the
presentation of the definition of under-way due to space limitations.
Therefore, ${\mathit{fishing\\_trip/4}}$ as defined in rule (41), holds for
the intervals that start when a fishing vessel stops being moored at a
${\mathit{portA}}$, next the vessel is underway and during that period it
passes through a fishing area with id ${\mathit{AreaID}}$ and end when the
fishing vessel starts being moored at ${\mathit{portB}}$.

##  4 Executable semantics

Complex Event Processing refers to the processing of one or multiple streams
of atomic low level entities by continuously applying temporal queries and
producing a stream of time associated complex event detections. In our case,
the input stream comprises time associated temporal phenomena and the
detection stream comprises the detections of the user defined temporal
phenomena. Below, we provide the executable semantics that describe the
recognition mechanics for stream processing.

###  4.1 Stream processing

A stream is an arbitrary long sequence of time associated low level entities
i.e., atomic predicates of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}},\Phi^{-}$
and $\Phi^{=}$. A stream $\sigma$ that contains time associated atomic
formulae ‘occurring’ from the start of time $t_{0}$ up to a time $t_{\sigma}$
can be expressed by the model $\mathcal{M}_{\sigma}=\langle
T_{\sigma},I_{\sigma},<,V^{\cdot},V^{-},V^{=}\rangle$, where
$T_{\sigma}=[t_{0},t_{\sigma}]\subset T$ and $I_{\sigma}=\\{[ts,te]:ts<te\
\text{and}\ ts,te\in T_{\sigma}\\}\cup\\{[ts,\infty):ts\in T_{\sigma}\\}$ and
as in Section 2.3 $V^{.}:\Phi_{o}^{.}\rightarrow 2^{T_{\sigma}}$,
$V^{-}:\Phi_{o}^{-}\rightarrow 2^{I_{\sigma}}$, $V^{-}:\Phi_{o}^{=}\rightarrow
2^{I_{\sigma}}$ are valuations. Note that in the case of streams, a valuation
of an atomic formula provides the ordered set of instants or intervals that
the atomic formula is associated with. Sets of instants are ordered via the
less than relation, while interval sets are totally ordered, in other words
the ordering is applied first on the starts of intervals then the ends. This
ordering allows, as discussed later, for efficient computations of the
instants or the intervals at which formulae hold.

Similar to other approaches [5, 18], for efficiency reasons, we choose to use
a sliding window approach, whereby recognition of user-defined temporal
phenomena happens with temporal queries on a dynamically updated working
memory ${\mathit{WM}}$ that is specified by a temporal window $\omega$. A
temporal window $\omega$ is a finite sub-sequence of a stream $\sigma$, that
contains low level entities with associated temporal information that falls
within a time period $\omega=(t_{i},t_{j}],t_{i}<t_{j}$ with $t_{i},t_{j}\in
T$. We denote the number of time instants included in a temporal window
$\omega$, i.e., its size, as $|\omega|=t_{j}-t_{i}$.

####  4.1.1 Evaluation order of temporal phenomena

The evaluation of the temporal phenomena must be performed in an order that
does not allow unmet dependencies during processing. Recall that cyclic
dependencies are forbidden (see Section 2.2), therefore, the dependencies
between a set of temporal phenomena can be represented by a directed acyclic
graph $G_{d}=\\{E,D\\}$ where $E$ is the set of input and user defined
phenomena, and $D\subseteq E\times E$ is the set of dependencies.
Consequently, the processing order of a set of temporal phenomena relies on
finding a valid evaluation order, that is a numbering
$n:E\rightarrow\mathbb{N}$ of the phenomena so that
$n(A)<n(B)\Rightarrow(A,B)\not\in D$, meaning that $A$ will be evaluated
before $B$, and that $A$ does not depend on $B$. A numbering that satisfies
these constraints can be acquired by applying topological sort on $G_{d}$.
Phenomena in level 0—these are the input phenomena—of the topological order,
have no dependencies, while phenomena in higher levels have at least one
direct dependency to phenomena of the previous level, or more to phenomena of
lower levels.

####  4.1.2 Sliding window mechanics

In order to deal efficiently with the input load, we adopt a sliding temporal
window approach. With this approach, user defined temporal phenomena are
detected using information inside a working memory set ${\mathit{WM}}$ that
contains: time associated phenomena of the input stream that take place within
the current temporal window $\omega$, time associated phenomena of previous
windows that have been classified as non-redundant and finally the detections
of the current query.

Recognition occurs at equally distanced times $t_{q}\in T$, where
$t_{q+1}-t_{q}=s$ is the sliding step. At each $t_{q}$, the instants and the
intervals at which temporal phenomena are true or hold are computed according
to the evaluation order specified by the topological sorting of the $G_{d}$
graph and the current working memory ${\mathit{WM}}$. Algorithm 1 describes
the recognition process at a query time $t_{q}$ with working memory
${\mathit{WM}}$, window size $|\omega|$ and sliding step set to $s$. The
instants and intervals at which user defined temporal phenomena are true or
hold are computed for each level using ‘process/2’ and are asserted in the
current working memory; this ensures that they will be computed only once per
recognition query (lines 2-10). During the processing of the user defined
temporal phenomena some instants or intervals of the ${\mathit{WM}}$ are
classified as non-redundant—we will discuss this step shortly. When all the
temporal phenomena levels have been processed, the ${\mathit{WM}}$ is updated
(lines 11-12). During this step, all redundant information that falls outside
the next window, i.e., within $[t_{0},t_{q}-\omega+s]$, will be removed from
the working memory ${\mathit{WM}}$ and the processing of the next query at
$t_{q}+s$ will be able to commence.

Input: $\mathit{WM}$; Levels; $|\omega|$; $s$; $t_{q}$

1 allNonRedundant=[];

2 for  _level in [1,Levels]_ do

3 phenomenaDefs = phenomenaOfLevel(level);

4 for  _ phenomenon in phenomenaDefs_ do

5 intervals, instants, nonRedundant = process(phenomenon, $\mathit{WM}$);

6 if  _ type(phenomenon==‘event’)_ then

7 ${\mathit{WM}}$.assert(detections(phenomenon, instants));

8 else

9 ${\mathit{WM}}$.assert(detections(phenomenon, intervals));

10 allNonRedundant.add(nonRedundant)

11

12 for  _ element in ${\mathit{WM}}$.period($t_{0}$,$t_{q}-\omega+s$)_ do

13 if  _element not in allNonRedundant_ then WM.remove(element);

14

Algorithm 1 Querying process for working memory $\mathit{WM}$.

A time associated phenomenon included in $\mathit{WM}$ at $t_{q}$ is redundant
if it holds (a) for an instant or an interval that is is not included or
overlaps the next window $(t_{q}+s-\omega,t_{q}+s]$ and (b) does not
participate in incomplete or complete evaluations of formulae that hold for
intervals that overlap the next window. Consider for example the intervals of
Figure 1. During the window $\omega=(t_{q}-|\omega|,t_{q}]$, the states
${\mathit{moored(v,a)}},\ {\mathit{moored(v,b)}}$ hold for the intervals
$[t_{0},t_{1}]$ and $[t_{6},t_{7}]$ respectively, the ${\mathit{underway(v)}}$
state holds for the intervals $\\{[t_{2},t_{5}],[t_{9},\infty)\\}$, the input
state ${\mathit{in\\_fishing\\_area}}$ holds for the interval $[t_{3},t_{4}]$
and finally the dynamic temporal phenomenon
${\mathit{fishing\\_trip(v,a,f,b)}}$ holds for the interval $[t_{1},t_{6}]$.
As the window advances, all the intervals that are redundant (dashed
underlined) can be discarded since they can no longer contribute in a future
query and fall outside the window. However, the interval $[t_{6},t_{7}]$ where
${\mathit{moored(v,b)}}$ holds must be retained, since at window $\omega$ it
participates in the incomplete evaluations of the dynamic temporal phenomena
${\mathit{fishing\\_trip(v,a,f,b)}}$ and ${\mathit{fishing\\_trip(v,b,f,b)}}$.
In other words, it may participate in a detection of
${\mathit{fishing\\_trip(v,a,f,b)}}$ or ${\mathit{fishing\\_trip(v,b,f,b)}}$
in a future query.

Incomplete evaluations can only occur for dynamic temporal phenomena as per
the fact that their detection requires information that sometimes is not yet
available. However, this is not the case for evaluations of events and states;
since at any given query time and a working memory $\mathit{WM}$ the instants
or intervals at which they are true or hold can always be determined. Note
though that intervals may be updated if new information allows it. For
example, a formula $\phi\rightarrowtail\psi$ can be true at an interval
$[ts,\infty)$ at query time $t_{q}$ while at a query time
$t_{q}^{\prime}>t_{q}$ the interval may get updated to $[ts,te]$ if there is a
satisfaction of $\psi\wedge\neg\phi$ at $te>t_{q}$.

The feasibility of an incomplete evaluation of a user defined dynamic temporal
phenomenon is determined by propagating the temporal constraints imposed by
its definition and by also taking into account the information of the current
${\mathit{WM}}$. If the evaluation status of a formula $\phi\in\Phi^{=}$ at
query $t_{q}$ is unknown then all the participating time associated phenomena
should be retained for the re-evaluation of $\phi$ in future queries.
Consequently, at each query time, in order to label ${\mathit{WM}}$ elements
as redundant or not, apart from evaluations of temporal phenomena that can be
determined to be true or false, incomplete evaluations whose validity status
is unknown must also be computed.

$\omega$$\omega^{\prime}$$\mathit{T}$$\mathit{t_{q}-|\omega|}$$\mathit{t_{0}}$$\mathit{t_{1}}$$\mathit{t_{2}}$$\mathit{t_{3}}$$\mathit{t_{4}}$$\mathit{t_{5}}$$\mathit{t_{6}}$$\mathit{t_{7}}$$\mathit{t_{q^{\prime}}-|\omega|}$$\mathit{t_{9}}$$\mathit{t_{q}}$$\mathit{t_{9}}$$\mathit{t_{10}}$$\mathit{t_{11}}$$\mathit{t_{12}}$$\mathit{t_{13}}$${\mathit{fishing\\_trip(v,b,f,b)}}$${\mathit{fishing\\_trip(v,a,f,b)}}$${\mathit{in\\_fishing\\_area(v,f)}}$${\mathit{underway(v)}}$${\mathit{moored(v,b)}}$${\mathit{moored(v,a)}}$

Figure 1: Example of redundant (dashed underlined) and non redundant
intervals, after the transition from window $\omega$ to $\omega^{\prime}$.
Horizontal black bold and hollow lines correspond to evaluations of phenomena
with all the required information, while grey lines correspond to evaluations
with incomplete information. Bold black lines denote intervals that are
computed during $\omega$, while hollow black lines denote intervals that are
computed during $\omega^{\prime}$.

In order to present the mechanism that classifies redundancy we introduce the
concept of incomplete intervals. An incomplete interval
$i_{inc}=[t,t_{\circ}]$ is a pair of a known time instant and an unknown
value111We extend the set of all allowed values with $t_{\circ}$ denoting a
time instant that is currently not known but the domain of its possible values
is known. ${\mathit{t_{\circ}}}$ with a known domain $D_{t_{\circ}}\subset T$.
Incomplete intervals are produced when the evaluation status of a
$\phi\in\Phi^{=}$ formula is unknown, while the domains of the unknown instant
values are created by propagating the formula constraints. Given a working
memory ${\mathit{WM}}$ the validity status of a formula of $\Phi^{=}$ is
unknown iff one of the following cases is true:

  * •

the evaluation status of a formula $\phi\ \textsf{\small before}\ \psi$ is
unknown iff for the last ending interval(s) $\\{[ts_{1},t],...,[ts_{k},t]\\}$
where $\phi$ holds ($\phi\in\Phi^{-}\cup\Phi^{=}$) or the last instant $t$
where $\phi$ is true
($\phi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$),
there not exists an instant $t^{\prime}$
($\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$)
or an interval $[t^{\prime},te^{\prime}]$ ($\psi\in\Phi^{-}\cup\Phi^{=}$) with
$t^{\prime}>t$ where $\psi$ is true or holds respectively, in which case the
associated incomplete intervals are $[ts_{i},t_{\circ}]$, $i\in[1,k]$ when
$\phi\in\Phi^{-}\cup\Phi^{=}$ or $[t,t_{\circ}]$ when
$\phi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
with $D_{t_{\circ}}=[t+2,\infty)$,

  * •

the evaluation status of a formula $\phi\ \textsf{\small contains}\ \psi$ is
unknown iff $\phi$ holds for an interval $[ts,\infty)$ and there not exists an
instant $t$, $t>ts$
($\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$)
or an interval $[ts^{\prime},te^{\prime}]$ with $ts<ts^{\prime}$
($\psi\in\Phi^{-}\cup\Phi^{=}$) where $\psi$ is true or holds respectively, in
which case the associated incomplete interval is $[ts,t_{\circ}]$ with
$D_{t_{\circ}}=(t_{q},\infty)$.

  * •

the evaluation status of a formula $\phi\ \textit{relation}\ \psi$ where
relation $\in\\{\textsf{\small equals},\textsf{\small starts}\\}$ is unknown
iff $\phi$ and $\psi$ hold for an interval $[ts,\infty)$ in which case the
associated incomplete interval is $[ts,t_{\circ}]$ with
$D_{t_{\circ}}=(t_{q},\infty)$.

  * •

the evaluation status of a formula $\phi\ \textit{relation}\ \psi$ where
$\textit{relation}\in\\{\textsf{\small before}$, meets, overlaps,
$\textsf{\small finishes}\\}$, $\phi\in\Phi^{-}\cup\Phi^{=}$ and $\psi\in\Phi$
is unknown iff $\phi$ holds for an interval $[ts,\infty)$, in which case the
associated incomplete interval is $[ts,t_{\circ}]$ with
$D_{t_{\circ}}=[t_{q}+2,\infty)$.

  * •

the evaluation status of a formula $\phi\ {\mathit{relation}}\ \psi$ where
${\mathit{relation}}$ is a temporal relation,
$\phi,\psi\in\Phi^{-}\cup\Phi^{=}$, is unknown, iff the evaluation status of
$\phi$ or $\psi$ is unknown and the domains of the unknown instants allow a
feasible solution to the $\phi\ {\mathit{relation}}\ \psi$ formula’s
constraints.

At a query time $t_{q}$, intervals or instants at which a formula
$\phi\in\Phi$ is true, ending or occurring before the start of the next window
$t_{q}-\omega+s$, and participating in evaluations with unknown validity are
classified as non-redundant since their presence will be possibly required in
the re-evaluations of the formulae with unknown validity in future recognition
queries. Moreover, intervals or instants that hold or occur before the start
of the next window $t_{q}-\omega+s$ are also retained if they participate in
complete evaluations of formulae that hold for intervals that overlap
$t_{q}-\omega+s$, therefore ensuring that recognised entities that hold on
intervals that overlap the next window will also be available for processing
in the next recognition query.

###  4.2 Processing of temporal phenomena

The set of time instants or intervals at which input phenomena are true or
hold is provided by the input. In the case of user defined phenomena the
corresponding sets have to be computed by processing their definitions. In
this section we present the methodology for processing the formulae that
comprise temporal phenomena definitions.

####  4.2.1 Events

Events are defined by means of $\phi\ \in\
\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
formulae. The methodology for computing the set of time instants at which a
formula
$\phi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
is true is described below.

  * •

Conjunction (Disjunction) If $\phi$ and $\psi$ are
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
formulae and are true respectively at the time instants sets $J$ and $K$
$\subseteq\omega$ then their conjunction (disjunction) is described by the set
$C=J\cap K$ ($C=J\cup K$).

  * •

Negation If $\phi$ is a formula of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
and $J$ is the set of instants where $\phi$ is true in $\omega$, then
$\neg\phi$ is true in the set of instants $C=\omega\setminus J$.

  * •

Start (end) Start (end) accept a formula $\phi$ of $\Phi^{-}$ and return the
starting (ending) points of the intervals the formula $\phi$ holds.

####  4.2.2 States

User-defined states are expressed via the formulae of $\Phi^{-}$. By
definition the intervals at which a state may hold are disjoint and maximal;
this is because formulae of $\Phi^{-}$ utilise the temporal operators
$\rightarrowtail,\sqcup,\sqcap$ and $\setminus$ which, as defined in Section
2.3, will always hold on disjoint maximal intervals. Below we describe the
computation of these intervals for each operator.

Maximal range Given a working memory ${\mathit{WM}}$ a formula
$\phi\rightarrowtail\psi$ for $\phi,\psi\in\Phi$ holds for the intervals that
start at the instant $t_{s}$ where $\phi$ is true and continue to hold
indefinitely unless at an instant $t_{e}>t_{s}$, $\psi\wedge\neg\phi$ is true.
In Appendix 0.A.1 we present the single-scan algorithm that computes the
intervals at which a formula $\phi\rightarrowtail\psi$ for
$\phi,\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
holds.

Temporal union, intersection and complement In plain language, for $\phi$ and
$\psi$ formulae of $\Phi^{-}$ the temporal operators are defined as follows.
The temporal union $\phi\sqcup\psi$, holds for the maximal intervals where at
least one of $\phi$ and $\psi$ holds. The temporal intersection of
$\phi\sqcap\psi$ formulae holds for the maximal intervals where both formulae
hold together. Finally, the temporal complement $\phi\setminus\psi$ holds for
the maximal sub-intervals of the intervals where $\phi$ holds and $\psi$ does
not hold. Figure 2 illustrates an example of these operations. The computation
of the intervals resulting from these operators can be computed efficiently
using single-scan, sorting-based or index-based algorithms [13]. Since these
algorithms appear widely in related bibliography [13, 9], for our setting, we
describe only the single-scan algorithm, presented in [13], for temporal union
in Appendix 0.A.2.

$\mathit{T}$$\mathit{t_{0}}$$\mathit{t_{1}}$$\mathit{t_{2}}$$\mathit{t_{3}}$$\mathit{t_{4}}$$\mathit{t_{5}}$$\phi\setminus\psi$$\phi\sqcap\psi$$\phi\sqcup\psi$$\psi$$\phi$
Figure 2: Example of the resulting intervals for the temporal operators
$\sqcup,\sqcap$ and $\setminus$ between fomulae $\phi$ and $\psi$ of
$\Phi^{-}$.

####  4.2.3 Dynamic temporal phenomena

Dynamic temporal phenomena are defined using formulae of $\Phi^{=}$ and may
hold in non-disjoint intervals. Given a working memory ${\mathit{WM}}$, the
intervals at which dynamic temporal phenomena hold can be computed using the
declarative semantics. When the formulae participating in a temporal relation
are either of
$\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
or $\Phi^{-}$ efficient linear complexity algorithms are possible since the
instants or the disjoint set of intervals at which they hold are ordered. In
Appendix 0.A.3 we present the linear complexity algorithm that computes the
intervals where $\phi\ \textsf{\small before}\ \psi$ with
$\phi,\psi\in\Phi^{-}$ holds. When the participating formulae involve those of
$\Phi^{=}$, that may hold on non-disjoint intervals, a naive approach that
checks all pairs of the participating time entities requires polynomial time.
However, with indexes such as range trees, the intervals at which temporal
relations with participating formulae of $\Phi^{=}$ hold can be computed in
linearithmic time [17].

##  5 Related work

There are numerous languages for describing temporal phenomena with different
levels of expressiveness. For example, P. Balbiani et al. in [6] present a
two-sorted point-interval temporal logic framework where both instants and
intervals can be used in formulae. However, in P. Balbiani’s approach,
operations such as the maximal range, union, intersection and complement are
not available, therefore phenomena that utilise these operators (e.g., the
definition of ${\mathit{moored/2}}$ in Section 3) are not directly, if at all,
expressible in their language. Moreover, neither executable semantics nor
applications of their temporal logic are discussed. A. Ahmed et al. in [1] use
point-based metric temporal logic that has limited interval expressivity to
specify stream queries for intrusion detection. Kowalski in [16] presents the
Event Calculus, a logic based formalism that deals with events (instantaneous)
and their effects on inertive fluents (durative), i.e., time-varying
properties.

In the field of complex event processing or recognition, G. Cugola et al. in
[12] formally present an event specification language, TESLA, that allows the
definition of possibly hierarchical complex event patterns that happen on
instants of time. In [4] D. Anicic et al. present ETALIS, a rule based system
where complex events are durative and their definition among others may
involve sequences of events, negation and some of the Allen’s algebra
relations. Compared to TESLA and ETALIS our language allows the description of
both instantaneous and durative temporal phenomena. Efficient complex event
recognition approaches using the Event Calculus among others involve [5, 10].
In [5] A. Artikis et. al. present the Event Calculus for Run-Time reasoning.
Their approach allows the definition and processing of possibly hierarchical
events and fluents that happen on instants or hold on intervals. Compared to
the Event Calculi approaches of [5, 10] our language allows the expression of
temporal relations between durative and instantaneous phenomena that may hold,
additionally, in non-disjoint intervals.

##  6 Summary & Future Directions

We formally presented a language for the representation of temporal phenomena,
with declarative and operational semantics. Our language allows the
representation of possibly hierarchical instantaneous and durative temporal
phenomena. Definitions of temporal phenomena may involve the standard logical
connectives, temporal operators of maximal range, union, intersection and
complement and the seven basic temporal relations of Allen’s algebra relations
of intervals. An open-source Prolog implementation of a Complex Event
Processing system called ‘Phenesthe’ utilising the language and the
operational semantics presented in this paper is available in [21].

Our future directions involve a scalability study of ‘Phenesthe’ and a
demonstration of its efficiency using real world maritime data. Moreover, we
aim to evaluate theoretically the expressiveness of our language and compare
it with existing ones. Finally, we aim to integrate temporal stream processing
with process mining techniques for the discovery of dynamic temporal
phenomena.

## References

  * [1] Ahmed, A., Lisitsa, A., Dixon, C.: A misuse-based network intrusion detection system using temporal logic and stream processing. In: 2011 5th International Conference on Network and System Security. pp. 1–8 (2011). https://doi.org/10.1109/ICNSS.2011.6059953
  * [2] Allen, J.F.: Maintaining knowledge about temporal intervals. Communications of the ACM 26(11), 832–843 (Nov 1983). https://doi.org/10.1145/182.358434
  * [3] Anicic, D., Fodor, P., Rudolph, S., Stühmer, R., Stojanovic, N., Studer, R.: A Rule-Based Language for Complex Event Processing and Reasoning, Lecture Notes in Computer Science, vol. 6333, p. 42–57. Springer Berlin Heidelberg (2010). https://doi.org/10.1007/978-3-642-15918-3_5
  * [4] Anicic, D., Rudolph, S., Fodor, P., Stojanovic, N.: Stream reasoning and complex event processing in etalis. Semantic Web 3(4), 397–407 (2012). https://doi.org/10.3233/SW-2011-0053
  * [5] Artikis, A., Sergot, M., Paliouras, G.: An event calculus for event recognition. IEEE Transactions on Knowledge and Data Engineering 27(4), 895–908 (2015). https://doi.org/10.1109/TKDE.2014.2356476
  * [6] Balbiani, P., Goranko, V., Sciavicco, G.: Two-sorted point-interval temporal logics. Electronic Notes in Theoretical Computer Science 278, 31–45 (Nov 2011). https://doi.org/10.1016/j.entcs.2011.10.004
  * [7] Beck, H., Dao-Tran, M., Eiter, T.: Lars: A logic-based framework for analytic reasoning over streams. Artificial Intelligence 261, 16–70 (Aug 2018). https://doi.org/10.1016/j.artint.2018.04.003
  * [8] Bellini, P., Mattolini, R., Nesi, P.: Temporal logics for real-time system specification. ACM Comput. Surv. 32(1), 12–42 (Mar 2000). https://doi.org/10.1145/349194.349197
  * [9] Bohlen, M.H., Busatto, R., Jensen, C.S.: Point-versus interval-based temporal data models. In: Proceedings 14th International Conference on Data Engineering. pp. 192–200 (1998). https://doi.org/10.1109/ICDE.1998.655777
  * [10] Chittaro, L., Montanari, A.: Efficient temporal reasoning in the cached event calculus. Computational Intelligence 12(3), 359–382 (Aug 1996). https://doi.org/10.1111/j.1467-8640.1996.tb00267.x
  * [11] Chomicki, J.: Temporal query languages: A survey. In: Gabbay, D.M., Ohlbach, H.J. (eds.) Temporal Logic. p. 506–534. Springer Berlin Heidelberg (1994)
  * [12] Cugola, G., Margara, A.: Tesla: a formally defined event specification language. In: DEBS ’10. p. 50. ACM Press (2010). https://doi.org/10.1145/1827418.1827427
  * [13] Dohr, A., Engels, C., Behrend, A.: Algebraic operators for processing sets of temporal intervals in relational databases. In: TIME (2018)
  * [14] Horng-Yuan Chen, Jeffrey J. P. Tsai, Yaodong Bi: An event-based real-time logic to specify the behavior and timing properties of real-time systems. In: Proceedings of the Third International Conference on Tools for Artificial Intelligence - TAI 91. pp. 210–219 (1991). https://doi.org/10.1109/TAI.1991.167097
  * [15] Khan, A., Bozzato, L., Serafini, L., Lazzerini, B.: Visual reasoning on complex events in soccer videos using answer set programming. In: Calvanese, D., Iocchi, L. (eds.) GCAI 2019. Proceedings of the 5th Global Conference on Artificial Intelligence. EPiC Series in Computing, vol. 65, pp. 42–53 (2019). https://doi.org/10.29007/pjd4
  * [16] Kowalski, R., Sergot, M.: A logic-based calculus of events. New Generation Computing 4(1), 67–95 (Mar 1986). https://doi.org/10.1007/BF03037383
  * [17] Mao, C., Eran, A., Luo, Y.: Efficient genomic interval queries using augmented range trees. Scientific Reports 9(1), 5059 (Mar 2019). https://doi.org/10.1038/s41598-019-41451-3
  * [18] Mileo, A., Abdelrahman, A., Policarpio, S., Hauswirth, M.: Streamrule: A nonmonotonic stream reasoning system for the semantic web. In: Faber, W., Lembo, D. (eds.) Web Reasoning and Rule Systems. pp. 247–252. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)
  * [19] Mueller, E.T.: Chapter 5 - the commonsense law of inertia. In: Mueller, E.T. (ed.) Commonsense Reasoning (Second Edition), pp. 77–89. Morgan Kaufmann, Boston, second edition edn. (2015). https://doi.org/10.1016/B978-0-12-801416-5.00005-X
  * [20] Pitsikalis, M., Artikis, A., Dreo, R., Ray, C., Camossi, E., Jousselme, A.L.: Composite event recognition for maritime monitoring. In: DEBS (2019). p. 163–174. Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3328905.3329762, https://doi.org/10.1145/3328905.3329762
  * [21] Pitsikalis, M., Lisitsa, A., Luo, S.: Phenesthe (10 2021), https://github.com/manospits/Phenesthe
  * [22] Roy, J.: Rule-based expert system for maritime anomaly detection. In: Carapezza, E.M. (ed.) Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense IX. vol. 7666, pp. 597 – 608. International Society for Optics and Photonics, SPIE (2010). https://doi.org/10.1117/12.849131

##  Appendix 0.A Algorithms

###  0.A.1 Maximal range

Algorithm 2, describes the computation of the intervals at which a formula
$\phi\rightarrowtail\psi$ where
$\phi,\psi\in\Phi^{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$
holds. ${\mathit{ST}}$ is a chronologically sorted set comprised of triplets
$(t,\phi_{bool},\psi_{bool})$, where $t$ is a time instant at which at least
one of $\phi$ or $\psi$ holds, and $\phi_{bool}$, $\psi_{bool}$ are boolean
values denoting the truth value of $\phi$ and $\psi$ at the instant $t$.
Finally, ${\mathit{MI}}$ is the resulting interval set.

Input: $ST$ chronologically sorted set

Result: ${\mathit{MI}}$ Ordered disjoint interval set

1 started=Null;

2 for  _$i$ in ST_ do

3 if  _$i.\phi_{bool}$ and started==Null_ then

4 started=$i.t$

5 if  _$i.\psi_{bool}$ and $\neg$ $i.\phi_{bool}$ and started$\neq$Null_ then

6 MI.append([started,i.t]);

7 started=Null

8

9 if  _started $\neq$ Null_ then

10 MI.append([started,$\infty$])

Algorithm 2 Computation of a state’s intervals.

Computation of the intervals where $\phi\rightarrowtail\psi$ holds is achieved
by iterating over the instants where $\phi,\psi$ are true. An interval is
added in the ${\mathit{MI}}$ set when the earliest instant at which
$\psi\wedge\neg\phi$ is true is processed after the earliest instant at which
$\phi$ is true (lines 2-7). An open to infinity interval is added in the
${\mathit{MI}}$ if there isn’t an instant where $\psi\wedge\neg\phi$ is true
occurring after the earliest instant where $\phi$ is true (8-9).

###  0.A.2 Temporal union

Consider the formulae $\phi,\psi\in\Phi^{-}$, the sets
$Int_{\phi}=\\{[ts,te]\in
I_{\omega}:\mathcal{M}_{\omega},[ts,te]\models\phi\\}$,
$Int_{\psi}=\\{[ts,te]\in
I_{\omega}:\mathcal{M}_{\omega},[ts,te]\models\psi\\}$, then the temporal
union $\phi\sqcup\psi$ holds for the intervals computed by the Algorithm 3 as
follows.

Input: SE ordered starting/ending instants

Result: UI Ordered disjoint interval set

1 starting_points,ending_points=0;

2 for  _i in SE_ do

3 if  _$i.s$_ then

4 if  _starting_points =0_ then $ts=i.t$;

5 starting_points+=$i.s$;

6

7 if  _$i.e$_ then

8 ending_points+=$i.e$;

9

10 if  _$s==e$ and $s>0$_ then

11 UI.append([$ts,i.t$]);

12 starting_points,ending_points=0;

13

14

15 if  _starting_points ¿ ending_points_ then UI.append([started,$\infty$]);

Algorithm 3 Temporal union.

‘${\mathit{SE}}$’ is a list of triplets $(t,s,e)$ ordered on $t$; $t$ is an
instant that is a starting or ending point of an interval in $Int_{\phi}\cup
Int_{\psi}$ and $s$, $e$ are integer values $\in\\{0,1,2\\}$ denoting the
number of times $t$ is a starting point or an ending point in the intervals of
$Int_{\phi}\cup Int_{\psi}$. Finally, ‘UI’ contains the intervals where
$\phi\sqcup\psi$ holds. ‘UI’ is computed with the use of the two counters
‘starting_points’ and ‘ending_points’ corresponding to the number each instant
is a starting or ending point respectively. When the two counters become equal
an interval that starts from the instant $t$ that first increased
‘starting_points’ from 0 (lines 4,5) and ends at the instant $t$ that caused
‘starting_points==ending_points’ is added in UI (lines 8-10). If by the end of
all the iterations, the number of ‘starting_points’ is greater than the
‘ending_points’ then an interval open to infinity is appended in UI (line 11).

###  0.A.3 Temporal relation: before

The intervals at which $\phi\ \textsf{\small before}\ \psi$ where
$\phi,\psi\in\Phi^{-}$ holds are computed by Algorithm 4 in linear time.
$\phi_{{\mathit{ints}}}$, $\psi_{{\mathit{ints}}}$ are sets containing the
disjoint intervals at which $\phi$ or $\psi$ hold, ${\mathit{BI}}$ is the set
containing the computed intervals and $i_{inc}$ is an incomplete interval if
available. With the use of the two counters $i,y$, the end of the current
interval of $\phi_{{\mathit{ints}}}$ is checked if it is before the current
interval of $\psi_{{\mathit{ints}}}$. If this condition is not satisfied the
loop will continue until an interval of $\psi_{{\mathit{ints}}}$ is found that
satisfies the condition (lines 3-5). When the end of the current interval of
$\phi_{{\mathit{ints}}}$ is less than the start of the current interval of
$\psi_{{\mathit{ints}}}$ the algorithm continues by checking whether there are
any subsequent intervals in $\phi_{{\mathit{ints}}}$ that end later than the
start of the current interval of $\psi_{{\mathit{ints}}}$ (lines 6-9). This
ensures that the current interval of $\phi_{{\mathit{ints}}}$ is directly
before the current interval of $\psi_{{\mathit{ints}}}$. In line 10, the
resulting interval is added in ${\mathit{BI}}$. If there are intervals still
in $\phi_{{\mathit{ints}}}$ but no intervals of $\psi_{{\mathit{ints}}}$
remaining incomplete intervals are created according to the rules presented in
Section 4 (lines 12,15).

Input: $\phi_{{\mathit{ints}}}$, $\psi_{{\mathit{ints}}}$ the ordered interval
sets where $\phi$ or $\psi$ hold, and $t_{q}$ the current query time.

Result: ${\mathit{BI}}$ Ordered interval set, and $BI_{inc}$ incomplete
interval set.

1 i,y=0; $i_{inc}$=Null;

2 while  _i $<|\phi_{{\mathit{ints}}}|$_ do

3 while  _y $<|\psi_{{\mathit{ints}}}|$_ do

4 if  _$\phi_{{\mathit{ints}}}$[i].end $<\psi_{{\mathit{ints}}}$[y].start_
then break ;

5 y++;

6 if  _y $<|\psi_{{\mathit{ints}}}|$_ then

7 while  _i+1 $<|\phi_{{\mathit{ints}}}|$_ do

8 if  _$\phi_{{\mathit{ints}}}$[i+1].end $<\psi_{{\mathit{ints}}}$[y].start_
then i++;

9 else break ;

10

11
BI.append([$\phi_{{\mathit{ints}}}$[i].start,$\phi_{{\mathit{ints}}}$[i].end]);

12 i++;

13

14 else

15 $BI_{inc}$=create_incomplete_intervals($\phi_{{\mathit{ints}}}$,i,$t_{q}$);

16 break ;

17

18

Algorithm 4 Computation of the intervals a $\phi\ \textsf{\small before}\
\psi$ relation holds for $\phi,\psi\in\Phi^{-}$.