We consider the problem of identifying patterns of interest in colored strings. A colored string is a string in which each position is colored with one of a finite set of colors. Our task is to find substrings  that always occur followed by the same color at the same distance. The problem is motivated by applications in embedded systems verification, in particular, assertion mining. The goal there is to automatically infer properties of the embedded system from the analysis of its simulation traces. We show that  the number of interesting patterns is upper-bounded by O(n^2)  where n is the length of the string. We introduce a baseline algorithm with \mathcal{O}(n^2) running time which identifies all interesting patterns for all colors in the string satisfying certain minimality conditions. When one is interested in patterns related to only one color , we provide an algorithm that identifies patterns in \mathcal{O}(n^2\log n) time , but is faster than the first algorithm in practice , both on simulated and on real-world patterns.
In this paper, we consider the problem of identifying patterns of interest in colored strings. A colored string is a string where each position is assigned one of a finite set of colors. Our task is to find substrings of the colored string that always occur followed by the same color at the same distance. The problem is motivated by applications in embedded systems verification, in particular, assertion mining. The goal there is to automatically find properties of the embedded system from the analysis of its simulation traces. We show that , in our setting, the number of patterns of interest is upper-bounded by O(n^2) , where n is the length of the string. We introduce a baseline algorithm , running in \mathcal{O}(n^2) time, which identifies all patterns of interest satisfying certain minimality conditions, for all colors in the string . For the case where one is interested in patterns related to one color only, we also provide a second algorithm which runs in \mathcal{O}(n^2\log n) time in the worst case but is faster than the baseline algorithm in practice . Both solutions use suffix trees, and the second algorithm also uses an appropriately defined priority queue, which allows us to reduce the number of computations. We performed an experimental evaluation of the proposed approaches over both synthetic and real-world datasets, and found that the second algorithm outperforms the first algorithm on all simulated data, while on the real-world data, the performance varies between a slight slowdown (on half of the datasets) and a speedup by a factor of up to 11.
R
We
In this paper, we
R
in which
where
R
colored with
assigned
A
of the colored string
R
infer
find
A
, in our setting,
R
interesting patterns
patterns of interest
A
,
R
with
, running in
R
running time
time,
R
interesting patterns
patterns of interest satisfying certain minimality conditions,
R
satisfying certain minimality conditions. When
. For the case where
R
only one color , we provide an algorithm that identifies patterns
one color only, we also provide a second algorithm which runs
R
,
in the worst case
R
first
baseline
R
, both on simulated and on
. Both solutions use suffix trees, and the second algorithm also uses an appropriately defined priority queue, which allows us to reduce the number of computations. We performed an experimental evaluation of the proposed approaches over both synthetic and
R
patterns.
datasets, and found that the second algorithm outperforms the first algorithm on all simulated data, while on the real-world data, the performance varies between a slight slowdown (on half of the datasets) and a speedup by a factor of up to 11.