Videos

Subsequences in Words and Oscillations

Presenter
October 2, 2014
Keywords:
  • Inverse Theory, Number Theory
MSC:
  • 11P70
Abstract
Given a set of t words made of 0's and 1's, we wish to find a pair of them with a long common subsequence. How long a subsequence can be guarantee? It turns out that this question naturally leads to a decomposition of words into pieces that oscillate at approximately the same frequency. I will explain the solution to the problem above, and to some of the related questions. Based on the the joint works with J. Ma and L. Zhou.