Cyclic Complexity of Words

DOI10.1007/978-3-662-44522-8_14MaRDI QIDQ2922011zbMATHOpenAlexFDO

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

Publication date 14 October 2014

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

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)

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.$

Recommendations

• Cyclic complexity of words
• scientific article; zbMATH DE number 7069796
• Aspects of Molecular Computing
• Words with unbounded periodicity complexity
• scientific article; zbMATH DE number 3892611
• scientific article; zbMATH DE number 1992418
• Some bounds on the complexity of words
• scientific article; zbMATH DE number 1992419
• Recurrent words with constant abelian complexity
• Universal cycles of classes of restricted words

Cites work

• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A new complexity function for words based on periodicity
• Abelian complexity and abelian co-decomposition
• Abelian complexity of minimal subshifts
• Another generalization of abelian equivalence: binomial complexity of infinite words
• Burrows-Wheeler transform and Sturmian words
• Characterisations of balanced words via orderings
• Combinatorics on Words
• Maximal pattern complexity for discrete systems
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• On Christoffel classes
• On a generalization of abelian equivalence and complexity of infinite words
• On the asymptotic abelian complexity of morphic words
• Sturmian and Episturmian Words
• Substitutions in dynamics, arithmetics and combinatorics
• The abelian complexity of the paperfolding word
• Ultimately constant abelian complexity of infinite words
• Words and forbidden factors

Cited in

(14)

• On the character of words of sublinear complexity
• Unique Subwords in Nonperiodic Words
• On the Lie complexity of Sturmian words
• A new complexity function for words based on periodicity
• Cyclic Permutations of Letters of Words in Languages over an Alphabet
• On a group theoretic generalization of the Morse-Hedlund theorem
• On the parity slope of words of low complexity
• scientific article; zbMATH DE number 7069796 (Why is no real title available?)
• On subword complexity functions
• Cyclic complexity of words
• On the additive complexity of a Thue-Morse-like sequence
• Relationally Periodic Sequences and Subword Complexity
• Lie complexity of words
• Words with the maximum number of abelian squares

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)