Combinatorial Aspects of Words and their Applications
Final Report Abstract
The objectives of the current project had been described in its proposal as follows: “This project is about advances in the combinatorial understanding of sequential structures and equations and the transfer of such results to direct applications and generalized concepts. The main objectives of this project can be categorized in three parts: 1. the investigation of the repetition structure of words, 2. the investigation of word equations and morphisms, and 3. the consideration of algorithmic problems on sequentially represented objects with combinatorial tools, and the motivated generalization of concepts and results about words.” These objectives have been met. Although not every specified conjecture could have been solved, considerable progress has been made in all three of these categories. In some cases, unexpected directions of research opened up and were followed. In particular, part 3, algorithmic progress and generalizations, did yield interesting results with a considerable move towards possible applications. Motivated from algorithmic questions in the field of computational biology, a general theme that influenced all three parts of this project – repetitions, equations, and algorithms – emerged, namely considering problems on words under some transformation. Such a transformation could be a morphism or antimorphism, in particular a permutation and, more specific, an involution. Taking this point of view did not just allow us to generalise concepts of word combinatorics, but also brought our work closer to application fields. For this reason, questions related to this theme have been emphasised during this project.
Publications
- Combinatorics of pseudo-repetitions. In Mathematical Foundations of Computer Science, MFCS 2012, Bratislava, volume 7464 of Lecture Notes in Comput. Sci., pages 668–680, 2012
F. Manea, R. Mercas, and D. Nowotka
(See online at https://doi.org/10.1007/978-3-642-32589-2_58) - String matching with involutions. In Unconventional Computation and Natural Computation, UCNC 2012, Orléans, volume 7445 of Lecture Notes in Comput. Sci., pages 106–117, 2012
C. Grozea, F. Manea, M. Müller, and D. Nowotka
(See online at https://doi.org/10.1007/978-3-642-32894-7_11) - Cubic patterns with permutations. J. Comput. Syst. Sci., 81(7):1298–1310, 2015
F. Manea, M. Müller, and D. Nowotka
(See online at https://doi.org/10.1016/j.jcss.2015.04.001) - k-abelian pattern matching. J. Discrete Algorithms, 34:37–48, 2015
T. Ehlers, F. Manea, R. Mercas, and D. Nowotka
(See online at https://doi.org/10.1016/j.jda.2015.05.004) - Unary patterns under permutations. Theor. Comput. Sci., 743:72–82, 2018
J. Currie, F. Manea, D. Nowotka, and K. Reshadi
(See online at https://doi.org/10.1016/j.tcs.2018.05.033)
