• English
    • français
  • English 
    • English
    • français
View Item 
  •   WinnSpace Home
  • Department of Mathematics and Statistics
  • James D. Currie
  • View Item
  •   WinnSpace Home
  • Department of Mathematics and Statistics
  • James D. Currie
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Growth rate of binary words avoiding xxxR

Thumbnail

View Open

Binary words avoiding xxxR revised - asymptotics.pdf (344.2Kb)

Metadata

Show full item record

Author

Currie, James D.
Rampersad, Narad

Uri

http://hdl.handle.net/10680/1760

Date

2016-01

Doi

doi.org/10.1016/j.tcs.2015.11.004

Citation

Theoret. Comput. Sci. 609 (2016), 456–468

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.

Collections

  • James D. Currie

Report a copyright concern

Contact Us | Send Feedback
 

 

Browse

All of WinnSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Report a copyright concern

Contact Us | Send Feedback