Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/102229
Название: | Palindromic rich words and run-length encodings |
Авторы: | Guo, C. Shallit, J. Shur, A. M. |
Дата публикации: | 2016 |
Издатель: | Elsevier B.V. |
Библиографическое описание: | 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. |
Аннотация: | 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. |
Ключевые слова: | 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://elar.urfu.ru/handle/10995/102229 |
Условия доступа: | info:eu-repo/semantics/openAccess |
Идентификатор SCOPUS: | 84979598573 |
Идентификатор WOS: | 000382593100001 |
Идентификатор PURE: | d8e3572e-9131-4118-8ff9-c969584f4bcf 1180603 |
ISSN: | 200190 |
DOI: | 10.1016/j.ipl.2016.07.001 |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-84979598573.pdf | 192,64 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.