Growth rate of binary words avoiding xxx
| Autor: | James D. Currie, Narad Rampersad |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
General Computer Science
Logarithm 010102 general mathematics Binary number Of the form 0102 computer and information sciences 01 natural sciences Upper and lower bounds Theoretical Computer Science Set (abstract data type) Combinatorics Exponential growth 010201 computation theory & mathematics Growth rate 0101 mathematics Mathematics |
| Zdroj: | Theoretical Computer Science. 609:456-468 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2015.11.004 |
| Popis: | Consider the set of those binary words with no non-empty factors of the form x x x R . Du, Mousavi, Schaeffer, and Shallit asked whether this set of words grows polynomially or exponentially with length. In this paper, we demonstrate the existence of upper and lower bounds of the form n lg ? n + o ( lg ? n ) on the number of such words of length n, where lg ? n denotes the base-2 logarithm of n. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect