Archive of posts with tag 'BryanWilkinson'

• Bryan Wilkinson, Generalized Davenport-Schinzel Sequences: Regaining Linearity

  Generalized Davenport-Schinzel Sequences: Regaining Linearity

  Bryan Wilkinson
  Aarhus University, Danmark

  2014/11/18 Tuesday 4PM-5PM
  Room 1409

  We prove the linearity (of the lengths) of some generalized Davenport-Schinzel sequences. Standard Davenport-Schinzel sequences of order 2 (avoiding abab) are linear, while those of order 3 (avoiding ababa) and higher can be superlinear. Our goal is to determine what pattern(s), in addition to ababa, must be forbidden to regain linearity. This work is motivated by an intriguing open problem: does the lower envelope of any set of degree 3 polynomials have linear complexity?

  Tags:

  • BryanWilkinson