Life Sciences and Health Seminar Wictor Zuba

Stringology - different models and approaches
  • What Seminars Evolutionary Intelligence English
  • When 08-02-2022 from 16:00 to 17:00 (Europe/Amsterdam / UTC100)
  • Where online
  • Contact Name
  • Web Visit external website
  • Add event to calendar iCal

Join Zoom Meeting

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).