Palindromic rich words and run-length encodings / Guo Chuan,Shallit Jeffrey,Shur Arseny M. // INFORMATION PROCESSING LETTERS. - 2016. - V. 116, l. 12. - P. 735-738.

ISSN/EISSN:

0020-0190 / 1872-6119

Type:

Article

Abstract:

A length n word is (palindromic) rich if it contains the maximum possible number, which is n, of distinct non-empty palindromic factors. We prove both necessary and sufficient conditions for richness in terms of run-length encodings of words. Relating sufficient conditions to integer partitions, we prove a lower bound of order C-root n, where C approximate to 37.6, on the growth function of the language of binary rich words. From experimental study we suggest that this growth function actually grows more slowly than n(root n) which makes our lower bound quite reasonable. (C) 2016 Elsevier B.V. All rights reserved.

Author keywords:

Combinatorial problems; Palindrome; Rich word; Growth function; Integer partition PERIODIC-LIKE WORDS

DOI:

10.1016/j.ipl.2016.07.001

Web of Science ID:

ISI:000382593100001

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

—

Другие поля

Поле	Значение
Month	DEC
Publisher	ELSEVIER SCIENCE BV
Address	PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
Language	English
EISSN	1872-6119
Keywords-Plus	PERIODIC-LIKE WORDS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Information Systems
Author-Email	c3guo@uwaterloo.ca shallit@uwaterloo.ca arseny.shur@urfu.ru
Funding-Acknowledgement	Russian Foundation for Basic Research {[}16-01-00795]
Funding-Text	Partially supported by the grant 16-01-00795 of the Russian Foundation for Basic Research.
Number-of-Cited-References	18
Usage-Count-Since-2013	3
Journal-ISO	Inf. Process. Lett.
Doc-Delivery-Number	DV0FJ