Stringology is the area of computer science which focuses on understanding the fundamental mathematical properties of strings (or texts), as well as designing efficient processing methods for them. Problems occurring in this area are central to Theoretical Computer Science with important practical applications; and algorithmic techniques originating from stringology appear in areas ranging from compiler construction to bioinformatics, from database theory (e.g., query processing in databases of textual data) to algorithmic learning theory, as well as software analysis and verification. An additional layer of difficulty in some of these areas stems from the fact that the processed data can be noisy, so robust processing methods, capable of working in such frameworks, are required and intensely studied.

Database theory is a broad area of research that provides theoretical foundations for data management systems. It studies logical languages, computational models, and efficient algorithms for managing data, combining techniques from theoretical computer science like logic, computational complexity, data structures, and algorithms, among others. Naturally, strings and more general sequences lay in the foundations of some database systems like text documents, data streams, and graph databases. Recently, the efficiency of query evaluation of these string-based systems has gained more relevance when researchers have made progress on algorithms for the enumeration, counting, or uniform generation of outputs. Here, having strong guarantees of efficiency is crucial, which calls for techniques developed in the area of algorithms of strings, automata theory, and combinatorics on words.

The main goal of this Dagstuhl Seminar is to transfer tools designed by the community working on string algorithms to tackle problems relevant to database theory, or in the case such tools do not exist, to design novel ones. We believe that for several problems considered in new applications of database theory, applying such tools can lead to obtaining better and more efficient solutions. Furthermore, because database theory is closely connected to practically relevant applications, we hope that this will lead to improvements that are useful for practitioners. To fulfil this goal, we intend to bring together leading researchers from both stringology and database theory, emphasizing string-based data management systems.

The program of the seminar will include two tutorials designed to introduce the basic concepts and problems in the relevant areas of database theory, as well as two survey talks presenting the standard repertoire of tools used in string algorithms. These tutorials will then be followed by short talks and open problem sessions to discover new connections between the two areas. We expect the following topics to be discussed: algorithmic aspects of textual information extraction, data streams management systems with a focus on the efficient analysis of data streams and property testing algorithms, and algorithmic aspects of graph databases.

Creative Commons BY 4.0

Pawel Gawrychowski, Florin Manea, Cristian Riveros, and Tatiana Starikovskaya