Closed Ziv-Lempel factorization of the m-bonacci words

Jahannia, Marieh; Mohammad-noori, Morteza; Narad, Rampersad; Stipulanti, Manon

doi:10.1016/j.tcs.2022.03.019

Download

Article (Scientific journals)

Closed Ziv-Lempel factorization of the m-bonacci words

Jahannia, Marieh; Mohammad-noori, Morteza; Narad, Rampersad et al.

2022 • In Theoretical Computer Science, 918, p. 32-47

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/267189

DOI
10.1016/j.tcs.2022.03.019

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Closed-Z-factorization-submission-2.pdf

Author preprint (213.08 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Ziv–Lempel factorization; Crochemore factorization; Closed words; Fibonacci word; m-bonacci word; episturmian words

Abstract :

[en] A word w is said to be closed if it has a proper factor x which occurs exactly twice in w, as a prefix and as a suffix of w. Based on the concept of Ziv-Lempel factorization, we define the closed z-factorization of finite and infinite words. Then we find the closed z-factorization of the infinite m-bonacci words for all m ≥ 2. We also classify closed prefixes of the infinite m-bonacci words.

Disciplines :

Mathematics

Author, co-author :

Jahannia, Marieh

Mohammad-noori, Morteza

Narad, Rampersad

Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Closed Ziv-Lempel factorization of the m-bonacci words

Publication date :

2022

Journal title :

Theoretical Computer Science

ISSN :

0304-3975

Publisher :

Elsevier, Netherlands

Volume :

918

Pages :

32-47

Peer reviewed :

Peer Reviewed verified by ORBi

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique

Available on ORBi :

since 18 January 2022

Statistics

Number of views

54 (5 by ULiège)

Number of downloads

42 (4 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Arnoux, P., Rauzy, G., Représentation géometrique de suites de complexité 2n+1. Bull. Soc. Math. Fr. 119:2 (1991), 199–215.
Badkobeh, G., Bannai, H., Goto, K., Tomohiro, I., Iliopoulos, C.S., Inenaga, S., Puglisi, S.J., Sugimoto, S., Closed factorization. Discrete Appl. Math. 212 (2016), 23–29.
Badkobeh, G., Fici, G., Lipták, Z., On the number of closed factors in a word. LATA 2015, 9th International Conference on Language and Automata Theory and Applications LNCS, vol. 8977, 2015, 381–390.
Berstel, J., Savelli, A., Crochemore factorization of Sturmian and other infinite words. Proc. MFCS'06 LNCS, vol. 4162, 2006, Springer, 157–166.
Bucci, M., De Luca, A., Fici, G., Enumeration and structure of trapezoidal words. Theor. Comput. Sci. 468 (2013), 12–22.
Crochemore, M., Rytter, W., Text Algorithms. 1994, The Clarendon Press, Oxford University Press.
De Luca, A., Fici, G., Zamboni, L.Q., The sequence of open and closed prefixes of a Sturmian word. Adv. Appl. Math. 90 (2017), 27–45.
Droubay, X., Justin, J., Pirillo, G., Episturmian words and some constructions of de Luca and Rauzy. Theor. Comput. Sci. 255 (2001), 539–553.
Durand, F., A characterization of substitutive sequences using return words. Discrete Math. 179 (1998), 89–101.
Fici, G., Factorizations of the Fibonacci infinite word. J. Integer Seq., 18(9), 2015, 15.9.3.
Fici, G., Open and closed words. Bull. Eur. Assoc. Theor. Comput. Sci. 123 (2017), 140–149.
Badkoubeh, G., Fici, G., Lipták, Z., On the number of closed factors in a word. LATA, 2015, 381–390.
Ghareghani, N., Mohammad-Noori, M., Sharifani, P., On z-factorization and c-factorization of standard episturmian words. Theor. Comput. Sci. 412 (2011), 5232–5238.
Jahannia, M., Mohammad-Noori, M., Rampersad, N., Stipulanti, M., Palindromic Ziv–Lempel and Crochemore factorizations of m-Bonacci infinite words. Theor. Comput. Sci. 790 (2019), 16–40.
Justin, J., Vuillon, L., Episturmian word: shifts, morphisms and numeration systems. Int. J. Found. Comput. Sci. 15:2 (2004), 329–348.
Justin, J., Vuillon, L., Return words in Sturmian and episturmian words. Theor. Inform. Appl. 34 (2000), 343–356.
Justin, J., Pirillo, G., Episturmian words and episturmian morphisms. Theor. Comput. Sci. 276 (2002), 281–313.
Lothaire, M., Algebraic Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol. 90, 2002, Cambridge University Press.
Kolpakov, R., Kucherov, G., On maximal repetitions in words. J. Discret. Algorithms 1:1 (2000), 159–186.
Lempel, A., Ziv, J., On the complexity of finite sequences. IEEE Trans. Inf. Theory IT-22 (1976), 75–81.
Morse, M., Hedlund, G.A., Symbolic dynamics II. Sturmian trajectories. Am. J. Math. 62 (1940), 1–42.
Rytter, W., Compressed and fully compressed pattern-matching in one and two dimensions. Proc. IEEE 88:11 (2000), 1769–1778.
Rytter, W., Application of Lempel–Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302 (2003), 211–222.
Siromoney, R., Mathew, L., Dare, D.R., Subramanian, K.G., Infinite Lyndon words. Inf. Process. Lett. 50 (1994), 101–104.
Tan, B., Wen, Z-Y., Some properties of the Tribonacci sequence. Eur. J. Comb. 28 (2007), 1703–1719.
Wen, Z-X., Wen, Z-Y., Some properties of the singular words of the Fibonacci word. Eur. J. Comb. 15:6 (1994), 587–598.
Ziv, J., Lempel, A., A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23:3 (1977), 337–343.