A Boyer-Moore type algorithm for timed pattern matching

DOI10.1007/978-3-319-44878-7_8MaRDI QIDQ4603563zbMATH OpenOpenAlexFDO

Authors Masaki Waga, Takumi Akazaki, Ichiro Hasuo

Publication date 16 February 2018

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.07207

Analysis of algorithms (68W40) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Algorithms on strings (68W32)

Abstract: The timed pattern matching problem is formulated by Ulus et al. and has been actively studied since, with its evident application in monitoring real-time systems. The problem takes as input a timed word/signal and a timed pattern (specified either by a timed regular expression or by a timed automaton); and it returns the set of those intervals for which the given timed word, when restricted to the interval, matches the given pattern. We contribute a Boyer-Moore type optimization in timed pattern matching, relying on the classic Boyer-Moore string matching algorithm and its extension to (untimed) pattern matching by Watson and Watson. We assess its effect through experiments; for some problem instances our Boyer-Moore type optimization achieves speed-up by two times, indicating its potential in real-world monitoring tasks where data sets tend to be massive.

Recommendations

Cited in

(8)

Describes a project that uses

Uses Software

This page was built for publication: A Boyer-Moore type algorithm for timed pattern matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603563)