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 ⌊
|
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |