Schedule: 2 March, 11am
Place: GSSI – MLH (Main Lecture Hall), viale F. Crispi 7

Speaker: Travis Gagie
Dalhousie University, Canada

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

Leave a Reply

Your email address will not be published. Required fields are marked *