Standard

A characterization of words of linear complexity. / Cassaigne, Julien; Frid, Anna E.; Puzynina, Svetlana; Zamboni, Luca Q.

в: Proceedings of the American Mathematical Society, Том 147, № 7, 07.2019, стр. 3103-3115.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Cassaigne, J, Frid, AE, Puzynina, S & Zamboni, LQ 2019, 'A characterization of words of linear complexity', Proceedings of the American Mathematical Society, Том. 147, № 7, стр. 3103-3115. https://doi.org/10.1090/proc/14440, https://doi.org/10.1090/proc/14440

APA

Cassaigne, J., Frid, A. E., Puzynina, S., & Zamboni, L. Q. (2019). A characterization of words of linear complexity. Proceedings of the American Mathematical Society, 147(7), 3103-3115. https://doi.org/10.1090/proc/14440, https://doi.org/10.1090/proc/14440

Vancouver

Cassaigne J, Frid AE, Puzynina S, Zamboni LQ. A characterization of words of linear complexity. Proceedings of the American Mathematical Society. 2019 Июль;147(7):3103-3115. https://doi.org/10.1090/proc/14440, https://doi.org/10.1090/proc/14440

Author

Cassaigne, Julien ; Frid, Anna E. ; Puzynina, Svetlana ; Zamboni, Luca Q. / A characterization of words of linear complexity. в: Proceedings of the American Mathematical Society. 2019 ; Том 147, № 7. стр. 3103-3115.

BibTeX

@article{a067545c86ca4e7abd77d4e94a45ee5f,
title = "A characterization of words of linear complexity",
abstract = "Given an infinite word x = x0x1x2 ···∈AN over some finite alpha-bet A, the factor complexity px(n) counts the number of distinct factors of x of each given length n, i.e., the number of distinct blocks xixi+1 ···xi+n−1 ∈ An 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 px(n) =O(n) if and only if there exists a set S ⊆ A∗ of bounded complexity (meaning lim sup pS (n) < +∞) such that each factor w of x is aconcatenation of two elements of S, i.e., w = uv with u, v ∈ 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.",
keywords = "Factor complexity, Linear complexity, Sturmian words, linear complexity",
author = "Julien Cassaigne and Frid, {Anna E.} and Svetlana Puzynina and Zamboni, {Luca Q.}",
year = "2019",
month = jul,
doi = "10.1090/proc/14440",
language = "English",
volume = "147",
pages = "3103--3115",
journal = "Proceedings of the American Mathematical Society",
issn = "0002-9939",
publisher = "American Mathematical Society",
number = "7",

}

RIS

TY - JOUR

T1 - A characterization of words of linear complexity

AU - Cassaigne, Julien

AU - Frid, Anna E.

AU - Puzynina, Svetlana

AU - Zamboni, Luca Q.

PY - 2019/7

Y1 - 2019/7

N2 - Given an infinite word x = x0x1x2 ···∈AN over some finite alpha-bet A, the factor complexity px(n) counts the number of distinct factors of x of each given length n, i.e., the number of distinct blocks xixi+1 ···xi+n−1 ∈ An 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 px(n) =O(n) if and only if there exists a set S ⊆ A∗ of bounded complexity (meaning lim sup pS (n) < +∞) such that each factor w of x is aconcatenation of two elements of S, i.e., w = uv with u, v ∈ 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.

AB - Given an infinite word x = x0x1x2 ···∈AN over some finite alpha-bet A, the factor complexity px(n) counts the number of distinct factors of x of each given length n, i.e., the number of distinct blocks xixi+1 ···xi+n−1 ∈ An 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 px(n) =O(n) if and only if there exists a set S ⊆ A∗ of bounded complexity (meaning lim sup pS (n) < +∞) such that each factor w of x is aconcatenation of two elements of S, i.e., w = uv with u, v ∈ 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.

KW - Factor complexity

KW - Linear complexity

KW - Sturmian words

KW - linear complexity

UR - http://www.scopus.com/inward/record.url?scp=85070609367&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/characterization-words-linear-complexity

U2 - 10.1090/proc/14440

DO - 10.1090/proc/14440

M3 - Article

AN - SCOPUS:85070609367

VL - 147

SP - 3103

EP - 3115

JO - Proceedings of the American Mathematical Society

JF - Proceedings of the American Mathematical Society

SN - 0002-9939

IS - 7

ER -

ID: 41185889