Hi,

I am construction a Full Text Search engine replacing the internal MySQL
engine in an experiment for index all the content of 20 years publications
of a newspaper, and the first layer to do a search is to convert the Boolean
Phrase entered by the user to a 3-CNF (3-conjuntive normal form).

All the FTS is programed in PERL, as I love it !, but I can't find a module
or an algorithm to reduce the expression to the 3-CNF.

I know that the problem to reduce some sentence to the 3-CNF-SAT form is
NP-complete, but I also read in my AI books that it's possible to implement
(without any garanties of the stop point and end time), as it is implemented
in Prolog or Lisp, then, my first approuch is to find some module to do the
reduction, if I cannot find, my second alternative is to glue my Perl
program to some Prolog interpreter (is it possible in Linux, I never tried
?).

Could someone help me ?

Thanks
Roberto Slepetys