DocumentCode
1844647
Title
Automata for Weak Factor Recognition
Author
Zhang, Meng ; Zhang, Yi ; Zhao, Kuo ; Hu, Liang
Author_Institution
Coll. of Comput. Sci. & Technol., Jilin Univ., Changchun
fYear
2008
fDate
18-21 Nov. 2008
Firstpage
1771
Lastpage
1776
Abstract
In this paper, a family of automata for weak factor recognition named weak factor automaton (WFA) is introduced. WFAs can at least recognize the factors of a word and have similar properties of the factor oracle. WFAs are not always acyclic and the acyclic WFA is equivalent to the factor oracle with redundant edges. Based on the same approach, a new weight automaton for precise full-text index is introduced. A simple linear on-line construction algorithm for these two classes of automata is also given.
Keywords
automata theory; graph theory; pattern recognition; full-text index; linear online construction algorithm; weak factor automaton; weak factor recognition; Automata; Compaction; Computer science; Educational institutions; Machine learning; Pattern matching; Tree graphs; DAWG; String matching; automaton; factor oracle; full text index;
fLanguage
English
Publisher
ieee
Conference_Titel
Young Computer Scientists, 2008. ICYCS 2008. The 9th International Conference for
Conference_Location
Hunan
Print_ISBN
978-0-7695-3398-8
Electronic_ISBN
978-0-7695-3398-8
Type
conf
DOI
10.1109/ICYCS.2008.395
Filename
4709242
Link To Document