Abstract | ||
---|---|---|
We study the problem of constructing infinite words having a prescribed finite set P of palindromes. We first establish that the language of all words with palindromic factors in P is rational. As a consequence we derive that there exists, with some additional mild condition, infinite words having P as palindromic factors. We prove that there exist periodic words having the maximum number of palindromes as in the case of Sturmian words, by providing a simple and easy to check condition. Asymmetric words, those that are not the product of two palindromes, play a fundamental role and an enumeration is provided. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1142/S012905410400242X | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Finite set,Existential quantification,Enumeration,Palindrome,Periodic graph (geometry),Mathematics,Combinatorics on words | Journal | 15 |
Issue | ISSN | Citations |
2 | 0129-0541 | 46 |
PageRank | References | Authors |
2.69 | 4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Srecko Brlek | 1 | 151 | 26.29 |
Sylvie Hamel | 2 | 59 | 4.22 |
Maurice Nivat | 3 | 1261 | 277.74 |
Christophe Reutenauer | 4 | 356 | 64.56 |