Please use this identifier to cite or link to this item:
|Title:||Subword complexity and power avoidance|
|Citation:||Shallit J. Subword complexity and power avoidance / J. Shallit, A. Shur. — DOI 10.1016/j.tcs.2018.09.010 // Theoretical Computer Science. — 2019. — Vol. 792. — P. 96-116.|
|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 ( [Formula presented] )-power-free binary words, but not over all ( [Formula presented] )+-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 ( [Formula presented] )-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. © 2018 Elsevier B.V.|
|Keywords:||COMBINATORICS ON WORDS|
COMBINATORICS ON WORDS
|Appears in Collections:||Научные публикации, проиндексированные в SCOPUS и WoS CC|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.