Two new papers that I have co-authored are available on Arxiv:
"Detecting Unary Patterns" (SPIRE 2017, new title: Detecting One-Variable Patterns), written together with Dmitry Kosolobov and Dirk Nowotka, proposes an efficient algorithm that locates in a text all the instances of a pattern that includes strings of letters and one-repeated variable (that can be replaced, uniformly, by any string of letters); the repeated variable can appear also reveresed.
This paper was started last year, when Dmitry visited us in Kiel, and put on Arxiv a while ago. However, since then it went through many changes and reached the current (nicer) form. It improves some of the algorithms presented in the papers from STACS 2014 (written together with Pawel Gawrychowski and Dirk Nowotka) and STACS 2015 (written together with Markus Schmid, Robert Mercas, and Henning Fernau).
"The Hardness of Solving Simple Word Equations" (MFCS 2017), written together with Joel Day and Dirk Nowotka, shows that the satisfiability of some very simple word equations is NP-complete. In word equations, we equate two strings (called sides) that contain variables and strings of letters. We want to check whether there is a way to assign (uniformly) strings of letters to the variables, such that the two sides become equal. In our simple case, each variable occurs at most once in each side and the order of the variables occurring in both sides is the preserved (the variables can be, however, separated by potentially distinct constant factors). Surprisingly, solving such simple equations, even when the sides contain exactly the same variables, is NP-hard. By considerations regarding the combinatorial structure of the shortest solutions of the more general quadratic equations we obtain that the satisfiability problem for regular-ordered equations is in NP. Finally, we also show that a related class of simple word equations, that generalises one-variable equations, is in P.
This paper was the result of the work Joel and I started recently on word equations and closes some of the open problems left in the paper from DLT 2016, written together with Markus Schmid and Dirk Nowotka. The paper published on Arxiv is a "cleaner" version of the paper we submitted, with some type-o-s and imprecisions fixed.
Both these papers are part of my current DFG-research project, on algorithms and combinatorics of words.
