Back to list of 2005/06 seminars
Regular expressions define sets of sequences with a common pattern. They are widely used in Computing, both at the surface (eg. in search queries) and beneath (eg. in program analysis). Another form of description for the very same sets is by finite-state machines that recognise sequences. For these machines there are textbook procedures to test for equivalents and to find the simplest one. But here's an odd thing: there are no such procedures for regular expresssions; we have to translate expressions (at some expense) to machines, and translating back again is tricky. Can we devise effective equivalence and simplification procedures that work directly with regular expressions?