Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101935
Title: Subword complexity and power avoidance
Authors: Shallit, J.
Shur, A.
Issue Date: 2019
Publisher: Elsevier B.V.
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
CRITICAL EXPONENT
POWER-FREE WORD
SUBWORD COMPLEXITY
THUE–MORSE WORD
COMPUTATIONAL METHODS
BINARY WORDS
COMBINATORICS ON WORDS
CRITICAL EXPONENT
INFINITE WORD
POWER-FREE WORD
SUBWORD COMPLEXITY
SYSTEMATIC STUDY
COMPUTER SCIENCE
URI: http://hdl.handle.net/10995/101935
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85053678820
PURE ID: 10768632
4f12dcd3-32cf-4670-8da0-1dc9c4fcc2d1
ISSN: 3043975
DOI: 10.1016/j.tcs.2018.09.010
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85053678820.pdf459,79 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.