Ternary Square-Free Partial Words with Many Wildcards / Gasnikov Daniil,Shur Arseny M. // . - 2016. - V. 9840, l. . - P. 177-189.

ISSN/EISSN:

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

Type:

Proceedings Paper

Abstract:

We contribute to the study of square-free words. The classical notion of a square-free word has a natural generalization to partial words, studied in several papers since 2008. We prove that the maximal density of wildcards in the ternary infinite square-free partial word is surprisingly big: 3/16. In addition, we introduce a related characteristic of infinite square-free words, called flexibility, and find its values for some interesting words and classes of words.

Author keywords:

Partial word; Square-free word; Letter density THEOREM; FINE; WILF

DOI:

10.1007/978-3-662-53132-7\_15

Web of Science ID:

ISI:000389721100015

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

—

Другие поля

Поле	Значение
Editor	Brlek, S and Reutenauer, C
Booktitle	DEVELOPMENTS IN LANGUAGE THEORY, DLT 2016
Series	Lecture Notes in Computer Science
Note	20th International Conference on Developments in Language Theory (DLT), Montreal, CANADA, JUL 25-28, 2016
Organization	Lab Combinatoire Informatique Math
Publisher	SPRINGER INT PUBLISHING AG
Address	GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND
Language	English
ISBN	978-3-662-53132-7; 978-3-662-53131-0
Keywords-Plus	THEOREM; FINE; WILF
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Software Engineering; Computer Science, Theory \& Methods
Author-Email	legionlon@gmail.com arseny.shur@urfu.ru
Number-of-Cited-References	15
Doc-Delivery-Number	BG5SG