Name
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 extensible trace pairs (which represent still extensible prefixes of a searched factor appearing in some other trace), and show that both structures are lattices. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/BFb0023490 | STACS |
Keywords | Field | DocType |
extended abstract,trace monoids,pattern matching,linear time,finite automaton | Discrete mathematics,Algebra,Monoid,Pattern matching,Mathematics | Conference |
Volume | ISSN | ISBN |
1200 | 0302-9743 | 3-540-62616-6 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jochen Meßner | 1 | 13 | 1.19 |
| J Messner | 2 | 13 | 1.19 |