A new characterization of maximal repetitions by Lyndon trees

DOI10.1137/1.9781611973730.38MaRDI QIDQ5363085zbMATH OpenOpenAlexFDO

Authors Hideo Bannai, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta, Tomohiro I

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.38

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Recommendations

• The ``runs theorem
• Maximal repetitions in strings
• The runs theorem and beyond
• Analysis of Maximal Repetitions in Strings
• Fast and Practical Algorithms for Computing All the Runs in a String

Cited in

(27)

• Lyndon array construction during Burrows-Wheeler inversion
• Computing primitively-rooted squares and runs in partial words
• Reconstructing a string from its Lyndon arrays
• Inverse Lyndon words and inverse Lyndon factorizations of words
• On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties
• Can formal languages help pangenomics to represent and analyze multiple genomes?
• Dynamic and internal longest common substring
• Optimal bounds for computing \({\alpha}\)-gapped repeats
• Cartesian and Lyndon trees
• Two-dimensional maximal repetitions
• Longest -gapped repeat and palindrome
• Prefix-suffix square completion
• Two-dimensional maximal repetitions
• On the density of Lyndon roots in factors
• Fast computation of abelian runs
• Some variations on Lyndon words (invited talk)
• Small-space LCE data structure with constant-time queries
• 2D Lyndon words and applications
• Almost linear time computation of maximal repetitions in run length encoded strings
• The ``runs theorem
• Numeric Lyndon-based feature embedding of sequencing reads for machine learning approaches
• Exact and inexact search for 2d side-sharing tandems
• Unveiling the connection between the Lyndon factorization and the canonical inverse Lyndon factorization via a border property
• Longest common extensions with wildcards: trade-off and applications
• Counting maximal-exponent factors in words
• Efficiently computing runs on a trie
• Lyndon words formalized in Isabelle/HOL

This page was built for publication: A new characterization of maximal repetitions by Lyndon trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363085)