Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

A characterization of words of linear complexity


Authors: Julien Cassaigne, Anna E. Frid, Svetlana Puzynina and Luca Q. Zamboni
Journal: Proc. Amer. Math. Soc. 147 (2019), 3103-3115
MSC (2010): Primary 68R15; Secondary 37B10
DOI: https://doi.org/10.1090/proc/14440
Published electronically: April 3, 2019
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given an infinite word $ x=x_0x_1x_2\cdots \in \mathbb{A}^\mathbb{N}$ over some finite alphabet $ \mathbb{A},$ the factor complexity $ p_x(n)$ counts the number of distinct factors of $ x$ of each given length $ n,$ i.e., the number of distinct blocks $ x_ix_{i+1}\cdots x_{i+n-1}\in \mathbb{A}^n$ occurring in $ x.$ The factor complexity provides a useful measure of the extent of randomness of $ x$: periodic words have bounded factor complexity while digit expansions of normal numbers have maximal complexity. In this paper we obtain a new characterization of infinite words $ x$ of sublinear complexity, namely we show that $ p_x(n)=O(n)$ if and only if there exists a set $ S\subseteq \mathbb{A}^*$ of bounded complexity (meaning $ \limsup p_S(n)<+\infty )$ such that each factor $ w$ of $ x$ is a concatenation of two elements of $ S,$ i.e., $ w=uv$ with $ u,v \in S.$ In the process we introduce the notions of marker words and marker sets which are both new and may be of independent interest. Marker sets defined by right special factors constitute the key tool needed to split each factor of an infinite word of linear complexity into two pieces.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 68R15, 37B10

Retrieve articles in all journals with MSC (2010): 68R15, 37B10


Additional Information

Julien Cassaigne
Affiliation: CNRS, Aix Marseille University, Centrale Marseille, I2M, Marseille, France
Email: julien.cassaigne@math.cnrs.fr

Anna E. Frid
Affiliation: CNRS, Aix Marseille University, Centrale Marseille, I2M, Marseille, France
Email: anna.e.frid@gmail.com

Svetlana Puzynina
Affiliation: Saint Petersburg State University and Sobolev Institute of Mathematics, Novosibirsk, Russia
Email: s.puzynina@gmail.com

Luca Q. Zamboni
Affiliation: Institut Camille Jordan, Université Lyon 1, France
Email: zamboni@math.univ-lyon1.fr

DOI: https://doi.org/10.1090/proc/14440
Keywords: Factor complexity, Sturmian words, linear complexity
Received by editor(s): March 30, 2018
Received by editor(s) in revised form: September 3, 2018
Published electronically: April 3, 2019
Additional Notes: The third author was partially supported by Russian Foundation of Basic Research (grant 18-31-00118).
Communicated by: Nimish Shah
Article copyright: © Copyright 2019 American Mathematical Society