Jochen Messner
Abstract:
An algorithm is presented solving the factor problem in trace monoids.
Given two traces represented by words, the algorithm determines in
linear time whether the first trace is a factor of the second one. The
space used for this task is linear in the length of the first word.
Similar to the Knuth-Morris-Pratt Algorithm for the factor problem on
words, the algorithm simulates a finite automaton determined by the
first word on the second word. To develop the algorithm, we examine
overlaps of two traces, and show that they form a lattice. Finally we
investigate the lattice of extensible trace pairs (which represent still
extensible prefixes of a searched factor appearing in some other trace),
because of their close relations to the structures used by the
algorithm.