Advances and Applications in Discrete Mathematics

The Advances and Applications in Discrete Mathematics is a prestigious peer-reviewed journal indexed in the Emerging Sources Citation Index (ESCI). It is dedicated to publishing original research articles in the field of discrete mathematics and combinatorics, including topics such as graphs, coding theory, and block design. The journal emphasizes efficient and powerful tools for real-world applications and welcomes expository articles that highlight current developments in the field.

Submit Article

SQUARE COMPLETION OPERATION OF MAXIMAL SUFFIX IN FIBONACCI WORD

Authors

  • K. Ernest Bognini
  • Idrissa Kaboré
  • B. Thomas Ouedraogo

Keywords:

morphism, duplication, strict completion, maximal square, Fibonacci word.

DOI:

https://doi.org/10.17654/0974165823039

Abstract

In this paper, we define the notion of maximal suffix duplication and the notion of strict square completion of maximal suffix in an infinite word. Then, we get that each of these operations can be used iteratively to generate the Fibonacci word F. Finally, we show that duplication generates F faster than strict square completion.

Received: February 3, 2023;
Accepted: March 20, 2023;

References

F. Dejean, Sur un théorème de Thue, J. Combin. Theory Ser. A 13 (1972), 90-99 (in French).

M. Dumitran, J. Gil, F. Manea and V. Mitrana, Bounded prefix suffix duplication, M. Holzer, eds., CIAA 2014, LNCS, 8587, Springer, Heidelberg, 2014, pp. 176-187.

M. Dumitran and F. Manea, Prefix-suffix square completion, LNCS 9304, 2015, pp. 147-159.

L. J. Garcia, F. Manea and V. Mitrana, Prefix-suffix duplication, J. Comput. Syst. Sci. 80(7) (2014), 1254-1265.

M. Hall, Generators and relation in groups - the Burnside problem, Lectures on Modern Mathematics, Vol. 2, Wiley, New York, 1964, pp. 42-92.

J. Knuth, D. E. Morris and J. H. Pratt, Fast pattern matching in strings, SIAM J. Comput. 6(2) (1977), 323-350.

R. Kolpakov and G. Kucherov, Finding maximal repetitions in a word in linear time, Proceedings of FOCS, 1999, pp. 596-604.

M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics, Addison-Wesley, Cambridge University Press, Vol. 17, 2002.

P. Séébold, Propriétés combinatoires des mots infinis engendrés par certains morphismes, Thèse de Doctorat, Tec. LITP., 1985, pp. 85-114.

A. Thue, Selected Mathematical Papers, T. Nagell, A. Selberg, S. Selberg and K. Thalberg, eds., Universitetsforlaget, Oslo, 1977.

Downloads

Published

2023-05-20

Issue

Vol. 39 No. 1 (2023)

Section

Articles

License

Copyright (c) 2023 Pushpa Publishing House, Prayagraj, India

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

_________________________

Licensing Terms:

Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.

Contact Pushpa Publishing House for more info or permissions.

How to Cite

SQUARE COMPLETION OPERATION OF MAXIMAL SUFFIX IN FIBONACCI WORD. (2023). Advances and Applications in Discrete Mathematics, 39(1), 99-115. https://doi.org/10.17654/0974165823039

Similar Articles

1-10 of 20

You may also start an advanced similarity search for this article.

Most read articles by the same author(s)