## 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!

**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.**BWT validation — wildcards, corruption**(Jackie)**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(n*^{1.2}poly(log n))-time algorithm was developed during the workshop (Pawel and Tomek Kociumaka know the details).**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)**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.**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?**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.**Bound on gapped repeats**(Shunsuke) Prove or disprove: a word of length*n*contains O(α n)*α*-gapped repeats (an O(α^{2}n) 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.]*