Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102229
Title: Palindromic rich words and run-length encodings
Authors: Guo, C.
Shallit, J.
Shur, A. M.
Issue Date: 2016
Publisher: Elsevier B.V.
Citation: Guo C. Palindromic rich words and run-length encodings / C. Guo, J. Shallit, A. M. Shur. — DOI 10.1016/j.ipl.2016.07.001 // Information Processing Letters. — 2016. — Vol. 116. — Iss. 12. — P. 735-738.
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 Cn, where C≈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 nn, which makes our lower bound quite reasonable. © 2016 Elsevier B.V.
Keywords: COMBINATORIAL PROBLEMS
GROWTH FUNCTION
INTEGER PARTITION
PALINDROME
RICH WORD
ENCODING (SYMBOLS)
COMBINATORIAL PROBLEM
GROWTH FUNCTIONS
INTEGER PARTITIONS
PALINDROME
RICH WORD
C (PROGRAMMING LANGUAGE)
URI: http://hdl.handle.net/10995/102229
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84979598573
PURE ID: 1180603
d8e3572e-9131-4118-8ff9-c969584f4bcf
ISSN: 200190
DOI: 10.1016/j.ipl.2016.07.001
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84979598573.pdf192,64 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.