2016/05/11 by Jeffrey Gaither, Gaither, Jeffrey, Ward, Mark Daniel
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1605.03390
openalex publication_date 2016/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
The precise analysis of the variance of the profile of a suffix tree has been a longstanding open problem. We analyze three regimes of the asymptotic growth of the variance of the profile of a suffix tree built from a randomly generated binary string, in the nonuniform case. We utilize combinatorics on words, singularity analysis, and the Mellin transform.