Document Open Access Logo

Determining Sets of Quasiperiods of Infinite Words

Authors Guilhem Gamard, Gwenaël Richomme

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.40.pdf
  • Filesize: 427 kB
  • 13 pages

Document Identifiers

Author Details

Guilhem Gamard
Gwenaël Richomme

Cite As Get BibTex

Guilhem Gamard and Gwenaël Richomme. Determining Sets of Quasiperiods of Infinite Words. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.40

Abstract

A word is quasiperiodic if it can be obtained by concatenations and overlaps of a smaller word, called a quasiperiod. Based on links between quasiperiods, right special factors and square factors, we introduce a method to determine the set of quasiperiods of a given right infinite word. Then we study the structure of the sets of quasiperiods of right infinite words and, using our method, we provide examples of right infinite words with extremal sets of quasiperiods (no quasiperiod is quasiperiodic, all quasiperiods except one are quasiperiodic, ...). Our method is also used to provide a short proof of a recent characterization of quasiperiods of the Fibonacci word. Finally we extend this result to a new characterization of standard Sturmian words using a property of their sets of quasiperiods.

Subject Classification

Keywords
  • combinatorics on Words
  • quasiperiodicity
  • Sturmian words

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Apostolico and A. Ehrenfeucht. Efficient detection of quasiperiodicities in strings. Theor. Comput. Sci., 119:247-265, 1993. Google Scholar
  2. P. Arnoux and G. Rauzy. Représentation géométrique de suites de complexité 2n+1. Bull. Soc. Math. France, 119:199-215, 1991. Google Scholar
  3. J. Berstel. Fibonacci words - a survey. In The book of L. Springer-Verlag, 1986. Google Scholar
  4. V. Berthé and M. Rigo, editors. Combinatorics, Automata and Number Theory. Number 135 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2010. Google Scholar
  5. G. S. Brodal and C. N. S. Pedersen. Finding maximal quasiperiodicities in strings. In Combinatorial Pattern Matching (CPM'2000), 11th Annual Symposium, CPM 2000, Montreal, Canada, June 21-23, 2000, volume 1848 of Lect. Notes in Comput. Science, pages 397-411, 2000. Google Scholar
  6. M. Christou, M. Crochemore, and I. Costas S. Quasiperiodicities in Fibonacci strings. Technical Report 1201.6162, ArXiv, 2002 (To appear in Ars Combinatoria). Google Scholar
  7. A. de Luca. Sturmian words: structure, combinatorics, and their arithmetics. Theor. Comput. Sci., 183:45-82, 1997. Google Scholar
  8. S. Fischler. Palindromic prefixes and episturmian words. J. Combin. Theory Ser. A, 113(7):1281-1304, 2006. Google Scholar
  9. G. Gamard and G. Richomme. Coverability in two dimensions. In A. Horia Dediu, E. Formenti, C. Martín-Vide, and B. Truthe, editors, Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings, volume 8977 of Lect. Notes in Comput. Science, pages 402-413. Springer, 2015. Google Scholar
  10. A. Glen, F. Levé, and G. Richomme. Quasiperiodic and Lyndon episturmian words. Theor. Comput. Sci., 409(3):578-600, 2008. Google Scholar
  11. R. Groult and G. Richomme. Optimality of some algorithms to detect quasiperiodicities. Theoretical Computer Science, 411:3110 - 3122, 2010. Google Scholar
  12. C. S. Iliopoulos and L. Mouchard. An o(nlog n) algorithm for computing all maximal quasiperiodicities in strings. In C. S. Calude and M. J. Dinneen, editors, Combinatorics, Computation and Logic. Proceedings of DMTCS'99 and CATS'99, Lect. Notes in Comput. Science, pages 262-272, Auckland, New-Zealand, 1999. Springer. Google Scholar
  13. J. Justin and G. Pirillo. Episturmian words and episturmian morphisms. Theor. Comput. Sci., 276(1-2):281-313, 2002. Google Scholar
  14. F. Levé and G. Richomme. Quasiperiodic infinite words: some answers. Bull. Europ. Assoc. Theoret. Comput. Sci., 84:128-238, 2004. Google Scholar
  15. F. Levé and G. Richomme. Quasiperiodic Sturmian words and morphisms. Theor. Comput. Sci., 372(1):15-25, 2007. Google Scholar
  16. M. Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, 1983. Reprinted in the Cambridge Mathematical Library, Cambridge University Press, UK, 1997. Google Scholar
  17. M. Lothaire. Algebraic Combinatorics on Words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002. Google Scholar
  18. S. Marcus. Quasiperiodic infinite words. Bull. Eur. Assoc. Theor. Comput. Sci., 82:170-174, 2004. Google Scholar
  19. T. Monteil and S. Marcus. Quasiperiodic infinite words: multi-scale case and dynamical properties. arXiv:math/0603354v1, 2006. Google Scholar
  20. L. Mouchard. Normal forms of quasiperiodic strings. Theor. Comput. Sci., 249:313-324, 2000. Google Scholar
  21. H. Mousavi, L. Schaeffer, and J. Shallit. Decision algorithms for Fibonacci-automatic words, I: basic results. RAIRO Theor. Inform. Appl., To appear. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact