Detailseite
Projekt Druckansicht

Algorithmische Kombinatorik auf Folgen

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2012 bis 2019
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 218587403
 
Erstellungsjahr 2019

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung