Talk "Efficient Online Timed Pattern Matching by Automata-Based Skipping"

by Ichiro Hasuo

Fri, 06 July 2018 at 10:10 am in Royal Holloway, United Kingdom

Joint work with: Masaki Waga, Kohei Suenaga (FORMATS'17)

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  (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 . 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.