Title: Efficient Online Timed Pattern Matching by Automata-Based Skipping,
Abstract: The timed pattern matching problem is an actively studied topic because of
its relevance in monitoring of real-time systems. There one is given a log $w$
and a specification $\mathcal{A}$ (given by a timed word and a timed automaton
in this paper), and one wishes to return the set of intervals for which the log
$w$, when restricted to the interval, satisfies the specification
$\mathcal{A}$. In our previous work we presented an efficient timed pattern
matching algorithm: it adopts a skipping mechanism inspired by the classic
Boyer--Moore (BM) string matching algorithm. In this work we tackle the problem
of online timed pattern matching, towards embedded applications where it is
vital to process a vast amount of incoming data in a timely manner.
Specifically, we start with the Franek-Jennings-Smyth (FJS) string matching
algorithm---a recent variant of the BM algorithm---and extend it to timed
pattern matching. Our experiments indicate the efficiency of our FJS-type
algorithm in online and offline timed pattern matching.