Uncommon Suffix Tries

Common assumptions on the source producing the words inserted in a suffix trie with $n$ leaves lead to a $\log n$ height and saturation level. We provide an example of a suffix trie whose height increases faster than a power of $n$ and another one whose saturation level is negligible with respect to $\log n$. Both are built from VLMC (Variable Length Markov Chain) probabilistic sources; they are easily extended to families of sources having the same properties. The first example corresponds to a ''logarithmic infinite comb'' and enjoys a non uniform polynomial mixing. The second one corresponds to a ''factorial infinite comb'' for which mixing is uniform and exponential.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00652952
Author Cénac, Peggy, Chauvin, Brigitte, Paccaut, Frédéric, Pouyanne, Nicolas
Maintainer CCSD
Last Updated November 10, 2026, 11:33 (UTC)
Created November 10, 2026, 11:33 (UTC)
Identifier hal-00652952
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Institut de Mathématiques de Bourgogne [Dijon] (IMB) ; Université de Bourgogne (UB)-Centre National de la Recherche Scientifique (CNRS)
creator Cénac, Peggy
date 2011-12-14T00:00:00
harvest_object_id 62455d2a-85d6-4e1d-a8d9-161459d02c1f
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-03-31T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1112.4131
set_spec type:UNDEFINED