Asymptotic estimation of the average number of terminal states in DAWGs
Raffinot, Mathieu
HAL, hal-00693885 / Harvested from HAL
Following the work of A. Blumer, A. Ehrenfeucht and D. Haussler, we obtain an asymptotic estimation of the average number of terminal states in the suffix directed acyclic word graph (DAWG - also called suffix automaton) under a Bernoulli model. We first extract an expression of the average from the structure of the DAWG. With a Mellin transform, we then obtain an asymptotic expansion of the form In(n)ln(A)+ C(A) + F(n) where n is the size of the word, A the alphabet size, C(A) a function of A, and F an oscillating function with small amplitude. Finally, we compare theoretical results with experimental results. (C) 1999 Elsevier Science B.V. All rights reserved.
Publié le : 1999-07-05
Classification:  [MATH.MATH-MP]Mathematics [math]/Mathematical Physics [math-ph]
@article{hal-00693885,
     author = {Raffinot, Mathieu},
     title = {Asymptotic estimation of the average number of terminal states in DAWGs},
     journal = {HAL},
     volume = {1999},
     number = {0},
     year = {1999},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00693885}
}
Raffinot, Mathieu. Asymptotic estimation of the average number of terminal states in DAWGs. HAL, Tome 1999 (1999) no. 0, . http://gdmltest.u-ga.fr/item/hal-00693885/