Back to Search
Start Over
Counting the Palstars
- Publication Year :
- 2013
- Publisher :
- arXiv, 2013.
-
Abstract
- A palstar (after Knuth, Morris, and Pratt) is a concatenation of even-length palindromes. We show that, asymptotically, there are $\Theta(\alpha_k^n)$ palstars of length $2n$ over a $k$-letter alphabet, where $\alpha_k$ is a constant such that $2k-1 < \alpha_k < 2k-{1 \over 2}$. In particular, $\alpha_2 \doteq 3.33513193$.
- Subjects :
- FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
Formal Languages and Automata Theory (cs.FL)
FOS: Mathematics
Mathematics - Combinatorics
Computer Science - Formal Languages and Automata Theory
Combinatorics (math.CO)
05A15, 05A16, 05A05, 68R15
Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....adcd85b76eadf05711638ae8c6cf4e8e
- Full Text :
- https://doi.org/10.48550/arxiv.1311.2318