Re: reduction to 3-CNF

[Sven Hilbert]

Hi Roberto,

I have the same problem right now.
Did you find a solution?

(I'd prefere Perl-only-scripts...)

 
 I am looking for some way to do the same of LogicalExpand function of
 Wolfran Mathematica. It get's a logical expression in input and returns a
 CNF of the logical expression.
 
 Ex:
 IN: LogicalExpand [  a  b  ! ( c || ( d  ! e))]
 OUT: a  b  e  (! c || a)  b  ! c  ! d
 

regards
Sven

Re: reduction to 3-CNF

[Fandiño]

Hi Roberto,

 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 ?).

you can use Language::Prolog::Yaswi to call SWI-Prolog from Perl. 

- Salva

__
Do you Yahoo!?
Yahoo! Search - Find what you’re looking for faster
http://search.yahoo.com

reduction to 3-CNF

[Roberto Slepetys Ferreira]

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