https://www.dagstuhl.de/14111

# Combinatorics and Algorithmics of Strings

## 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)

## Summary

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

## Classification

• Data Structures / Algorithms / Complexity

## Keywords

• Combinatorics on words
• String algorithms
• Automata

## Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.