Join Zoom Meeting
https://cwi-nl.zoom.us/j/81535249101?pwd=ZDh3Y1kyZmxBUml1Tm00Rkx0NXBwdz09
Meeting ID: 815 3524 9101
Passcode: 967201
Title: Stringology - different models and approaches
Speaker: Wiktor Zuba
Abstract: In the talk I am going to present an overview of the results from some of the papers I co-authored with the stringology group of the University of Warsaw. The talk contains an overview of the problem of finding a cover (a smaller text whose occurrences cover all the positions of the input text) in many distinct stringological models and the differences encountered while studying them. A different result shows a use of stringology for solving a graph problem - a compression of a representation of a Hamiltonian cycle of a sigma-tau Cayley graph of permutations. The use of the compressed representation results in finding efficient ranking and unranking algorithms for the cycle. Yet another result shows a conditional hardness of a problem of finding an Abelian square (a word whose two parts contain the same multiset of letters) - that is show, that the problem (almost surely) cannot be solved in strongly subquadratic time (while most stringology papers aim in obtaining linear time solutions to problems).
