Published January 10, 2003
| Submitted
Journal Article
Open
Palindrome complexity
Abstract
We study the palindrome complexity of infinite sequences on finite alphabets, i.e., the number of palindromic factors (blocks) of given length occurring in a given sequence. We survey the known results and obtain new results for some sequences, in particular for Rote sequences and for fixed points of primitive morphisms of constant length belonging to "class P" of Hof–Knill–Simon. We also give an upper bound for the palindrome complexity of a sequence in terms of its (block-)complexity.
Additional Information
© 2002 Michael Baake:. Published by Elsevier. Available online 6 December 2002. Dedicated to Jean Berstel for his 60th birthday with our very best wishes. JPA, MB, and DD began to discuss together on palindromes during the summer school and workshop "The Mathematics of Aperiodic Order" at the University of Alberta at Edmonton. They want to thank very warmly R. V. Moody for having organized this conference and having permitted many people from different fields to confront questions and knowledges. The second author thanks the German Research Council (DFG) for its support. The fourth author thanks the German Academic Exchange Service for /nancial support through Hochschulsonderprogramm III (Postdoktoranden). Finally we would like to thank A. Rodenhausen for her questions on the Kolakoski sequence, S. Brlek for his helpful comments on this sequence, and V. Berthé for several useful comments on a previous version of this paper.Attached Files
Submitted - 0106121.pdf
Files
0106121.pdf
Files
(275.4 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:8a2b0f14d3cafc6e5c9e98e78650b5a5
|
275.4 kB | Preview Download |
Additional details
- Eprint ID
- 76405
- DOI
- 10.1016/S0304-3975(01)00212-2
- Resolver ID
- CaltechAUTHORS:20170408-212853433
- Deutsche Forschungsgemeinschaft (DFG)
- Hochschulsonderprogramm III
- Deutscher Akademischer Austauschdienst (DAAD)
- Created
-
2018-04-02Created from EPrint's datestamp field
- Updated
-
2023-09-28Created from EPrint's last_modified field