Searching for Zimin patterns / Rytter Wojciech,Shur Arseny M. // THEORETICAL COMPUTER SCIENCE. - 2015. - V. 571, l. . - P. 50-57.

ISSN/EISSN:

0304-3975 / 1879-2294

Type:

Article

Abstract:

In the area of pattern avoidability the central role is played by special words called Zimin patterns. The symbols of these patterns are treated as variables and the rank of the pattern is its number of variables. Zimin type of a word x is introduced here as the maximum rank of a Zimin pattern matching x. We show how to compute Zimin type of a word on-line in linear time. Consequently we get a quadratic time, linear-space algorithm for searching Zimin patterns in words. Then we demonstrate how the Zimin type of the length n prefix of the infinite Fibonacci word is related to the representation of n in the Fibonacci numeration system. Using this relation, we prove that Zimin types of such prefixes and Zimin patterns inside them can be found in logarithmic time. Finally, we give some upper bounds on the function f (n, k) such that every k-ary word of length at least f (n, k) has a factor that matches the rank n Zimin pattern. (C) 2015 Elsevier B.V. All rights reserved.

Author keywords:

Zimin word; Unavoidable pattern; On-line algorithm; Fibonacci word STRINGS

DOI:

10.1016/j.tcs.2015.01.004

Web of Science ID:

ISI:000349875700005

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

—

Другие поля

Поле	Значение
Month	MAR 16
Publisher	ELSEVIER SCIENCE BV
Address	PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
Language	English
EISSN	1879-2294
Keywords-Plus	STRINGS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	rytter@mimuw.edu.pl arseny.shur@urfu.ru
Funding-Acknowledgement	Polish Research Center {[}NCN2014/13/B/ST6/00770]; Ministry of Education and Science of the Russian Federation {[}02.A03.21.0006]; Russian Foundation of Basic Research {[}13-01-00852]; Ural Federal University {[}02.A03.21.0006]
Funding-Text	Supported by the grant NCN2014/13/B/ST6/00770 of the Polish Research Center.; Supported under the Agreement 02.A03.21.0006 of 27.08.2013 between the Ministry of Education and Science of the Russian Federation and Ural Federal University, and by the grant 13-01-00852 of the Russian Foundation of Basic Research.
Number-of-Cited-References	10
Usage-Count-Since-2013	2
Journal-ISO	Theor. Comput. Sci.
Doc-Delivery-Number	CB8JL