Taming Regular Expressions with Logic

Abstract

Regular expressions are one of the most widely used ways to specify patterns strings. Originally developed in theoretical computer science, they quickly found their way into applications.

But using regular expressions for non-trivial trivial tasks can quickly lead to additional problems, from technical debt over unexpected behaviour to regex denial of service attacks.

In this talk, I will explain how these problems can be avoided by treating regular expressions as relational queries. This is only one application of the new logic FC that combines finite model theory with combinatorics on words and which my coauthors and I developed over the last years. 

I will also provide a brief survey of our insights into FC and sketch how it can be used to design query languages on strings (in the style of SQL or Datalog) and schema languages for textual data.

Speaker

Dr Dominik Freydenberger, Computer Science Department, Loughborough University