DocumentCode
3026790
Title
Parallel Algorithms for Constructing Fellow Automata of Regular Expressions
Author
Yuqiang, Sun ; Ruimin, Yang ; Yuwan, Gu ; Jing, You
Author_Institution
Coll. of Comput. & Inf. Technol., Henan Normal Univ., Xinxiang, China
fYear
2009
fDate
25-26 April 2009
Firstpage
57
Lastpage
60
Abstract
A parallel algorithm for translating regular expression into its Follow automata is proposed in the paper. Firstly, we construct the Thompson automata of a regular expression. Then, the Glushkov automata are achieved by removing xi the path and the equivalent states which have equivalent relations are merged into one. So we can get a smaller finite automata, named Follow automata. Finally the parallel processing of algorithm is described in detail with an example.
Keywords
automata theory; formal languages; parallel algorithms; Follow automata; Glushkov automata; Thompson automata; parallel algorithm; parallel processing; regular expression translation; Application software; Automata; Databases; Educational institutions; Information science; Information technology; Parallel algorithms; Parallel processing; Pattern matching; Sun; Follow automatata; NFA; parallel algorithm; regular expressions; state;
fLanguage
English
Publisher
ieee
Conference_Titel
Database Technology and Applications, 2009 First International Workshop on
Conference_Location
Wuhan, Hubei
Print_ISBN
978-0-7695-3604-0
Type
conf
DOI
10.1109/DBTA.2009.41
Filename
5207814
Link To Document