Generating square-free words efficiently / Shur Arseny M. // THEORETICAL COMPUTER SCIENCE. - 2015. - V. 601, l. . - P. 67-72.

ISSN/EISSN:

0304-3975 / 1879-2294

Type:

Article; Proceedings Paper

Abstract:

We study a simple algorithm generating square-free words from a random source. The source produces uniformly distributed random letters from a k-ary alphabet, and the algorithm outputs a (k+1)-ary square-free word. We are interested in the ``conversion ratio{''} between the lengths of the input random word and the output square-free word. For any k >= 3 we prove the expected value of this ratio to be a constant and calculate it up to an O(1/k(5)) term. For the extremal case of ternary square-free words, we suggest this ratio to have a constant expectation as well and conjecture its actual value from computer experiments. (C) 2015 Elsevier B.V. All rights reserved.

Author keywords:

Square-free word; Random word; String algorithms POWER-FREE LANGUAGES; GROWTH

DOI:

10.1016/j.tcs.2015.07.027

Web of Science ID:

ISI:000362131900009

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

—

Другие поля

Поле	Значение
Month	OCT 11
Note	9th International Conference on WORDS, Turku, FINLAND, SEP 16-20, 2013
Publisher	ELSEVIER SCIENCE BV
Address	PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
Language	English
EISSN	1879-2294
Keywords-Plus	POWER-FREE LANGUAGES; GROWTH
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	Arseny.Shur@urfu.ru
Funding-Acknowledgement	Ministry of Education and Science of the Russian Federation {[}02.A03.21.0006]; Ural Federal University; Russian Foundation for Basic Research {[}13-01-00852]
Funding-Text	Supported by Ministry of Education and Science of the Russian Federation under the Agreement 02.A03.21.0006 of 27.08.2013 with Ural Federal University, and by the grant 13-01-00852 of Russian Foundation for Basic Research.
Number-of-Cited-References	8
Journal-ISO	Theor. Comput. Sci.
Doc-Delivery-Number	CS5QB