Algorithmic Combinatorics on Sequences
Final Report Abstract
The main results we have obtained within this project are related to the area of combinatorial pattern matching. In particular, related to the area of matching patterns with variables, we have developed efficient algorithms for matching various classes of patterns: unary patterns, k-local patterns, generalized-pattern-repetitions, etc. The notion of k-locality, originally defined for patterns, can be extended to arbitrary strings, yielding, as such, an interesting descriptional complexity measure for sequential data. The study of this measure led to interesting results related to the problem of matching patterns with variables, as well as to some unexpected results regarding the efficient computation and approximation of graph-parameters, and, ultimately, to a state-of-the-art approximation algorithm for computing the cutwidth of graphs (a very well studied problem). The investigation of classes of patterns with variables with tractable matching problem was extended to the study of word equations whose sides are such patterns. A natural questions about such word equations is whether deciding their satisfiability is tractable or not. Surprisingly, we were able to show that some very simple class have an NP-hard satisfiability problem. For instance, the class of equations in which exactly the same variables occur in both sides of the equations, and, moreover, in the same order, is one of the simplest classes of equations with an unbounded number of variables; its satisfiability problem is NP-complete. Our results also led to the development of a series of tools which enabled us to show that deciding the satisfiability of word equations from certain (non-trivial) classes is in NP or even in P. This opens an attack direction to closing some open problems related to word equations, e.g., settling the complexity of the satisfiability of quadratic word equations. Similarly, we investigated a series of logical theories that extend the existential theory of equations over free monoids (i.e., the theory of word equations), and are relevant for the development of practical string solvers; we showed their decidability or, respectively, undecidability. Extending our study of patterns in words, we investigated a particular class of patterns in permutations, the so called rollercoasters. In particular, we discussed the existence of long rollercoasters in permutations, extending, as such, the classical study of long increasing/decreasing sequences in permutations. The results we have obtained are of both combinatorial and algorithmic nature. We continued our work in the area of combinatorics on words, and obtained results related to the avoidability of repetitions under permutations (pseudo-repetitions) and to pseudo-repetition enforcing relations between words. These were complemented by algorithmic results related to the detection of repetitive structures in words. For instance, we developed algorithms that compute efficiently square-factorisations of words.
Publications
- Factorizing a string into squares in linear time. In 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, volume 54 of LIPIcs, pages 27:1–27:12, 2016
Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, and Florin Manea
(See online at https://doi.org/10.4230/LIPIcs.CPM.2016.27) - Detecting one-variable patterns. In String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, volume 10508 of Lecture Notes in Computer Science, pages 254–270. Springer, 2017
Dmitry Kosolobov, Florin Manea, and Dirk Nowotka
(See online at https://doi.org/10.1007/978-3-319-67428-5_22) - Local patterns. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, volume 93 of LIPIcs, pages 24:1– 24:14, 2017
Joel D. Day, Pamela Fleischmann, Florin Manea, and Dirk Nowotka
(See online at https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.0) - Longest gapped repeats and palindromes. Discrete Mathematics & Theoretical Computer Science, 19(4), 2017
Marius Dumitran, Pawel Gawrychowski, and Florin Manea
(See online at https://doi.org/10.23638/DMTCS-19-4-4) - The hardness of solving simple word equations. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, volume 83 of LIPIcs, pages 18:1–18:14, 2017
Joel D. Day, Florin Manea, and Dirk Nowotka
- On matching generalised repetitive patterns. In Developments in Language Theory - 22nd International Conference, DLT, volume 11088 of Lecture Notes in Computer Science, pages 269–281, 2018
Joel D. Day, Pamela Fleischmann, Florin Manea, Dirk Nowotka, and Markus L. Schmid
(See online at https://doi.org/10.1007/978-3-319-98654-8_22) - Rollercoasters and caterpillars. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, volume 107 of LIPIcs, pages 18:1–18:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018
Therese C. Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit
- The satisfiability of word equations: Decidable and undecidable theories. In Reachability Problems - 12th International Conference, RP 2018, volume 11123 of Lecture Notes in Computer Science, pages 15–29, 2018
Joel D. Day, Vijay Ganesh, Paul He, Florin Manea, and Dirk Nowotka
(See online at https://doi.org/10.1007/978-3-030-00250-3_2) - Tighter bounds and optimal algorithms for all maximal α-gapped repeats and palindromes - finding all maximal α-gapped repeats and palindromes in optimal worst case time on integer alphabets. Theory Comput. Syst., 62(1):162–191, 2018
Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Koppl, and Florin Manea
(See online at https://doi.org/10.1007/s00224-017-9794-5) - Fast and longest rollercoasters. In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 of LIPIcs, pages 30:1–30:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019
Pawel Gawrychowski, Florin Manea, and Radoslaw Serafin
