Asymptotic estimation of the average number of terminal states in DAWGs - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 1999

Asymptotic estimation of the average number of terminal states in DAWGs

Mathieu Raffinot
  • Fonction : Auteur
  • PersonId : 844841

Résumé

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.

Dates et versions

hal-00693885 , version 1 (03-05-2012)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More