Prague Stringology Conference 2017

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

On Reverse Engineering the Lyndon Tree

Abstract:
We consider the problem of reverse engineering the Lyndon tree, i.e., given a full binary ordered tree T with n leaves as input, compute a string w of length n for which it's Lyndon tree is isomorphic to the input tree. Although the problem is easy and solvable in linear time when assuming a binary alphabet or when there is no limit on the alphabet size, how to efficiently find the smallest alphabet size for a solution string is not known. We show several new observations concerning this problem. Namely, we show that:
1) For any full binary ordered tree T, there exists a solution string w over an alphabet of size at most h+1, where h is the height of T.
2) For any positive n, there exists a full binary ordered tree T with n leaves, s.t. the smallest alphabet size of the solution string for T is
n
2
.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference