Abstract
We present a method which displays all palindromes of a given length from De Bruijn words of a certain order, and also a recursive one which constructs all palindromes of length \(n+1\) from the set of palindromes of length \(n\). We show that the palindrome complexity function, which counts the number of palindromes of each length contained in a given word, has a different shape compared with the usual (subword) complexity function. We give upper bounds for the average number of palindromes contained in all words of length n, and obtain exact formulae for the number of palindromes of length 1 and 2 contained in all words of length \(n\).
Authors
Mira-Cristiana Anisiu
Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy, Cluj-Napoca
Valeriu Anisiu
Department of Mathematics Faculty of Mathematics and Computer Science Babeş-Bolyai University of Cluj-Napoca
Zoltán Kása
Department of Computer Science Faculty of Mathematics and Computer Science Babeş-Bolyai University of Cluj-Napoca
Keywords
?
Paper coordinates
M.-C. Anisiu, V. Anisiu, Z. Kása, Properties of palindromes in finite words, Pure Math. Appl., 17 (2006) nos. 3-5, pp. 183-195.
About this paper
Journal
Pure Mathematics and Applications
Publisher Name
Romanian Academy
DOI
Print ISSN
Online ISSN
1788-800X
google scholar link
[1] J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity, Theoret. Comput. Sci., 292 (2003), 9–31.
[2] M.-C. Anisiu and J. Cassaigne, Properties of the complexity function for finite words, Rev. Anal. Num. Théor. Approx., 33 (2004), 123–139.
[3] J.-P. Borel and C. Reutenauer, Palindromic factors of billiard words, Theoret. Comput. Sci., 340 (2005), 334–348.
[4] N.G. De Bruijn, A combinatorial problem, Nederl. Akad. Wetensch. Proc., 49 (1946), 758–764 = Indag. Math., 8 (1946), 461–467.
[5] A. Ehrenfeucht, K.P. Lee and G. Rozenberg, Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. Comput. Sci., 1 (1975), 59–75.
[6] C. Flye Sainte-Marie, Solution to question nr. 48, l’Intermédiaire des Mathématiciens, 1 (1894), 107–110
[7] H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms, SIAM Review, 24 (1982), 195–221.
[8] R.A. Games, A generalized recursive construction for De Bruijn sequences, IEEE Trans. Inform. Theory, 29 (1983), 843–850.
[9] M. Giel-Pietraszuk, M. Hoffmann, S. Dolecka, J. Rychlewski and J. Barciszewski, Palindromes in proteins, J. Protein Chem., 22 (2003), 109–113.
[10] I.J. Good, Normal recurring decimals, J. London Math. Soc., 21 (1946),
167–169.
[11] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd edition (Reading, Massachusetts: Addison-Wesley), 1994.
[12] M. Heinz, Zur Teilwortkomplexität für Wörter und Folgen über einem endlichen Alphabet, EIK, 13 (1977), 27–38.
[13] A. de Luca, On the combinatorics of finite words, Theoret. Comput. Sci., 218 (1999), 13–39.
[14] A. de Luca and Al. de Luca, Combinatorial properties of Sturmian palindromes, Int. J. Found. Comput. Sci., 17 (2006), 557–573.
[15] F. Levé and P. Séébold, Proof of a conjecture on word complexity, Bull. Belg. Math. Soc. Simon Stevin, 8 (2001), 277–291.
[16] M.H. Martin, A problem in arrangements, Bull. American Math. Soc., 40 (1934), 859–864.
[17] M. Morse and G.A. Hedlund, Symbolic dynamics, Amer. J. Math., 60 (1938), 815–866.
[18] A. Ralston, A new memoryless algorithm for De Bruijn sequences, J. Algorithms, 2 (1981), 50–62