2017/12/23 by Maxime Crochemore, Crochemore, Maxime, Luís M. S.Russo +1
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1712.08749
openalex publication_date 2017/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The article describes the structural and algorithmic relations between Cartesian trees and Lyndon Trees. This leads to a uniform presentation of the Lyndon table of a word corresponding to the Next Nearest Smaller table of a sequence of numbers. It shows how to efficiently compute runs, that is, maximal periodicities occurring in a word.