Open AccessOptimal Parallel Construction of Minimal Suffix and Factor Automata
Author(s) -
Dany Breslauer,
Ramesh Hariharan
Publication year - 1995
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v2i16.19884
Subject(s) - suffix tree , suffix , generalized suffix tree , automaton , compressed suffix array , factor (programming language) , computer science , string (physics) , deterministic finite automaton , tree (set theory) , mathematics , algorithm , theoretical computer science , data structure , combinatorics , programming language , philosophy , linguistics , mathematical physics
This paper gives optimal parallel algorithms for the construction of the smallest deterministic finite automata recognizing all the suffixes and the factors of a string. The algorithms use recently discovered optimal parallel suffix tree construction algorithms together with data structures for the efficient manipulation of trees, exploiting the well known relation between suffix and factor automata and suffix trees.