Standard

Subword complexity and power avoidance. / Shallit, Jeffrey; Shur, Arseny.
в: Theoretical Computer Science, Том 792, 05.11.2019, стр. 96-116.

Результаты исследований: Вклад в журнал › Статья › Рецензирование

Harvard

Shallit, J & Shur, A 2019, 'Subword complexity and power avoidance', Theoretical Computer Science, Том. 792, стр. 96-116. https://doi.org/10.1016/j.tcs.2018.09.010

APA

Shallit, J., & Shur, A. (2019). Subword complexity and power avoidance. Theoretical Computer Science, 792, 96-116. https://doi.org/10.1016/j.tcs.2018.09.010

Vancouver

Shallit J, Shur A. Subword complexity and power avoidance. Theoretical Computer Science. 2019 нояб. 5;792:96-116. doi: 10.1016/j.tcs.2018.09.010

Author

Shallit, Jeffrey ; Shur, Arseny. / Subword complexity and power avoidance. в: Theoretical Computer Science. 2019 ; Том 792. стр. 96-116.

BibTeX

@article{4f12dcd332cf46708da01dc9c4fcc2d1,
title = "Subword complexity and power avoidance",
abstract = "We begin a systematic study of the relations between subword complexity of infinite words and their power avoidance. Among other things, we show that the Thue-Morse word has the minimum possible subword complexity over all overlap free binary words and all (7/3)-power-free binary words, but not over all (7/3)(+)-power-free binary words;the twisted Thue-Morse word has the maximum possible subword complexity over all overlap-free binary words, but no word has the maximum subword complexity over all (7/3)-power-free binary words;if some word attains the minimum possible subword complexity over all square-free ternary words, then one such word is the ternary Thue word;the recently constructed 1-2-bonacci word has the minimum possible subword complexity over all symmetric square-free ternary words. ",
keywords = "Combinatorics on words, Critical exponent, Power-free word, Subword complexity, Thue–Morse word, OVERLAP-FREE WORDS, COMBINATORIAL PROPERTIES, BOUNDS, ENUMERATION, GROWTH-RATES, Thue-Morse word",
author = "Jeffrey Shallit and Arseny Shur",
year = "2019",
month = nov,
day = "5",
doi = "10.1016/j.tcs.2018.09.010",
language = "English",
volume = "792",
pages = "96--116",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier BV",

}

RIS

TY - JOUR

T1 - Subword complexity and power avoidance

AU - Shallit, Jeffrey

AU - Shur, Arseny

PY - 2019/11/5

Y1 - 2019/11/5

N2 - We begin a systematic study of the relations between subword complexity of infinite words and their power avoidance. Among other things, we show that the Thue-Morse word has the minimum possible subword complexity over all overlap free binary words and all (7/3)-power-free binary words, but not over all (7/3)(+)-power-free binary words;the twisted Thue-Morse word has the maximum possible subword complexity over all overlap-free binary words, but no word has the maximum subword complexity over all (7/3)-power-free binary words;if some word attains the minimum possible subword complexity over all square-free ternary words, then one such word is the ternary Thue word;the recently constructed 1-2-bonacci word has the minimum possible subword complexity over all symmetric square-free ternary words.

AB - We begin a systematic study of the relations between subword complexity of infinite words and their power avoidance. Among other things, we show that the Thue-Morse word has the minimum possible subword complexity over all overlap free binary words and all (7/3)-power-free binary words, but not over all (7/3)(+)-power-free binary words;the twisted Thue-Morse word has the maximum possible subword complexity over all overlap-free binary words, but no word has the maximum subword complexity over all (7/3)-power-free binary words;if some word attains the minimum possible subword complexity over all square-free ternary words, then one such word is the ternary Thue word;the recently constructed 1-2-bonacci word has the minimum possible subword complexity over all symmetric square-free ternary words.

KW - Combinatorics on words

KW - Critical exponent

KW - Power-free word

KW - Subword complexity

KW - Thue–Morse word

KW - OVERLAP-FREE WORDS

KW - COMBINATORIAL PROPERTIES

KW - BOUNDS

KW - ENUMERATION

KW - GROWTH-RATES

KW - Thue-Morse word

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

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000490648500008

U2 - 10.1016/j.tcs.2018.09.010

DO - 10.1016/j.tcs.2018.09.010

M3 - Article

AN - SCOPUS:85053678820

VL - 792

SP - 96

EP - 116

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

ID: 10768632