The Prague Stringology Club Workshop '98
The Factor Automaton
| Abstract: |
| The direct acyclic word graph (DAWG) is a good data structure representing a set of strings related to some word with very small space complexity. The famoust DAWG is the factor DAWG which is representing the set Fac(text) of all factors (substrings) of the string text. Bellow we call factor DAWG as DAWG. Finite automaton implementing this data structure is able to make out any substring of string text in time proportional only to length of the substring while its space complexity is linear to the length of the string text. We can define several operations on DAWG. Operations are usefull for fast derivating of the DAWG automaton from a similar one. This paper concern operation L-delete on factor graph DAWG and the relationship between deterministic and nondeterministic factor automaton. |
| Download paper: |  |
 |
| PostScript |