Hi.
Max Wolf wrote:
I have a fundamental question about CLP vs LP.
I played around with Mozarts LPs features and the smooth
integration with CLP stuff.
I appreciate what can be done with it for e.g. parsing (NLP).
In a previous post i have read, that alice does not support this
kind of programming style.
(no equivalent to Mozarts Space.choose)
Which looks totally reasonable to me, considering what gecode does.
Yes, as Alice is based on Gecode, we can only offer what Gecode offers.
My question is now: How should recursively defined problems that
could utilize constraints be tackled with Gecode style CLP?
Parsing is a good example. A syntax is typically defined
recursively and the size of the parse-tree isnt limited.
The examples in the CLP tutorial are all non-recursive.
That's right. Typically, there are two alternatives: (1) cast the
problem into a pure constraint problem, or (2) implement the
recursion yourself.
For (1), the XDG project could be a reference (http://www.ps.uni-
sb.de/~rade/xdg.html). The XDG parser uses something like a
"constrained parse tree", i.e. it encodes the tree into finite set
variables and constraints among these variables. So instead of
encoding the recursion into the control (i.e. more or less into the
search engine), you encode it into the constraint model.
For option (2), you more or less have to mimic the behaviour of the
Search in Mozart.
I would appreciate any pointer that sheds some light on this.
(The less academic and the more practical the better).
I guess it all comes down to add additional variables and
constraints to an existing Space during search, based upon partial
results.
You can do something like that, yes. But you can also think of this
as an optimization: instead of setting up a new constraint problem
with more variables, more propagators, and initial domains
constrained to what they were in the old problem, you recycle the old
problem by just adding the stuff you need. So this is something you
can always do.
The question is just how you get Alice/Gecode to introduce your
additional stuff into the space. For this, you will have to write
your own search engine. After propagation has finished, and before
you recursively search the children of the current space, you look at
the variables and decide whether you have to add something (or set up
a completely new space).
I hope this helps!
Cheers,
Guido
--
Guido Tack
Programming Systems Lab, Saarland University, Germany
http://www.ps.uni-sb.de/~tack
_______________________________________________
alice-users mailing list
[email protected]
http://www.ps.uni-sb.de/mailman/listinfo/alice-users
