constraint satisfaction programming
Author Message
constraint satisfaction programming

I'm looking for some interesting research in the topic of constraint logic
programming or constraint satisfaction programming. I'm already familiar with
Jaffar's and Lassez' work and also with the Prolog III approach.

1.) Any information about related research, esp. implementation of this
paradigm for different other domains than R (as in CLP(R)) are of
interest.
2.) I am also interested in applications and experience in any constraint
satisfaction based language that may contribute to an evaluation of

I appreciate any response, Thanks

Parvis
---
Parvis Avini

Mon, 20 Jul 1992 17:35:00 GMT
constraint satisfaction programming

Quote:

>I'm looking for some interesting research in the topic of constraint logic
>programming or constraint satisfaction programming. I'm already familiar with
>Jaffar's and Lassez' work and also with the Prolog III approach.

I saw an excellent talk a couple of years ago by a man named Wm. Leler
in which Wm. (pronounced Wim) discussed a constraint language called
Bertrand.  This language was developed by Wm. in connection with research
leading to his Ph.D.  His Ph.D. thesis has since been published as a
distinguished thesis by one of the computer science publishers.  It's called
Constraint Languages.  It's fairly recent.  Don't know the publisher right
off hand.

Phil Miller

Mon, 20 Jul 1992 16:27:00 GMT
constraint satisfaction programming

Quote:

>I'm looking for some interesting research in the topic of constraint logic
>programming or constraint satisfaction programming. ...

Trilogy is a logic programming language with constraints:

In the domain of integers Trilogy solves arbitrary linear forms
(Diophantine systems). For instance the query:

x >= 0 & y >= 0 & 6*x + 8*y = 46

will solve without any backtracks to

x = 5  y = 2  and  x = 1 y = 5

Linear forms can can be combined into formulas involving ands, ors and
existential quantifiers. Trilogy simplifies arbitrary such formulas. In other
words, Trilogy implements the full decision procedure for the Presburger
arithmetic.

Trilogy contains arrays. In this domain it solves constraints of
the form

a(i) = v

where an unknown (logical) array a is constrained in an unknown point i
to the unknown value v. For instance the query

a::[0..2]->[4..6] & a(0) < a(i) & a(i) < a(2)

where a is a logical array of three elements with the values constrained to
the interval [4..6] will solve without any backtracks to

a = [4,5,6] & i = 1

See also the article 538 for the solution of the Triangle Puzzle in Trilogy.
This contribution discusses a declarative technique which eliminates
most of the uses of the "var" predicate of Prolog.

The March issue of the Byte magazine contains a review of Trilogy.
logic programming with procedural and data-base programming while
remaining within the first order logic (that's why the name Trilogy:
three languages within logic) Trilogy does not contain a
single extralogical feature.

You can also obtain from me two papers of mine on Trilogy:

The Constraint Language Trilogy: Semantics and Computations

and

Types of Trilogy

The papers discuss the logic foundations of computations and the types of
Trilogy.

The Byte review is admittedly, quite terse. Moreover, the reviewer
criticized Trilogy for certain shortcomings when his programs
were incorrectly programmed (for instance the Tower of Hanoi). But overall,
the review is quite good considering the fact that the author never
encountered another constraint language since Trilogy is the first
commercially available logic language with constraints.

Trilogy, which sells for \$99.95 (US), was developed
for the IBM-PCs and compatibles by

Complete Logic Systems Inc.
741 Blueridge Ave.
N. Vancouver, BC
ph: (604) 986-3234

Mon, 17 Aug 1992 05:09:00 GMT
constraint satisfaction programming
Posting-Front-End: GNU Emacs 18.47.144 of Wed Feb 10 1988 on etlcom (berkeley-unix)

Quote:
> I'm looking for some interesting research in the topic of constraint logic
> programming or constraint satisfaction programming. I'm already familiar with
> Jaffar's and Lassez' work and also with the Prolog III approach.

See my article, entitled 'Dependency Propagation', included in IJCAI87
Proceedings, though, I'm afraid, this is not very well-written; less
than half of it talks about constraint programming, and natural
language is what the rest of it is about. I should work out its
constraint programming part in a more complete form.

A crucial difference between my DP and others (CLP, Prolog III, etc.)
is that DP deals with constraints on combinatorial objects (i.e., the
term structures of logic) whereas the constraints considered in the
other approaches are about arithmetic objects (rational numbers or
real numbers). Another difference is that in DP we look upon
processing as constraint transformation. Since the constraint is the
program here, processing is a sort of program transformation.

Currently under way is an implementation of the interpreter according
to DP. This implementation is being done in language C. The first
phase of the work is supposed to be finished within one month or two,
and will be applied to a natural-language parser based on a
unification grammar formalism.

I hope this is of some interest to you.

HASIDA, Koiti ('HASIDA' is my family name)
Machine Inference Section

Mon, 17 Aug 1992 02:52:00 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages