AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING Conferences uri icon

  •  
  • Overview
  •  
  • Research
  •  
  • Identity
  •  
  • Additional Document Info
  •  
  • View All
  •  

abstract

  • An asymptotic lower bound for the maxrun function ρ(n) = max {number of runs in string x | all strings x of length n} is presented. More precisely, it is shown that for any ε > 0, (α−ε)n is an asymptotic lower bound, where [Formula: see text]. A recent construction of an increasing sequence of binary strings “rich in runs” is modified and extended to prove the result.

publication date

  • February 2008