dc.contributor.author | Currie, James D. | |
dc.contributor.author | Rampersad, Narad | |
dc.date.accessioned | 2019-12-11T15:47:08Z | |
dc.date.available | 2019-12-11T15:47:08Z | |
dc.date.issued | 2016-01 | |
dc.identifier.citation | Theoret. Comput. Sci. 609 (2016), 456–468 | en_US |
dc.identifier.uri | http://hdl.handle.net/10680/1760 | |
dc.description.abstract | Abstract
Consider the set of those binary words with no non-empty factors of the form
xxx^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. | en_US |
dc.description.uri | doi.org/10.1016/j.tcs.2015.11.004 | en_US |
dc.language.iso | en | en_US |
dc.publisher | Elsevier | en_US |
dc.rights | info:eu-repo/semantics/openAccess | en_US |
dc.subject | patterns with reversal, enumeration, words avoiding patterns, combinatorics on words | en_US |
dc.title | Growth rate of binary words avoiding xxxR | en_US |
dc.type | Article | en_US |
dc.identifier.doi | doi.org/10.1016/j.tcs.2015.11.004 | en_US |