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

Location

SW101,
Cornwallis South West,
University of Kent,
Canterbury,
Kent,
CT2 7NF
United Kingdom
Map

Details

Contact: O.Chitil
E: oc@kent.ac.uk
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