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
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;
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
DOI :
10.1109/ICYCS.2008.395
