A Boyer-Moore type algorithm for timed pattern matching

DOI10.1007/978-3-319-44878-7_8zbMATH Open1433.68262arXiv1606.07207OpenAlexW2460913653MaRDI QIDQ4603563FDOQ4603563

Authors: Masaki Waga, Takumi Akazaki, Ichiro Hasuo

Publication date: 16 February 2018

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

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.

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

Recommendations

Mathematics Subject Classification ID

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

Cited In (8)

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)