Skip to Main content Skip to Navigation
Journal articles

Asymptotic estimation of the average number of terminal states in DAWGs

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00693885
Contributor : Mathieu Raffinot <>
Submitted on : Thursday, May 3, 2012 - 8:58:58 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM

Links full text

Identifiers

Citation

Mathieu Raffinot. Asymptotic estimation of the average number of terminal states in DAWGs. Discrete Applied Mathematics, Elsevier, 1999, 92 (2-3), pp.193--203. ⟨10.1016/S0166-218X(99)00047-5⟩. ⟨hal-00693885⟩

Share

Metrics

Record views

268