Dagstuhl Seminar 24472
Regular Expressions: Matching and Indexing
( Nov 17 – Nov 22, 2024 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/24472
Organizers
- Inge Li Gørtz (Technical University of Denmark - Lyngby, DK)
- Sebastian Maneth (Universität Bremen, DE)
- Gonzalo Navarro (University of Chile - Santiago de Chile, CL)
- Nicola Prezza (University of Venice, IT)
Contact
- Marsha Kleinbauer (for scientific matters)
- Jutka Gasiorowski (for administrative matters)
Dagstuhl Reports
As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.
- Upload (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
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.
Creative Commons BY 4.0
Inge Li Gørtz, Sebastian Maneth, Gonzalo Navarro, and Nicola Prezza
Please log in to DOOR to see more details.
- Antoine Amarilli (INRIA Lille, FR) [dblp]
- Hideo Bannai (Institute of Science Tokyo, JP) [dblp]
- Ruben Becker (University of Venice, IT) [dblp]
- Giulia Bernardini (University of Trieste, IT) [dblp]
- Philip Bille (Technical University of Denmark - Lyngby, DK) [dblp]
- Manuel Cáceres (Aalto University, FI) [dblp]
- Davide Cenzato (University of Venice, IT) [dblp]
- James Davis (Purdue University - West Lafayette, US) [dblp]
- Dominik D. Freydenberger (Loughborough University, GB) [dblp]
- Pawel Gawrychowski (University of Wroclaw, PL) [dblp]
- Adrián Gómez Brandón (University of Coruña, ES) [dblp]
- Inge Li Gørtz (Technical University of Denmark - Lyngby, DK) [dblp]
- Roberto Grossi (University of Pisa, IT) [dblp]
- Moshe Lewenstein (Bar-Ilan University - Ramat Gan, IL) [dblp]
- Konstantinos Mamouras (Rice University - Houston, US) [dblp]
- Sebastian Maneth (Universität Bremen, DE) [dblp]
- Wim Martens (Universität Bayreuth, DE) [dblp]
- Yasuhiko Minamide (Institute of Science Tokyo, JP) [dblp]
- Gonzalo Navarro (University of Chile - Santiago de Chile, CL) [dblp]
- Nicola Prezza (University of Venice, IT) [dblp]
- Cristian Riveros (PUC - Santiago de Chile, CL) [dblp]
- Markus L. Schmid (HU Berlin, DE) [dblp]
- Teresa Steiner (Technical University of Denmark - Lyngby, DK) [dblp]
- Michelle Sweering (CWI - Amsterdam, NL) [dblp]
- Simon Rumle Tarnow (Technical University of Denmark - Lyngby, DK)
- Brink van der Merwe (University of Stellenbosch, ZA) [dblp]
Classification
- Data Structures and Algorithms
Keywords
- finite automata
- regular expressions
- complex patterns
- text indexing
- graph matching and indexing
