Total palindrome complexity of finite words |
| |
Authors: | Mira-Cristiana Anisiu Valeriu Anisiu |
| |
Institution: | a Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy, Cluj-Napoca, Romania b Babe?-Bolyai University of Cluj-Napoca, Faculty of Mathematics and Computer Science, Department of Mathematics, Romania c Sapientia University Cluj-Napoca, Department of Mathematics and Informatics Tg. Mure?, Romania |
| |
Abstract: | The palindrome complexity function palw of a word w attaches to each n∈N the number of palindromes (factors equal to their mirror images) of length n contained in w. The number of all the nonempty palindromes in a finite word is called the total palindrome complexity of that word. We present exact bounds for the total palindrome complexity and construct words which have any palindrome complexity between these bounds, for binary alphabets as well as for alphabets with the cardinal greater than 2. Denoting by Mq(n) the average number of palindromes in all words of length n over an alphabet with q letters, we present an upper bound for Mq(n) and prove that the limit of Mq(n)/n is 0. A more elaborate estimation leads to . |
| |
Keywords: | Palindrome complexity Finite words |
本文献已被 ScienceDirect 等数据库收录! |
|