TY - GEN
T1 - Largest Repetition Factorization of Fibonacci Words
AU - Kishi, Kaisei
AU - Nakashima, Yuto
AU - Inenaga, Shunsuke
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.
PY - 2023
Y1 - 2023
N2 - A factorization of a string w is said to be a repetition factorization of w if every factor in the factorization is a repetition (i.e., the factor has a period shorter than or equal to the half of its length). Inoue et al. [TOCS 2022] showed how to compute the largest/smallest repetition factorization of a given string w of length n in $$O(n \log n)$$ time and O(n) space, by reducing the problems to the longest/shortest path problems on the repetition graph built on w. Inoue et al. also considered repetition factorizations on Fibonacci words, and posed a conjecture on the size $$S:{F_k}$$ of the largest repetition factorization of the k-th Fibonacci word $$F:k$$. In this work, we provide a complete proof for this problem, by showing that $$S:{F_k}$$ is given by the recurrence $$S:{F_k} = S_{F_{k-1}} + S_{F_{k-2}} + 1$$ for every $$k \ge 15$$.
AB - A factorization of a string w is said to be a repetition factorization of w if every factor in the factorization is a repetition (i.e., the factor has a period shorter than or equal to the half of its length). Inoue et al. [TOCS 2022] showed how to compute the largest/smallest repetition factorization of a given string w of length n in $$O(n \log n)$$ time and O(n) space, by reducing the problems to the longest/shortest path problems on the repetition graph built on w. Inoue et al. also considered repetition factorizations on Fibonacci words, and posed a conjecture on the size $$S:{F_k}$$ of the largest repetition factorization of the k-th Fibonacci word $$F:k$$. In this work, we provide a complete proof for this problem, by showing that $$S:{F_k}$$ is given by the recurrence $$S:{F_k} = S_{F_{k-1}} + S_{F_{k-2}} + 1$$ for every $$k \ge 15$$.
UR - http://www.scopus.com/inward/record.url?scp=85174447371&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85174447371&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-43980-3_23
DO - 10.1007/978-3-031-43980-3_23
M3 - Conference contribution
AN - SCOPUS:85174447371
SN - 9783031439797
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 284
EP - 296
BT - String Processing and Information Retrieval - 30th International Symposium, SPIRE 2023, Proceedings
A2 - Nardini, Franco Maria
A2 - Pisanti, Nadia
A2 - Venturini, Rossano
PB - Springer Science and Business Media Deutschland GmbH
T2 - 30th International Symposium on String Processing and Information Retrieval, SPIRE 2023
Y2 - 26 September 2023 through 28 September 2023
ER -