Regular Expression Minimisation

Hi,


I am currently doing some research into minimisation of Regular
Expressions, having defined normal forms for general expressions and
developed a minimisation technique. Note that this is different from
minimisation of an FSA - I have yet to see an FSA minimisation
algorithm which produces a minimal Regular Expression when the
resulting automaton is translated into a regular expression.


(For this purpose, I am defining a minimal expression as the one which
has the minimal entropy, ex. a* is more minimal than a.)


I would like to find out about any such similar research or standard
algorithms, so that I may refer and give credit to other similar
research in my forthcoming paper on the subject.


Angelo Dalli

Return to the comp.compilers page.
Search the comp.compilers archives again.