Name
Abstract | ||
|---|---|---|
The Lyndon factorization of a string w is a unique factorization ℓ1p1,…,ℓmpm of w such that ℓ1,…,ℓm is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the reverse-engineering problem on Lyndon factorization: Given a sequence S=((s1,p1),…,(sm,pm)) of ordered pairs of positive integers, find a string w whose Lyndon factorization corresponds to the input sequence S, i.e., the Lyndon factorization of w is in a form of ℓ1p1,…,ℓmpm with |ℓi|=si for all 1≤i≤m. Firstly, we show that there exists a simple O(n)-time algorithm if the size of the alphabet is unbounded, where n is the length of the output string. Secondly, we present an O(n)-time algorithm to compute a string over an alphabet of the smallest size. Thirdly, we show how to compute only the size of the smallest alphabet in O(m) time. Fourthly, we give an O(m)-time algorithm to compute an O(m)-size representation of a string over an alphabet of the smallest size. Finally, we propose an efficient algorithm to enumerate all strings whose Lyndon factorizations correspond to S. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2017.05.038 | Theoretical Computer Science |
Keywords | Field | DocType |
Lyndon factorization,Reverse engineering problem | Integer,Discrete mathematics,Monotonic function,Combinatorics,Computer science,Ordered pair,Factorization,Lexicographical order,Unique factorization domain,Lyndon words,Alphabet | Conference |
Volume | ISSN | Citations |
689 | 0304-3975 | 1 |
PageRank | References | Authors |
0.36 | 21 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuto Nakashima | 1 | 57 | 19.52 |
| Takashi Okabe | 2 | 1 | 0.36 |
| Tomohiro I | 3 | 148 | 22.06 |
| Shunsuke Inenaga | 4 | 595 | 79.02 |
| Hideo Bannai | 5 | 620 | 79.87 |
| Masayuki Takeda | 6 | 902 | 79.24 |