On the size of the smallest alphabet for Lyndon trees

DOI10.1016/j.tcs.2018.06.044zbMath1430.68255OpenAlexW2883931698WikidataQ129492867 ScholiaQ129492867MaRDI QIDQ2326391

Masayuki Takeda, Yuto Nakashima, Hideo Bannai, Takuya Takagi, Shunsuke Inenaga

Publication date: 7 October 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.06.044

zbMATH Keywords

Lyndon wordsLyndon treesreverse-engineering problems

Mathematics Subject Classification ID

Combinatorics on words (68R15) Data structures (68P05)

Related Items (1)

Linear construction of a left Lyndon tree

Cites Work

• Unnamed Item
• Unnamed Item
• Reverse engineering of compact suffix trees and links: a novel algorithm
• Inferring strings from suffix trees and links on a binary alphabet
• Computing runs on a general alphabet
• On the action of the symmetric group on the free Lie algebra and the partition lattice
• Lyndon words, permutations and trees.
• Reconstructing a string from its Lyndon arrays
• The standard factorization of Lyndon words: an average point of view
• A suffix tree or not a suffix tree?
• Suffix Arrays: A New Method for On-Line String Searches
• Factorizing words over an ordered alphabet
• String Inference from Longest-Common-Prefix Array
• The “Runs” Theorem
• Faster Longest Common Extension Queries in Strings over General Alphabets
• Mathematical Foundations of Computer Science 2003
• On Burnside's Problem
• Free differential calculus. IV: The quotient groups of the lower central series

This page was built for publication: On the size of the smallest alphabet for Lyndon trees