Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 11081

Combinatorial and Algorithmic Aspects of Sequence Processing

( Feb 20 – Feb 25, 2011 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:




Sequences (aka strings or words) form the most basic and natural data structure. They occur whenever information is electronically transmitted (as bit streams), when natural language text is spoken or written down (as words over, for example, the Latin alphabet), in the process of heredity transmission in living cells (as DNA sequence) or the protein synthesis (as sequence of amino acids), and in many more different contexts. Given this universal form of representing information, algorithms to efficiently search through, analyze, (de-)compress, match, and encode and decode strings are therefore of chief interest. Combinatorial problems about strings lie at the core of such algorithmic questions. Many such combinatorial problems are common in the string processing efforts in the different fields of application.

The object of concern of this seminar, sequences, implies a large degree of generality. It plays an essential role in many fields and constitutes a true cross section area. Hence, the seminar was designed to bring together researchers from different disciplines whose interest are string processing algorithms and related combinatorial problems on words. Scientists working in the following fields were invited to consider the seminar's topic from a wide range of perspectives:

  • Combinatorics on words
  • Computational biology
  • Stringology
  • Natural computing
  • Machine learning

This Dagstuhl seminar was attended by 40 researchers from 13 countries. Everyone of the five topics above was about equally represented. Given the extremely interdisciplinary approach of this meeting it was an obvious necessity to hold a tutorial on each one of the participating research areas. These tutorials were held over the first and the morning of the second seminar day (see the scientific schedule below). They provided a good introduction for the non-specialists and triggered the first scientific discussions and exchanges.

Given the quality of presentations on this seminar and the constructive intensity of discussions between and after the talks, it is self-evident that follow-ups will be attempted. After this initial meeting of different communities, where common problems were identified, personal contacts established and first cooperations initiated, further events can be sharpened in focus and more on particular cross section topics regarding combinatorial and algorithmic problems in sequence processing.

Finally, we would like to say that the organization of a meeting for researchers of so unusually diverse fields bears a certain risk. However, it can be said that the event turned out better than expected. It was more than worthwhile to have taken that risk. We are grateful to all participants for their contributions to this successful seminar as well as to the staff of Schloss Dagstuhl for their perfect service.

  • Cyril Allauzen (Google - New York, US)
  • Rolf Backofen (Universität Freiburg, DE) [dblp]
  • Marie-Pierre Béal (University Paris-Est - Marne-la-Vallée, FR)
  • Juliana Bernardes (UPMC - Paris, FR)
  • Dany Breslauer (University of Haifa, IL) [dblp]
  • Alessandra Carbone (UPMC - Paris, FR)
  • Corinna Cortes (Google - New York, US) [dblp]
  • James D. Currie (University of Winnipeg, CA) [dblp]
  • Alessandro De Luca (University of Naples, IT)
  • Linda Dib (UPMC - Paris, FR)
  • Volker Diekert (Universität Stuttgart, DE) [dblp]
  • Mike Domaratzki (University of Manitoba - Winnipeg, CA)
  • Roberto Grossi (University of Pisa, IT) [dblp]
  • Stepan Holub (Charles University - Prague, CZ) [dblp]
  • Hendrik Jan Hoogeboom (Leiden University, NL) [dblp]
  • Costas S. Iliopoulos (King's College London, GB)
  • Juhani Karhumäki (University of Turku, FI) [dblp]
  • Juha Kärkkäinen (University of Helsinki, FI) [dblp]
  • Steffen Kopecki (University of Western Ontario - London, CA) [dblp]
  • Gregory Kucherov (University Paris-Est - Marne-la-Vallée, FR) [dblp]
  • Gad M. Landau (University of Haifa, IL) [dblp]
  • Thierry Lecroq (University of Rouen, FR) [dblp]
  • Christina Leslie (Memorial Sloan-Kettering Cancer Center - New York, US) [dblp]
  • Jan Manuch (Simon Fraser University - Burnaby, CA) [dblp]
  • Mehryar Mohri (New York University, US) [dblp]
  • Dirk Nowotka (Universität Kiel, DE) [dblp]
  • Enno Ohlebusch (Universität Ulm, DE) [dblp]
  • Yann Ponty (Ecole Polytechnique - Palaiseau, FR) [dblp]
  • Svetlana Puzynina (University of Turku, FI) [dblp]
  • Narad Rampersad (University of Liège, BE)
  • Gunnar Rätsch (Memorial Sloan-Kettering Cancer Center - New York, US) [dblp]
  • Antonio Restivo (University of Palermo, IT) [dblp]
  • Wojciech Rytter (University of Warsaw, PL) [dblp]
  • Shinnosuke Seki (University of Western Ontario - London, CA) [dblp]
  • Jeffrey O. Shallit (University of Waterloo, CA) [dblp]
  • Arseny M. Shur (Ural Federal Univ. - Ekaterinburg, RU) [dblp]
  • Alexander J. Smola (Google Inc. - Mountain View, US) [dblp]
  • Sören Sonnenburg (TomTom - Berlin, DE)
  • German Tischler-Höhle (Universität Würzburg, DE) [dblp]
  • Chris J. Watkins (Royal Holloway University of London, GB)

Related Seminars
  • Dagstuhl Seminar 14111: Combinatorics and Algorithmics of Strings (2014-03-09 - 2014-03-14) (Details)

  • data structures
  • algorithms
  • complexity

  • combinatorics on words
  • stringology
  • computational biology
  • natural computing
  • machine learning