On the Tree of Ternary Square-Free Words / Petrova Elena A.,Shur Arseny M. // . - 2015. - V. 9304, l. . - P. 223-236.

ISSN/EISSN:

0302-9743 / нет данных

Type:

Proceedings Paper

Abstract:

We contribute to the study of the set of ternary square-free words. Under the prefix order, this set forms a tree, and we prove two results on its structure. First, we show that non-branching paths in this tree are short: such a path from a node of nth level has length O(log n). Second, we prove that any infinite path in the tree has a lot of branching points: the lower density of the set of such points is at least 2/9.

Author keywords:

POWER FREE WORDS; APERIODIC WORDS; 3 SYMBOLS

DOI:

10.1007/978-3-319-23660-5\_19

Web of Science ID:

ISI:000363802400019

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

—

Другие поля

Поле	Значение
Editor	Manea, F and Nowotka, D
Booktitle	COMBINATORICS ON WORDS, WORDS 2015
Series	Lecture Notes in Computer Science
Note	10th International Conference on Combinatorics on Words (WORDS), Kiel Univ, Kiel, GERMANY, SEP 14-17, 2015
Organization	EATCS
Publisher	SPRINGER-VERLAG BERLIN
Address	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
Language	English
ISBN	978-3-319-23660-5; 978-3-319-23659-9
Keywords-Plus	POWER FREE WORDS; APERIODIC WORDS; 3 SYMBOLS
Research-Areas	Computer Science; Science \& Technology - Other Topics; Robotics
Web-of-Science-Categories	Computer Science, Artificial Intelligence; Computer Science, Theory \& Methods; Logic; Robotics
Author-Email	elena.petrova@urfu.ru arseny.shur@urfu.ru
Number-of-Cited-References	14
Doc-Delivery-Number	BD8CO