Abstract | ||
---|---|---|
The main result of the paper is an efficient parallel construction of factor automata. We show that the construction of directed acyclic word graphs (dawg's) and of minimal suffix and minimal factor automata can be done by almost optimal parallel algorithms (optimal within logarithmic factor). Our constructions have the same parallel complexity as the best known parallel algorithms computing suffix trees. We exploit a simple relation between dawg's and suffix trees. |
Year | DOI | Venue |
---|---|---|
1990 | 10.1016/0020-0190(90)90060-B | Information Processing Letters |
Keywords | DocType | Volume |
factor automata,minimal suffix,parallel construction,factor automaton | Journal | 35 |
Issue | ISSN | ISBN |
3 | 0020-0190 | 3-540-52953-5 |
Citations | PageRank | References |
2 | 0.43 | 10 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Maxime Crochemore | 1 | 2655 | 281.75 |
wojciech rytter | 2 | 130 | 17.13 |