Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 24472

Regular Expressions: Matching and Indexing

( Nov 17 – Nov 22, 2024 )

Please use the following short url to reference this page:




Regular expressions and finite automata lie at the foundations of Computer Science and have been used since the sixties in basic problems like compiler design. The key algorithmic challenge is regular expression matching, that is, efficiently identifying words of a regular language within a sequence.

Over the years, there have been numerous algorithmic advances around the topic, while at the same time, their applications have spread over too many different areas like information retrieval, databases, bioinformatics, security, and others, which not only make use of standard results but also pose new and challenging variants of the regular expression matching problem. The use of regular expressions has made its way even into current standards like SQL:2016 and SPARQL. Bringing together researchers from core stringology and relevant application areas will benefit both sides, giving the opportunity to exchange novel problems and solutions of theoretical and practical nature.

The seminar aims to bring together researchers from various research directions within algorithmic aspects of regular expressions and finite automata. Furthermore, the seminar will inspire the exchange of theoretical and practical results. Our aims are to identify practically relevant restrictions and extensions of regular expression matching, as well as variants that work on graphs rather than sequences, and propose matching and indexing algorithms to handle those, together with related impossibility results.

Copyright Inge Li Gørtz, Sebastian Maneth, Gonzalo Navarro, and Nicola Prezza

  • Data Structures and Algorithms

  • finite automata
  • regular expressions
  • complex patterns
  • text indexing
  • graph matching and indexing