Optimal Bounds for the Similarity Density of the Thue-Morse Word with Overlap-Free and 7/3-Power-Free Infinite Binary Words / Du Chen Fei,Shallit Jeffrey,Shur Arseny M. // INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - 2015. - V. 26, l. 8. - P. 1147-1165.

ISSN/EISSN:

0129-0541 / 1793-6373

Type:

Article; Proceedings Paper

Abstract:

We consider a measure of similarity for infinite words that generalizes the usual number theoretic notion of asymptotic or natural density for subsets of natural numbers. We show that every 4-power-free infinite binary word, other than the Thue-Morse word t and its complement t, has this measure of similarity with t between 1/3 and 2/3, and that this bound is optimal in a strong sense just for the class of overlap-free words. This is a generalization of a classical 1927 result of Kurt Mahler.

Author keywords:

Thue-Morse sequence; similarity density; 7/3-power-free sequence; overlap; overlap-free sequence SEQUENCE; SYMBOLS; SQUARES

DOI:

10.1142/S01290541140016X

Web of Science ID:

ISI:000371496500007

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	DEC
Note	14th International Conference on Automata and Formal Languages (AFL), Szeged, HUNGARY, MAY 27-29, 2014
Publisher	WORLD SCIENTIFIC PUBL CO PTE LTD
Address	5 TOH TUCK LINK, SINGAPORE 596224, SINGAPORE
Language	English
EISSN	1793-6373
Keywords-Plus	SEQUENCE; SYMBOLS; SQUARES
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	cfdu@uwaterloo.ca shallit@uwaterloo.ca arseny.shur@urfu.ru
Number-of-Cited-References	16
Journal-ISO	Int. J. Found. Comput. Sci.
Doc-Delivery-Number	DF6VV