INESC-ID Distinguished Lecture

Prof. Maxime Crochemore

Université Paris-Est, France

Repetitions in Strings

02 December 2013

17h 00m, meeting room @ Av Duque Ávila, 23, Lisboa

Abstract

>Large amounts of text are generated every day in the cyberspace via Web sites, emails, social networks, and other communication networks. These text streams need to be analysed to detect critical events or the monitor business for example. An important characteristics to take into account in this setting is the existence of repetitions in texts. Their study constitutes a fundamental area of combinatorics on words due to major applications to string algorithms, data compression, music analysis, and biological sequences analysis, etc. The talk surveys algorithmic methods used to locate repetitive segments in strings. It discusses the notion of runs that encompasses various types of periodicities considered by different authors, as well as the notion of maximal-exponent factors that captures the most significant repeats occurring in a string. The design and analysis of repeat finders rely on combinatorial properties of words and raise a series of open problems in combinatorics on words.

Bio

>Prof. Maxime Crochemore received his PhD in 1978 and his Doctorat (DSc) in 1983 at the University of Rouen. He got his first professorship position at the University of Paris-Nord in 1985 where he acted as President of the Department of Mathematics and Computer Science for two years. He became professor at the University Paris 7 in 1989 and was involved in the creation of the University of Marne-la-Valle where he is Professor, Emeritus from 2007. He also created the Computer Science research laboratory of this university in 1991 and was the director until 2005. He was Deputy Scientific Director of the Information and Communication Department of CNRS from 2004 to 2006. He was Senior Research Fellow from 2002 to 2007 and is presently Professor at King's College London. Prof. Crochemore's research interests are in the design and analysis of algorithms. His major achievements are on string algorithms, which includes pattern matching, text indexing, coding, and text compression. He also works on the combinatorial background of these subjects and on their applications to bio-informatics. He has co-authored several textbooks on algorithms and published more than 200 articles. He has been the recipient of several French grants on string algorithms and bio-informatics. He participated in a good number of international projects on algorithms and supervised to completion more than twenty PhD students.

Host

>Ana Teresa Correia de Freitas

Return to Distinguished Lecture Series List