Dagstuhl-Seminar 24472
Regular Expressions: Matching and Indexing
( 17. Nov – 22. Nov, 2024 )
Permalink
Organisatoren
- 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)
Kontakt
- Marsha Kleinbauer (für wissenschaftliche Fragen)
- Jutka Gasiorowski (für administrative Fragen)
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.
Klassifikation
- Data Structures and Algorithms
Schlagworte
- finite automata
- regular expressions
- complex patterns
- text indexing
- graph matching and indexing