Regular Expression Simplification
?Hi all, I am a final year undergraduate student at a university and I am doing my final honours project on natural language generation from regular expressions. For this to work efficiently I need to simplify the regular expressions before I translate them. It seems that there is some previous work done on this in Haskell but I have only been able to find this code (http://hackage.haskell.org/package/HaLeX-1.1/docs/src/Language-HaLex-RegExp....) which does some elementary simplification. 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? Best regards, Matias
Doing a quick google search, I found this paper [1]. Also you might try
searching for pushdown automata simplification or reduction
[1] - https://dl.acm.org/citation.cfm?id=2166677
On Thu, Mar 20, 2014 at 8:17 AM, Berg, Matias Juho wrote: Hi all, I am a final year undergraduate student at a university and I am doing
my final honours project on natural language generation from regular
expressions. For this to work efficiently I need to simplify the regular
expressions before I translate them. It seems that there is some previous
work done on this in Haskell but I have only been able to find this code (
http://hackage.haskell.org/package/HaLeX-1.1/docs/src/Language-HaLex-RegExp.html)
which does some elementary simplification. 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? Best regards, Matias _______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Perhaps the obvious question is "where do the regular expressions come from"? If they are generated somehow, instead of generating and then simplifying, you might find it useful to try to improve the generation process. I wonder if some of the work on grammar induction might be of use?
Hi Matias,
Kleene algebra involves the equations that are valid in the interpretation of regular expressions as word languages. So, however a simplifier of regular expressions is defined, its input and output should be equivalent w.r.t. those equations.
On the web page of my course on compiler construction (http://fldit-www.cs.tu-dortmund.de/ueb.html) you find a link to the Haskell module Compiler.hs, which includes data types, parsers and compilers for regular expressions. Among them is the algebra regNorm, which reduces regular expressions to a kind of additive normal form.
Best regards,
Peter
Am 20.03.2014 um 13:17 schrieb "Berg, Matias Juho"
Hi all,
I am a final year undergraduate student at a university and I am doing my final honours project on natural language generation from regular expressions. For this to work efficiently I need to simplify the regular expressions before I translate them. It seems that there is some previous work done on this in Haskell but I have only been able to find this code (http://hackage.haskell.org/package/HaLeX-1.1/docs/src/Language-HaLex-RegExp.html) which does some elementary simplification.
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?
Best regards,
Matias
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Thu, Mar 20, 2014 at 8:17 AM, Berg, Matias Juho
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, ~wren
On Thu, Mar 20, 2014 at 5:47 PM, Berg, Matias Juho
Hi all,
I am a final year undergraduate student at a university and I am doing my final honours project on natural language generation from regular expressions. For this to work efficiently I need to simplify the regular expressions before I translate them. It seems that there is some previous work done on this in Haskell but I have only been able to find this code (http://hackage.haskell.org/package/HaLeX-1.1/docs/src/Language-HaLex-RegExp....) which does some elementary simplification.
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?
Have not followed this thread closely so please excuse if this is already mentioned or is unfitting to your requirement Have you seen the Berry-Sethi algo?? www2.in.tum.de/hp/file?fid=571
participants (6)
-
Berg, Matias Juho -
Peter Padawitz -
Philip Dexter -
Richard A. O'Keefe -
Rustom Mody -
wren romano