Schedule: 2 March, 11am
Place: GSSI – MLH (Main Lecture Hall), viale F. Crispi 7
Speaker: Travis Gagie
Dalhousie University, Canada
https://www.dal.ca/faculty/computerscience/faculty-staff/travis-gagie.html
Abstract: Suppose we want to recognize the language of strings labelling walks on a finite, directed, edge-labelled graph $G$. Classic automata theory offers us two choices: a non-deterministic finite-state automaton, which is slow, or a deterministic one, which can be very big. For some natural graph classes, however — such as collections of paths, cycles and trees — we have a third option, which is both time- and space-efficient, has played an important role in the genomics revolution over the past decade and will continue to do so!
Wheeler Graphs: An Introduction with Applications to Genome Informatics