20. – 25. Februar 2011, Dagstuhl-Seminar 11081

Combinatorial and Algorithmic Aspects of Sequence Processing


Maxime Crochemore (King's College London, GB)
Lila Kari (University of Western Ontario – London, CA)
Mehryar Mohri (New York University, US)
Dirk Nowotka (Universität Kiel, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Report, Volume 1, Issue 2 Dagstuhl Report
Dagstuhl's Impact: Dokumente verfügbar


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.

Related Dagstuhl-Seminar


  • Data Structures
  • Algorithms
  • Complexity


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


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.