09.03.14 - 14.03.14, Seminar 14111

Combinatorics and Algorithmics of Strings

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.

Memorial Exhibition in honor of Aloys Ohlmann

The exhibit opens on Monday, March, 10 at 7.30 p.m. in the new building of Schloss Dagtuhl. All participants are cordially invited to attend.

This memorial exhibition in honor of Aloys Ohlmann (+16.09.2013) will display for the first time a series of 36 window paintings created by the artist in 1991. Aloys Ohlmann painted these works in homage to Bauhaus artist Oskar Schlemmer, who in 1942 - one year before his death - completed a cycle of 18 paintings representing different perspectives on window views as seen from both within and without.

www.dagstuhl.de/no_cache/en/about-dagstuhl/news/detail/meldung/519/

Motivation

Strings (aka sequences 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 (through DNA sequences) or the protein synthesis (as sequence of amino acids), and in many more different contexts. Given this universal form of representing information, the need to process strings is apparent and is actually a core purpose of computer use. Algorithms to efficiently search through, analyze, (de-)compress, match, 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 purpose of this seminar is to bring together researchers from different disciplines whose interests are string processing algorithms and related combinatorial problems on words. The two main areas of interest for this seminar are Combinatorics on Words and Stringology. Researchers from these fields work on string related problems from different angles. An exchange of their ideas promises to be mutually beneficial. Contributions from those fields can be characterized as follows where we exemplify those contributions on rather specific but by far not exhaustive topics of mutual interest.

We plan to initiate cooperation of researchers from both communities focusing on the following areas:

  • generalized avoidability questions (e.g. avoidable paterns under permutations),
  • efficient indexing for approximate queries,
  • complexity of solving word equations and the structure of word equations,
  • upper and lower bounds of string algorithms on unbounded alphabet,
  • relation of local vs. global periodicity,
  • efficient pattern matching in the streaming model.

These topics are central in combinatorics on words and stringology, respecively. Any progress in those areas would be a success of the proposed seminar. In summary, the outcome expected from this meeting is both theoretical and applied. On the theoretical side, we expect insights in the combinatorial foundations of strings beneficial to algorithmic challenges, as well as, new questions and research directions originating from practical problems. On the application side, we hope to find new algorithmic ideas for strings with better guarantees and efficient solutions to several of the string problems.