School of Computing

Feb 17
15:00 - 16:00
PLAS: Stefan Kahrs
PLAS Group Seminar
Reducing Regular Expressions (Further)

In the world of regular languages, finding the minimal DFA is a well-understood problem with a reasonably efficient implementation.For NFAs and regular expressions this is substantially harder.Yes, one can devise an algorithm which, given a regular expression, computes the smallest regular expression that has the same language, but that algorithm would compete with the definitely-best-chess-move program in the category of programs that hardly ever answer in real time.

So, what can be done, with "realistic" efforts?We have built a hierarchy of increasingly powerful transformations that tackle the issue. We explain how these transformations have been realised, as algebraic manipulations in other problem domains could often be done in a similar vein.

It turns out that on truly random regular expressionsO(n log n) trafos move very close to what is possible.Indeed, there is even such a thing as the "average size of a normal form"that is not infinity, at least for small alphabets.

Joint work with Colin Runciman


Cornwallis South West,
University of Kent,
United Kingdom


Contact: O.Chitil
School of Computing

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 14/08/2015