Re: RFC: implementation of package pools
William Lee Irwin III wrote:
>
> > which is just conjunction of propositional symbols or their negations.
> > In this case, it's already known which values the symbols would take.
> > In many other cases we have simple conjunctive forms of the sort
> > (P \/ Q) /\ (S \/ !T) /\ X
> > in which there's little or no overlap of propositional symbols among
> > conjunctions. [makes the instance quite easy to solve]
> > and correct me if I'm wrong, but the propositional sentences are
> > unrestricted CNF (conjunctive normal form), so it really is SAT.
> > the sentences in the database might be easy instances on the other hand.
>
> [suggestion to use AI algorithms for this sort of thing]
>
Hell no! If I suggested using AI for some of the traditional unix
style stuff here, I'd probably be hung on the tallest tree.
> This stuff sounds much like logic programming to me. Not that anyone
> would listen to a suggestion involving advanced languages, but it may
> well be possible to reuse some sort of logic programming engine, or,
> even easier, write this in Prolog (or some other logic language).
>
Prolog has some predicate logic and second-order logic constructs
which would make it an overkill for this simple application. Even
in this simple case involving only propositional calculus, we bump
into the famous NP-complete SAT problem. :( Lucky that the instances
we're dealing with are easy instances.
> Vast amounts of additional generality could also be implemented this way.
Yes, I'd like to take a look at the available logic languages in
debian for another project. I've used prolog before but only in AI
courses. There's GNU prolog and swi prolog in debian, there's also
a new language called mercury which I haven't been able to look at.
--
Eray (exa) Ozkural
Comp. Sci. Dept., Bilkent University, Ankara
e-mail: erayo@cs.bilkent.edu.tr
www: http://www.cs.bilkent.edu.tr/~erayo
Reply to: