Cyclic Complexity of Words

DOI10.1007/978-3-662-44522-8_14zbMATH Open1425.68326arXiv1402.5843OpenAlexW2951112613MaRDI QIDQ2922011FDOQ2922011

Julien Cassaigne, M. Sciortino, Luca Q. Zamboni, Gabriele Fici

Publication date: 14 October 2014

Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Abstract: We introduce and study a complexity function on words $c_x(n),$ called emph{cyclic complexity}, which counts the number of conjugacy classes of factors of length $n$ of an infinite word $x.$ We extend the well-known Morse-Hedlund theorem to the setting of cyclic complexity by showing that a word is ultimately periodic if and only if it has bounded cyclic complexity. Unlike most complexity functions, cyclic complexity distinguishes between Sturmian words of different slopes. We prove that if $x$ is a Sturmian word and $y$ is a word having the same cyclic complexity of $x,$ then up to renaming letters, $x$ and $y$ have the same set of factors. In particular, $y$ is also Sturmian of slope equal to that of $x.$ Since $c_x(n)=1$ for some $ngeq1$ implies $x$ is periodic, it is natural to consider the quantity $limin{f}_{nightarrowinfty}{c}_x(n).$ We show that if $x$ is a Sturmian word, then $limin{f}_{nightarrowinfty}{c}_x(n)=2.$ We prove however that this is not a characterization of Sturmian words by exhibiting a restricted class of Toeplitz words, including the period-doubling word, which also verify this same condition on the limit infimum. In contrast we show that, for the Thue-Morse word $t$, $limin{f}_{nightarrowinfty}{c}_t(n)=+infty.$

Full work available at URL: https://arxiv.org/abs/1402.5843

zbMATH Keywords

Sturmian wordsfactor complexitycyclic complexityminimal forbidden factor

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• Combinatorics on Words
• Substitutions in dynamics, arithmetics and combinatorics
• Characterisations of balanced words via orderings
• Abelian complexity of minimal subshifts
• Sturmian and Episturmian Words
• Words and forbidden factors
• On the Asymptotic Abelian Complexity of Morphic Words
• Maximal pattern complexity for discrete systems
• On a generalization of abelian equivalence and complexity of infinite words
• Burrows-Wheeler transform and Sturmian words
• On Christoffel classes
• Abelian complexity and abelian co-decomposition
• The abelian complexity of the paperfolding word
• Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words
• A new complexity function for words based on periodicity

Cited In (6)

• Words with the Maximum Number of Abelian Squares
• On the additive complexity of a Thue-Morse-like sequence
• Cyclic Permutations of Letters of Words in Languages over an Alphabet
• Title not available (Why is that?)
• Cyclic complexity of words
• Lie complexity of words

Recommendations

• Words with unbounded periodicity complexity 👍 👎
• Recurrent words with constant abelian complexity 👍 👎
• Universal cycles of classes of restricted words 👍 👎
• Cyclic complexity of words 👍 👎
• Some bounds on the complexity of words 👍 👎
• Aspects of Molecular Computing 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Cyclic Complexity of Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922011)