Open problems

The following open problems were considered at the workshop. If you find a solution to any of the problems, don't hesitate to contact the organizers of the workshop so that we can note it on this website!

  1. Superpolynomial speedup via LZ-factorization (Travis) A paper by Crochemore, Iliopoulos, Kociumaka, Radoszewski, Rytter, and Walen at ISAAC 2014 presented an example of an FPT algorithm for a problem on strings. One can possibly obtain a seriuos speedup in the solution via LZ-factorization of the input text. The goal is to find more problems of this kind.
  2. BWT validation — wildcards, corruption (Jackie)
  3. Small space multipattern matching (Pawel, Travis) m patterns and a text are given with read-only access. The problem is pattern matching in O(m) space. One can imagine different kinds of output: YES/NO is any of the pattern occurs, YES/NO for each pattern, an example occurrence for each pattern. The total length of input is n. An O(n1.2poly(log n))-time algorithm was developed during the workshop (Pawel and Tomek Kociumaka know the details).
  4. Bounds on non-standard squares (Kuba, Tomek) How many distinct order-preserving squares and parameterized squares can a string of length n contain? (Some partial results are in a paper by Kociumaka, Radoszewski, Rytter, and Walen at DLT 2014)
  5. DAWG construction for partial words (Bartek) How to efficiently construct a subword graph (DAWG) for a partial word? The size of this graph can be exponential. We are interested in construction time linear in the size of the DAWG.
  6. Prefix-Suffix Duplication (Marius) For a string s, by PrefDup(s) we denote a string s's, where s' is any prefix of s. By SufDup(s) we denote a string ss', where s' is any suffix of s. In this problem we are given two strings u, v. We are to determine whether, by iterating operations PrefDup and/or SufDup on both strings, one can obtain the same string. Is this problem decidable?
  7. Number of Lyndon roots of runs in intervals (Maxime) For each run in a string we find the leftmost occurrence of its Lyndon root (for definitions see this paper). Prove or disprove: an interval of length k in the word fully contains at most k such Lyndon roots of runs.
  8. Bound on gapped repeats (Shunsuke) Prove or disprove: a word of length n contains O(α n) α-gapped repeats (an O(α2n) bound can be found in a paper by Kolpakov, Podolskiy, Posypkin, and Khrapov from CPM 2014)
    This problem has been solved by Dominik Koeppl, Tomohiro I, and Shunsuke Inenaga: The conjecture of O(α n) holds for the maximum number of maximal α-gapped repeats. They further have proven that the same bound holds for the maximum number of maximal α-gapped palindromes (see a paper by Kolpakov and Kucherov). They are currently trying to pinpoint both numbers down to some small constants. [priv.comm.]