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
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.