Dagstuhl Seminar 14111
Combinatorics and Algorithmics of Strings
( Mar 09 – Mar 14, 2014 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/14111
Organizers
- Maxime Crochemore (King's College London, GB)
- James D. Currie (University of Winnipeg, CA)
- Gregory Kucherov (University Paris-Est - Marne-la-Vallée, FR)
- Dirk Nowotka (Universität Kiel, DE)
Contact
- Andreas Dolzmann (for scientific matters)
- Annette Beyer (for administrative matters)
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.
Processing strings efficiently is of concern in practically every application field. Understanding the combinatorial properties of sequences is a prerequisite for designing efficient algorithms on them. The Dagstuhl seminar 14111 has been concerned with exactly that: Combinatorics and Algorithmics of Strings.
This Dagstuhl seminar was attended by 41 researchers from 12 countries representing the two fields, algorithmics and combinatorics, about equally, although it needs to be mentioned that the overlap of these two communities is rather large. Inviting these close communities to Dagstuhl gave us the opportunity to start from substantial common ground and to work on scientific problems right from the beginning. Given that background, tutorials or other introductory sessions were not considered to be suitable elements for this seminar. Instead, much time was spent for problem posing and solving sessions. This seminar has clearly been research oriented.
The first seminar day, Monday, was entirely devoted to posing open problems. Based on those, the participants were able to form interest groups and engage into research activities early on. In the next days regular research talks and some more open problems were presented. However, time slots for research work were also allocated. On the last day of the seminar, Friday, we were able to already present some solutions to the problems posed in the beginning. In general, it is not to be expected that research problems are solved within a week (and most weren't), but it illustrates the impact of the meeting on catalysing research and collaboration between the participants.
The following two are great examples of such collaboration. Florin Manea asked about the complexity of deciding whether or not two words $u$ and w are $k$-binomial equivalent, that is, is the number of occurrences of all scattered subwords up to length k equal in u and w? Contributions by Pawel Gawrychowski (polynomial Monte-Carlo algorithm in the logarithmic word-size RAM model), Juhani Karhumäki, and Wojciech Rytter (polynomial time on a unit-cost RAM model), and discussions with Dominik Freydenberger and Manfred Kufleitner finally led to the conclusion that the problem can be solved in polynomial time in the logarithmic word-size RAM model. Another problem was posed by Juhani Karhumäki and Michael Rao (not present at the seminar) on the avoidability of shuffle squares. They asked: Does there exist an infinite word over some finite alphabet which avoids all factors that are a shuffle product of a word with itself? James Currie realized that shuffle squares can indeed be avoided applying the Lovász Local Lemma in his argument. However, this solution of avoidability in principle led to a proof for a very large alphabet, the size of which being a number of more than 40 digits. A few days after this Dagstuhl seminar Mike Müller improved that result by giving a rather low upper bound on the alphabet size of 10 on which shuffle squares can be avoided using a resent result by Joseph Miller. In general, it has to be noted that progress was made in many more areas and several papers in preparation were announced already.
Another notable highlight of the seminar was a session dedicated to word equations. Senior researchers of that particular research area, like Wojciech Plandowski and Volker Diekert, and young protagonists, like Aleksi Saarela, Stepan Holub, and Artur Jez, who talked about their recent efforts in developing the field, contributed and exchanged ideas. Such a unique assembly of major experts in word equations and their contributions at Dagstuhl was rather unique and a remarkable event.
In the light of such developments, it can be safely claimed that this seminar was a great success. Given the quality of presentations on this seminar and the constructive intensity of discussions, it is self-evident that a follow-up should be organised. We are grateful to all participants for their contributions to this successful seminar as well as to the staff of Schloss Dagstuhl for their great service.
Creative Commons BY 3.0 Unported license
Maxime Crochemore, James D. Currie, Gregory Kucherov, and Dirk Nowotka
- Dany Breslauer (University of Haifa, IL) [dblp]
- Julien Cassaigne (CNRS - Marseille, FR) [dblp]
- Julien Clément (Caen University, FR) [dblp]
- Maxime Crochemore (King's College London, GB) [dblp]
- James D. Currie (University of Winnipeg, CA) [dblp]
- Volker Diekert (Universität Stuttgart, DE) [dblp]
- Gabriele Fici (University of Palermo, IT) [dblp]
- Johannes Fischer (TU Dortmund, DE) [dblp]
- Dominik D. Freydenberger (Goethe-Universität - Frankfurt a. M., DE) [dblp]
- Anna E. Frid (Aix-Marseille University, FR) [dblp]
- Pawel Gawrychowski (MPI für Informatik - Saarbrücken, DE) [dblp]
- Amy Glen (Murdoch University, AU) [dblp]
- Stepan Holub (Charles University - Prague, CZ) [dblp]
- Artur Jez (MPI für Informatik - Saarbrücken, DE) [dblp]
- 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]
- Manfred Kufleitner (Universität Stuttgart, DE & TU München, DE) [dblp]
- Gad M. Landau (University of Haifa, IL) [dblp]
- Alessio Langiu (King's College London, GB & University of Palermo, IT) [dblp]
- Thierry Lecroq (University of Rouen, FR) [dblp]
- Moshe Lewenstein (Bar-Ilan University - Ramat Gan, IL) [dblp]
- Florin Manea (Universität Kiel, DE) [dblp]
- Giancarlo Mauri (University of Milan-Bicocca, IT) [dblp]
- Robert Mercas (Universität Kiel, DE) [dblp]
- Fillippo Mignosi (University of L'Aquila, IT) [dblp]
- Mike Müller (Universität Kiel, DE) [dblp]
- Dirk Nowotka (Universität Kiel, DE) [dblp]
- Wojciech Plandowski (University of Warsaw, PL) [dblp]
- Ely Porat (Bar-Ilan University - Ramat Gan, IL) [dblp]
- Svetlana Puzynina (University of Turku, FI) [dblp]
- Antonio Restivo (University of Palermo, IT) [dblp]
- Eric Rowland (University of Liège, BE) [dblp]
- Wojciech Rytter (University of Warsaw, PL) [dblp]
- Aleksi Saarela (University of Turku, FI) [dblp]
- Arseny M. Shur (Ural Federal Univ. - Ekaterinburg, RU) [dblp]
- Jamie Simpson (Curtin Univ. of Tech. - Perth, AU) [dblp]
- German Tischler-Höhle (Wellcome Trust Sanger Institute-Hinxton,Cambridge, GB) [dblp]
- Esko Ukkonen (University of Helsinki, FI) [dblp]
- Mikhail V. Volkov (Ural Federal Univ. - Ekaterinburg, RU) [dblp]
Related Seminars
- Dagstuhl Seminar 11081: Combinatorial and Algorithmic Aspects of Sequence Processing (2011-02-20 - 2011-02-25) (Details)
Classification
- data structures / algorithms / complexity
Keywords
- combinatorics on words
- string algorithms
- automata
