Cyclic complexity of words
type: Item
instance of: scholarly article
title: Cyclic complexity of words
zbMATH Open document ID: 1369.68271
author: Julien Cassaigne
author: Gabriele Fici
author: M. Sciortino
author: Luca Q. Zamboni
published in: Journal of Combinatorial Theory. Series A
publication date: 2017-02-09T00:00:00Z
review text: A new complexity function on words, called cyclic complexity, is introduced and studied. This function counts the number of conjugacy classes of factors of length \(n\) of an infinite word \(x\). Cyclic complexity distinguishes between Sturmian words of different slopes, yet can not provide a strict characterization of Sturmian words. A very useful extension of the Morse-Hedlund theorem is also presented and used in this paper.
reviewed by: Panayiotis Vlamos
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6682584
zbMATH Keywords: cyclic complexity
zbMATH Keywords: factor complexity
zbMATH Keywords: Sturmian words
zbMATH Keywords: Toeplitz words
zbMATH Keywords: Morse-Hedlund theorem
MaRDI profile type: Publication
full work available at URL: j.jcta.2016.07.002
OpenAlex ID: W2171392767
cites work: The number of factors in a paperfolding sequence
cites work: Sturmian and Episturmian Words
cites work: On an involution of Christoffel words and Sturmian morphisms
cites work: On Christoffel classes
cites work: Enumeration of factors in the Thue-Morse word
cites work: Cyclic Complexity of Words
cites work: Sequences with minimal block growth
cites work: Some combinatorial properties of Sturmian words
cites work: Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
cites work: Characterisations of balanced words via orderings
cites work: Sequence entropy and the maximal pattern complexity of infinite words
cites work: Maximal pattern complexity for discrete systems
cites work: Q4529547
cites work: Burrows-Wheeler transform and Sturmian words
cites work: Words and forbidden factors
cites work: Abelian complexity of minimal subshifts
DOI: 10.1016/J.JCTA.2016.07.002
description: scientific article; zbMATH DE number 6682584