[Haskell-cafe] Regular Expression Simplification

wren romano winterkoninkje at gmail.com
Sat Mar 22 22:19:05 UTC 2014

On Thu, Mar 20, 2014 at 8:17 AM, Berg, Matias Juho
<m.berg.10 at aberdeen.ac.uk> wrote:
> Does anyone have any suggestions on where to look for more examples so I can
> see what kinds of attempts people have used to try and solve this problem?
> Also if someone has worked on this kind of problem was Kleene algebra a good
> starting point?

It's not Haskell-specific, but you should look at the work done by
Xerox on XFST/OpenFST. One of the major issues they needed to tackle
is how to avoid the exponential blowup that can arise from
manipulating FSTs. I don't recall how much simplification they do, but
their main goal and use case was also dealing with natural language.

Live well,

More information about the Haskell-Cafe mailing list