Department of Informatics Members Win Best Paper Award

Informatics PhD students Golnaz Badkobeh and Chalita Toopsuwan and their supervisor Professor Maxime Crochemore have been awarded the Best Paper Award at the19th International Symposium on String Processing and Information Retrieval , held in Cartagena de Indias, Colombia, on 21-25 October 2012. SPIRE is one of the two top conferences, together with Combinatorial Pattern Matching, in the area of string processing, full-text indexing, data retrieval and their applications, especially to bio-informatics.

The significant result of their paper "Computing the maximal-exponent repeats of an overlap-free string in linear time" is an optimal algorithm to compute certain types of repeats in texts. Those repeats are patterns that can be used to develop data compression or data retrieval methods. The paper also contains an open question on the number of times these patterns can appear in a text. The result completes and extends previous works by various authors on consecutive repeats in strings and on which a 13-years old conjecture, the runs conjecture, is still open.