On Mon, Apr 29, 2013 at 1:41 PM, Joseph Stradling <joseph.stradl...@gmail.com> wrote: > Hello, > My name is Joseph Stradling and I am a junior chemical cngineering student > transitioning into computer science at New Mexico Tech. > > I am interested in improving the pattern matching and recognition as a > project for Google Summer of Code. I am currently trying to determine which > combination of possible project paths would be appropriately difficult and > useful. I am currently leaning towards: > > - Expression complexity measures > As I understand it, this is determining the complexity of regular > expressions. This seems challenging but fairly straightforward, and it looks > like there is pretty good literature on the subject
The paper "Understanding expression simplification" by Jacques Carette is a good introduction to these ideas (I can email you it if you can't find it online). > > - Expression tree similarity testing > Basically make something to determine similarity in expression trees. It > seems like something that can be solved with clever stacking, but I am > probably missing a big piece of the challenge > > - Heuristic equivalence testing > I assume this is just summing the two expressions and seeing if they add to > zero. > > - Semantic matching > To be perfectly honest, I have no idea how to do this cleverly. Possibly > with the heuristic equivalence testing? Also it says: > > implement semantic matching (e.g. expression: cos(x), pattern: sin(a*x) + b) > e.g by using power series for this purpose (improve series speed) I think there was some paper that described how to do this. > > I don't really know how I would go about using series for semantic matching. > Bottom line: this seems very difficult and time consuming, but it could just > be that I am pretty clueless about it. It seems pretty useful so I though it > would be worth attempting > > Questions: > What are expression signatures? I have no idea. This is probably referring to some idea from some paper on the topic. My guess, based on the name, is some kind of intelligent hash such that hash(a) != hash(b) means likely a != b and hash(a) == hash(b) means likely a == b. > Is there anything that has been recently done in this area? I think Matthew's work with unify and logpy fits this, but he can give you a more direct answer. You can also look at the recent work in the Fu trigsimp algorithm. > Is there a student already doing this? I looked over the group posts but I > didn't see anything. Not that I know of. > Would this be enough to occupy the summer? Well, honestly you picked one of the ideas on the ideas list that is rather open ended, in that the exact specifications of the problem are not determined by us. Not to discourage you, but projects like these will require a lot more from the applicant, because you will be expected to take these vague ideas that honestly even we are not sure about and make them concrete. If you do stick with this idea, one place to start would be to look at other computer algebra systems and see if they implement anything similar. That will give you some concrete ideas on what things work, and how to do them. Aaron Meurer > > I would appreciate any guidance. > -Joseph Stradling > > Application and patch to follow :-) > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sympy+unsubscr...@googlegroups.com. > To post to this group, send email to sympy@googlegroups.com. > Visit this group at http://groups.google.com/group/sympy?hl=en-US. > For more options, visit https://groups.google.com/groups/opt_out. > > -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscr...@googlegroups.com. To post to this group, send email to sympy@googlegroups.com. Visit this group at http://groups.google.com/group/sympy?hl=en-US. For more options, visit https://groups.google.com/groups/opt_out.
