A Boyer-Moore Type Algorithm for Timed Pattern Matching
A Boyer-Moore Type Algorithm for Timed Pattern Matching
复制标题
一种Boyer-Moore型定时模式匹配算法
DOI：
10.1007/978-3-319-44878-7_8
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ichiro Hasuo
中科院分区：
文献类型：
--
作者：
Masaki Waga;Takumi Akazaki;Ichiro Hasuo
时间模式匹配问题是由Ulus等人提出的，并在实时监控系统中得到了广泛的应用。该问题需要作为输入的定时字/信号和定时模式（由定时正则表达式或定时自动机指定）;它返回的一组时间间隔的给定定时字，当限制到该时间间隔时，匹配给定的模式。基于经典的Boyer-Moore字符串匹配算法及其由沃森和沃森扩展到（非定时）模式匹配的方法，我们提出了一种Boyer-Mooretype优化算法。我们通过实验来评估其效果;对于某些问题实例，我们的Boyer-Moore类型优化实现了两倍的速度提升，表明其在数据集往往很大的实际监控任务中的潜力。
Thetimed pattern matchingproblem 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 atimed word/signaland atimed pattern(specified either by atimed regular expressionor by atimed 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 aBoyer-Mooretype 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.
登录
查看更多内容
使用导数的在线定时模式匹配
DOI：
--
发表时间：
2016
期刊：
International Conference on Tools and Algorithms for Construction and Analysis of Systems
影响因子：
--
作者：
Dogan Ulus;Thomas Ferrère;E. Asarin;O. Maler
通讯作者：
O. Maler
使用定时模式进行测量
DOI：
10.1007/978-3-319-21668-3_19
发表时间：
2015
期刊：
Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Thomas Ferrère;O. Maler;D. Ničković;Dogan Ulus
通讯作者：
Dogan Ulus
用于正则表达式模式匹配的 Boyer-Moore 风格算法
DOI：
10.1016/s0167-6423(03)00013-3
发表时间：
2003
期刊：
Sci. Comput. Program.
影响因子：
--
作者：
Bruce W. Watson;Richard E. Watson
通讯作者：
Richard E. Watson
定时模式匹配
DOI：
--
发表时间：
2014
期刊：
International Conference on Formal Modeling and Analysis of Timed Systems
影响因子：
--
作者：
Dogan Ulus;Thomas Ferrère;E. Asarin;O. Maler
通讯作者：
O. Maler
FPGA 上的运行时观察器对和贝叶斯网络推理器：嵌入式系统的飞行认证系统健康管理
DOI：
10.1007/978-3-319-11164-3_18
发表时间：
2014
期刊：
2020 Design, Automation & Test in Europe Conference & Exhibition (DATE)
影响因子：
--
作者：
J. Geist;Kristin Y. Rozier;Johann Schumann
通讯作者：
Johann Schumann