Online Timed Pattern Matching Using Derivatives
Online Timed Pattern Matching Using Derivatives
复制标题
使用导数的在线定时模式匹配
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
O. Maler
中科院分区：
文献类型：
--
作者：
Dogan Ulus;Thomas Ferrère;E. Asarin;O. Maler
定时模式匹配在于找到由定时正则表达式定义的密集时间布尔信号的所有片段。产生所有匹配的集合，以二维区域为有限的联合。
自然，由于读取信号的前缀后，由于brzozowskii¾而引起的正则表达式的概念可以在定义剩下的匹配方面发挥作用。定时行为的密集无限状态以及我们对匹配感兴趣的事实，不仅是对这些问题的前缀接受。然后，我们根据这些结果实现了在线定时模式匹配算法。
Timed pattern matching consists in finding all segments of a dense-time Boolean signal that match a pattern defined by a timed regular expression. This problem has been formulated and solved in [17] via an offline algorithm that takes the signal and expression as inputs and produces the set of all matches, represented as a finite union of two-dimensional zones. In this work we develop an online version of this approach where the input signal is presented incrementally and the matching is computed incrementally as well.
Naturally, the concept of derivatives of regular expressions due to Brzozowskii¾?[6] can play a role in defining what remains to match after having read a prefix of the signal. However the adaptation of this concept is not a straightforward for two reasons: the dense infinite-state nature of timed behaviors and the fact that we are interested in matching, not only in prefix acceptance. To resolve these issues we develop an alternative theory of signals and expressions based on absolute time and show how derivatives are defined and computed in this setting. We then implement an online timed pattern matching algorithm based on these results.