Important step in solving Milner’s problem on regular expressions

Clemens Grabmayer, postdoctoral researcher at GSSI in L'Aquila, Italy, and Wan Fokkink, professor of theoretical computer science at the Vrije Universiteit Amsterdam, made an important step toward the solution of a problem posed by Turing Award winner Robin Milner in 1984, which resisted attempts at its solution ever since. Their result will be presented at the ACM/IEEE Symposium on Logic in Computer Science, to be held online in July.

05/12/2020 | 9:24 AM

The problem posed by Milner concerns regular expressions, which are fundamental to formal language theory and important for pattern matching (like the grep command in Linux). Milner proposed an equational system that allows the employment of regular expressions in proving correctness of computer programs.

Milner’s open question, which has been studied by researchers worldwide, is whether this system equates all regular expressions that give rise to equivalent program behaviour.

Grabmayer and Fokkink prove this result for a large fragment of regular expressions, and explain how the novel techniques they develop could open the way to a positive answer of Milner's question for all regular expressions.