Amiga Plus 1995 #2/Amiga Plus CD - 1995 - No. 2.iso/internet/faq/englisch/comp.constraints

Text File | 1995-04-11 | 77.4 KB | 1,620 lines

Archive-name: constraints-faq/part1
Last-Modified: Thu Feb  2 14:44:00 1995 by Michael Jampel
Version: 1.67

Important Changes (since last posting): `Topic' changed to `Subject'

Contributions and corrections should be sent to Michael Jampel
<[e-mail]>.

This is a list of Frequently Asked Questions (and answers) for the area
of constraints, including books, journal articles, ftp archives, and
systems & products. It is posted once a month to the newsgroups
comp.constraints, comp.answers, and news.answers.

NOTE: the WWW page associated with this FAQ now contains far more
information than the FAQ does, including meta-information, i.e. pointers
to other WWW pages and ftp sites. I strongly suggest you have a look at it:
    http://web.cs.city.ac.uk/archive/constraints/constraints.html

People who helped with this FAQ include Philippe Blache
<[e-mail]>, Mark Kantrowitz <[e-mail]>, Wm Leler
<[e-mail]>, Manfred Meyer <[e-mail]>, Milind Tambe
<[e-mail]>, Thomas Schiex <[e-mail]>, and Tad Hogg
<[e-mail]>.

Thanks to Mark Kantrowitz for allowing me to use large parts of his
FAQs and Resource Guides for comp.lang.prolog and comp.ai.

----------------------------------------------------------------
Table of Contents:
 [1-1]  Introduction
 [1-2]  Definitions, scope of the word `constraint'
 [1-3]  Sources of information about constraints
 [1-4]  Constraints-related Mailing Lists
 [1-5]  FTP Archives, WWW Pages, and Other Resources
 [1-6]  Books and Journal Articles
 [1-7]  Reviews and Surveys of Constraint Systems
 [1-8]  Complexity of Constraint Satisfaction (including Phase Transition)
 [1-9]  Benchmarks for Constraint Satisfaction Problems
 [1-10] Constraints for Natural Language Processing
 [1-11] N-Ary CSPs (N > 2)
 [1-12] Constraint Libraries for C programs
 [1-13] Constraints and Rule-Based (Production) Systems
 [1-14] Interval Constraints and Newton's Approximation
 [1-15] Dynamic CSPs (Constraint Satisfaction Problems)
 [1-16] Glossary: definitions of some terms
 [1-17] Explanation of value ordering heuristics
 [1-18] Explanation of constraint entailment
 [1-19] Explanation of Don't Know / Don't Care nondeterminism

In the second part of this FAQ:
 [2-1]  Introduction (same as in part1)
 [2-2]  Free and Commercial Constraint Systems

Search for [#] to get to topic number # quickly. In newsreaders which
support digests (such as rn), [CTRL]-G will page through the answers.

----------------------------------------------------------------
Subject: [1-1] Introduction

This guide lists constraint-related resources: archives, newsgroups,
books, magazines, compilers and interpreters (in part 2), and anything
else you can think of. Also included is a list of suppliers of products
and a list of publishers.

This guide is regularly posted in two parts to comp.constraints,
usually on the 17th or 18th of each month.

It may also be obtained by anonymous ftp from City University:
    ftp.cs.city.ac.uk [138.40.91.9],
 using username "anonymous" and password "name@host".
 The files part1 and part2 are located in the directory
    pub/constraints/constraints-faq/
 [The ftp site will also contain other items on constraints.]

WWW (World Wide Web) address:
    http://web.cs.city.ac.uk/archive/constraints/constraints.html
This is also a jumping-off point giving access to most of the ftp sites
mentioned in section [1-5].

The articles posted to the newsgroup are archived by month in the same
location as this FAQ, in subdirectory
ftp.cs.city.ac.uk:/pub/constraints/archive/comp.constraints

The FAQ postings are also archived in the periodic posting archive on
rtfm.mit.edu. Look in the anonymous ftp directory
/pub/usenet/news.answers/constraints-faq in the files part1 and part2.
If you do not have anonymous ftp access, you can access the archive by
mail server as well. Send an E-mail message to [e-mail]
with "help" and "index" in the body on separate lines for more
information.

FAQs and Resource Guides for other newsgroups will usually be available
on rtfm.mit.edu too.

Disclaimer: We are not responsible for anything at all. Ever. So there.

Copyright Michael Jampel 1994. Permission to do reasonable things
not for profit is given to anyone. Anything else, ask me.

----------------------------------------------------------------
Subject: [1-2] Definitions, scope of the word `constraint'

``Constraint programming techniques can be more declarative and elegant
(hence maintainable) than standard imperative languages, without
sacrificing efficiency.''

Areas of interest include:        [suggestions welcome]
 constraint satisfaction problem (eg Travelling Salesman)
 constraint satisfaction in AI
 constraint logic programming
 concurrent constraint programming
 complexity of constraint satisfaction
 dynamic (dynamically changing) constraint satisfaction problems
 partial constraint satisfaction
 hierarchical CLP
 object-oriented constraints
 deductive databases
 applications
 links to linear programming
 heterogeneous systems (e.g. mixtures of constraints with C (see [1-12]),
    expert system shells, constraint imperative programming etc).

----------------------------------------------------------------
Subject: [1-3] Sources of Information about constraints

The newsgroups comp.lang.prolog, comp.ai, and (to a lesser extent)
sci.op-research and comp.theory are a source of information and
discussion on constraints. See also [1-4] and [1-5].

----------------------------------------------------------------
Subject: [1-4] Mailing Lists

Constraint Logic Programming
[e-mail]

For those interested in the CLP(R) Language:
[e-mail]

Both the above lists are maintained by Spiro Michaylov
<[e-mail]>. E-mail the given addresses for more info.

The list [e-mail], aimed at Concurrent
Logic Programming, no longer exists, according to Vijay Saraswat
(information via David Joslin).

Constraint Satisfaction Problem (CSP)
To subscribe, send e-mail to [e-mail] in the form
"SUB CSP-LIST <name>". (Send submissions to <[e-mail]>.)
List maintained by Thomas Schiex <[e-mail]>. Previous articles are
archived at the same place as this FAQ; availble via WWW or ftp from
ftp.cs.city.ac.uk:/pub/constraints/archive/csp-list

Intelligent Decision Support System Mailing List [not completely
relevant, but to some extent related to applications of constraints] To
post to the list e-mail <[e-mail]>. Subscription requests
should be sent to <[e-mail]>

Electronic Journal of Functional and Logic Programming (EJFLP)

 EJFLP is a refereed journal that will be distributed for free via e-mail.
 The aim of EJFLP is to create a new medium for research investigating the
 integration of the functional, logic and constraint programming paradigms.

 For instructions on submitting a paper, send an empty mail message with
    subject: Help
 to:
    [e-mail].
 You will receive an acknowledgement of your submission within a few hours.

 To subscribe to the journal, send an empty mail message to the following
 address:
    [e-mail]
 You will receive an acknowledgement of your subscription within a few days.

 If there are any problems with the mail-server, send mail to
 [e-mail].

----------------------------------------------------------------
Subject: [1-5] FTP Archives, WWW pages, and Other Resources

The following are archives that contain constraint-related material.
Most of the archives are anonymous ftp sites.

[e-mail] has created an AI ftp repository.
    ftp.cs.cmu.edu:/user/ai
See also PTF below.

Constraint Programming Paper Archive:
Aarhus University, Denmark, has established an anonymous ftp archive
for papers on "Constraint Programming" at ftp.daimi.aau.dk:/pub/CLP/
For further information, contact Brian H. Mayoh <[e-mail]>.

Constraints Bibliography:

 ftp ???            [any offers?]
 ???
 Maintained by ???

 Manfred Meyer's constraints bibliography may be made available soon.
 It, and other useful items concerning constraints, may be found on the
 City University ftp site where this FAQ is stored. See topic [1-1].

Original Constraint Logic Programming Bibliography:
[A more recent, larger, version is available on the ftp site for this
FAQ: ftp.cs.city.ac.uk:/pub/constraints/bibliography/]

 ftp archive.cis.ohio-state.edu:/pub/clp (128.146.8.52)
 cd pub/clp or cd pub/clp/{bib,papers}
 Maintained by Spiro Michaylov <[e-mail]>

ECRC tech reports are available by anonymous ftp from ftp.ecrc.de or
http://www.ecrc.de/ on WWW.

FAQs on Linear and Non-Linear programming written by John Gregory
<[e-mail]> for the sci.op-research newsgroup are posted there
and are available from rtfm.mit.edu directory /pub/usenet/sci.answers/
in files linear-programming-faq and nonlinear-programming-faq.

   ICOT:
Japan's Institute for New Generation Computer Technology (ICOT) has
made their software available to the public free of charge. The
collection includes a variety of prolog-based programs in symbol
processing, knowledge representation, reasoning and problem solving,
natural language processing. All programs are available by anonymous
ftp from ftp.icot.or.jp. Note that most of the programs are written for
the PSI machines, and very few have been ported to Unix-based
emulators. Some languages are discussed in section [2-1] in part2 of
this FAQ; for further information, send email to [e-mail], or
write to ICOT Free Software Desk, Institute for New Generation Computer
Technology, 21st Floor, Mita Kokusai Bldg., 4-28, Mita 1-chome,
Minato-ku, Tokyo 108, Japan, fax [phone]. See also PTF.

   PTF:
The Prime Time Freeware CD-ROM series contains various items mentioned
in this FAQ including Mark Kantrowitz's AI Repository, some ICOT
material, BERTRAND, GARNET, and LIFE. Prime Time Freeware for UNIX
sells for $60 US, list, and is issued twice each year. E-mail
<[e-mail]> for more details.

   University of Washington (Seattle):
Constraint-related papers and solvers/implementations including
ThingLabII, CoolDraw (a constraint-based drawing system), and the
DeltaBlue and SkyBlue algorithms. All public domain. Contact Alan
Borning <[e-mail]> for details.
ftp.cs.washington.edu:/pub/constraints or, on WWW,
http://www.cs.washington.edu/research/projects/weird/www/constraints.html

  WWW sites:
http://web.cs.city.ac.uk/archive/constraints/constraints.html
http://ps-www.dfki.uni-sb.de/
http://www.ecrc.de/
http://www.cis.upenn.edu/~screamer-tools/home.html/
http://www.sics.se/ccp/ccp.html/
http://www.cs.washington.edu/research/projects/weird/www/constraints.html

----------------------------------------------------------------
Subject: [1-6] Books and Journal Articles

This is not intended to be a complete bibliography. See ftp sites above
for the location of longer bibliographies. Please suggest additions etc.

F. Benhamou and A. Colmerauer, eds. "Constraint Logic Programming:
Selected Research" MIT Press, 1993.

J. Cohen, "Constraint Logic Programming Languages",
Communications of the ACM 33(7):52-68, 1992. [Good introduction to CLP
and includes a historical overview.]

B. Freeman-Benson, J. Maloney, and A. Borning, "An Incremental
Constraint Solver", Communications of the ACM 33(1):54-63, 1990.
[Includes a good reading list on the history and applications of
constraints.]

E. Freuder, "Synthesizing Constraint Expressions",
Communications of the ACM 21(11):24-32, 1978.

T. Fruehwirth et al, "Constraint Logic Programming: An Informal
Introduction", in Logic Programming in Action, 1992, Springer-Verlag,
LNCS 636, (Also available as Technical Report ECRC-93-5. ECRC tech
reports are available from ftp.ecrc.de:/pub/ECRC_tech_reports)

J. Jaffar and J-L. Lassez, "Constraint Logic Programming", in
Proceedings of the 14th ACM Symposium on Principles of Programming
Languages (POPL), Munich, pp. 111-119, 1987.

J. Jaffar and M. Maher, "Constraint Logic Programming: A
Survey", Journal of Logic Programming, 1994, (To appear).

V. Kumar, "Algorithms for Constraint-Satisfaction Problems: A Survey",
AI Magazine 13(1):32-44, 1992.

E. Lawler, J. Lenstra, A. Rinnooy Kan and D. Shmoys,
"The Traveling Salesman Problem", Wiley, 1985/1992.

W. Leler, "Constraint Programming Languages", Addison-Wesley, 1988,
0-201-06243-7. (See entry on `BERTRAND' in section [2-1] of part2 of
this FAQ.)

A. Mackworth, "Consistency in Networks of Relations", Artificial
Intelligence 8(1):99-118, 1977.

P. Meseguer, "Constraint Satisfaction Problems: An Overview", AICOM
2(1):3-17, 1989.

U. Montanari, "Networks of Constraints: Fundamental Properties and
Applications to Picture Processing", Information Science 7(2):95-132,
1974.

G. Nemhasuer, A. Rinnooy Kan, M. Todd, "Optimization",
North-Holland, 1989.

J. Pearl, "Heuristics: Intelligent Search Strategies for Computer
Problem Solving", 1984, Addison-Wesley, 0-201-05594-5.

V. Saraswat, "Concurrent Constraint Programming", MIT Press, 1993.

G. Steele, "The Definition and Implementation of A Computer
Programming Language Based on Constraints", PhD thesis, MIT, 1980.

E. Tsang, "Foundations of Constraint Satisfaction", Academic Press, 1993.
ISBN 0-12-701610-4.

P. Van Hentenryck, "Constraint Logic Programming",
Knowledge Engineering Review, 6(3):151-194, September 1991.

P. Van Hentenryck, "Constraint Satisfaction in Logic Programming",
MIT Press, Cambridge, MA, 1989, ISBN 0-262-08181-4.

[See also the articles on Constraint Networks (pages 276-285) and
Constraint Satisfaction (pages 285-293) in Shapiro's Encyclopedia
of Artificial Intelligence.]

The Journal "Artificial Intelligence" has articles on the Constraint
Satisfaction Problem (CSP), as do other AI journals. Magazines related
to Prolog will have articles on Constraint Logic programming (CLP).

 AI Communications (4 issues/yr)
 "The European Journal on Artificial Intelligence" ISSN 0921-7126,
 European Coordinating Committee for Artificial Intelligence.

 AI Expert (issued monthly) ISSN 0888-3785, Miller Freeman Publishers
 On CompuServe: GO AIEXPERT. Reviews Prolog-related products.

 Expert Systems (4 issues/yr) ISSN 0266-4720,
 Learned Information (Europe) Ltd.

 IEEE Expert (issued bimonthly) ISSN 0885-9000, IEEE Computer Society

 The Journal of Logic Programming (issued bimonthly), (North-Holland),
 Elsevier Publishing Company, ISSN 0743-1066

 New Generation Computing, Springer-Verlag. (Prolog-related articles)

----------------------------------------------------------------
Subject: [1-7] Reviews and Surveys of Constraint Systems

The WWW address http://www.aiai.ed.ac.uk/~timd/constraints/csptools.html
contains an Overview of CSP tools, including CHIP, CHARME, and ILOG
SOLVER by Tim Duncan.

----------------------------------------------------------------
Subject: [1-8] Complexity of Constraint Satisfaction
        (including Phase Transition)

Standard papers on this area include:

Alan Mackworth and Eugene Freuder, "The Complexity of Some
Polynomial Network Consistency Algorithms for Constraint Satisfaction
Problems", in Artificial Intelligence, 1985, 25:65-73

Alan Mackworth and Eugene Freuder, "The Complexity of Constraint
Satisfaction Revisited", in Artificial Intelligence, February 1993, 59
(1-2): 57-62,

Also Tsang's book as mentioned previously.


Phase Transitions in Constraint Satisfaction Problems
-----------------------------------------------------

The search difficulty of constraint satisfaction problems can be
determined, on average, from knowledge of easily computed structural
properties of the problems. In fact, hard problem instances are
concentrated near an abrupt transition between under- and over-
constrained problems. This transition is analogous to phase transitions
in physical systems and offers a way to estimate the likely difficulty
of a constraint problem before attempting to solve it with search.

For more information and pointers to related work, see the web page:
ftp://parcftp.xerox.com/pub/dynamics/constraints.html

Information kindly supplied by Tad Hogg <[e-mail]>.

----------------------------------------------------------------
Subject: [1-9] Benchmarks for Constraint Satisfaction Problems

Some benchmarks are available from the same ftp archive and WWW page
as this FAQ: ftp.cs.city.ac.uk:/pub/constraints/csp-benchmarks
including a Radio Link Frequency Assignment Problem

----------------------------------------------------------------
Subject: [1-10] Constraints for Natural Language Processing

[This entry reprinted by kind permission of the author: Philippe
Blache <[e-mail]>, University of Nice-Sophia Antipolis]

Current linguistics theories often describe syntactic relations as
constraints on linguistic structures. It is in particular the case of
unification-based theories. But linguistic constraints are generally
far from the CLP ones and the question remains: is NLP a constraint
satisfaction problem ? [[MBJ adds an editorial note: Micha Meier
<[e-mail]> feels that NLP _is_ a typical CSP.]]

It is still difficult to say what could be the actual advantages of a
CLP approach for natural language processing in general. But if we
don't have a global answer, several works propose CLP representation of
particular problems such as linear precedence (cf Patrick Saint-
Dizier), disjunctive values (cf Franz Guenthner), subcategorization,
etc ... I'm currently working on the interpretation of HPSG's
principles with boolean constraints. The problem in this case comes
from the fact that the instantiation principles of this theory can be
seen as constraints on feature structures, but using actual active
constraints need a very rigid (and heavy) representation of these
structures. A compromise between a pure CLP and a pure linguistic
approach is still inevitable.

I would be deeply interested in other approaches to this problem.

Franz Guenthner (1988) "Features and Values 1988"
    CIS-BERICHT-90-2, Univerity of Munich

Patrick Saint-Dizier (1994) Advanced Logic Programming for Natural Language
    Processing, Academic Press, London

Philippe Blache (1992) "Using Active Constraints to Parse GPSGs"
    in proceedings of COLING'92

----------------------------------------------------------------
Subject: [1-11] N-Ary CSPs (N > 2)

[This entry reprinted by kind permission of the author: Sunil
Mohan <[e-mail]>, Rutgers University]

N-ary CSPs have constraints with arbitrary arity, including some with
arity > 2. There are some problems with solving CSPs that appear only
when encountering constraints with higher arities. Constraints with
maximum arity are also called global constraints.

Selecting a suitable Variable-Constraint Ordering (Control Sequence)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Some of the popular variable ordering heuristics for generating a
"good" control sequence fail on N-ary CSPs:

- Ordering based on variable domain size. Many such heuristics fail
because of their very localized view of the problem. Consider the CSP:
    {<x1..x5> | T1(x1 x2) T2(x1 x2 x3) T3(x4 x5)}
After first selecting (x1 x2 T1), a variable-domain-size based
heuristic could proceed to pick x4 as the next variable to bind, when
x3 could have been a better choice because it allows T3 to be tested.
Or, in Forward-Check, (x1 T1 x2 T3..) is probably a better choice than
(x1 T1 x4 T5 x2 T3..), but this heuristic does not have a way of
recognizing the presence of higher-arity constraints.

This is not a problem with Binary CSPs, particularly in FwdChk, because
after binding each variable, a binary constraint on that variable can
be tested.

- Ordering based on variable connectivity. In a CSP with a global
constraint, every variable is connected to n-1 other variables. The
same happens with heuristics based on minimizing Constraint Bandwidth
[Ramin Zabih, 8th NCAI 1990].


Some Ordering Heuristics for N-ary CSPs
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
I have experimented with the following ordering heuristics:
 - Minimizing Constraint Bandwidth Sum
 - Minimizing Constraint Depth Sum
    (Constr Depth is distance of constr from beginning of sequence)
 - Ordering variables based on nbr of constraints on it.

In general, to generate a good control sequence for N-ary CSPs, a
global view of the problem is needed. Binding a variable that allows a
(n-ary) constraint that already has the rest of its argument variables
bound, should get higher priority than another variable, all other
things being equal. Sometimes it is better to view the problem as one
of ordering constraints rather than variables.

I like to think of testing constraints as early as possible in the
search tree. Hence the Constraint BandWidth Sum and Depth Sum
heuristics. Of course, variable domain size is also a factor.

Decomposing the CSP
~~~~~~~~~~~~~~~~~~~
Freuder [JACM, Jan 1981] showed that tree-shaped CSPs can be solved
(find first solution) without backtracking after some consistency
processing. Consequently some techniques have been developed to get
non-tree problems into that form. Some techniques decompose a CSP into
variable clusters such that the shape of the constraint network on
these clusters is tree shaped [Dechter & Pearl, AIJ 1989; Gyssens,
Jeavons, Cohen, 1992; etc.]. Each variable cluster includes some
cluster-local constraints. The complexity of the problem is reduced to
the complexity of the largest cluster. With a global constraint in the
CSP, this kind of decomposition is not possible. Cycle-cutset based
techniques stumble in the same way.

----------------------------------------------------------------
Subject: [1-12] Constraint Libraries for C Programs

Peter Van Beek <[e-mail]> has written a set of libraries
for C, implementing various standard algorithms as discussed by Prosser
and others. This package is available from ftp.cs.ualberta.ca:/pub/ai/csp
where you will find a README and also csplib.tar.Z. Also available from
the archive site for this FAQ (see section [1-1]).

----------------------------------------------------------------
Subject: [1-13] Constraints and Rule-Based (Production) Systems

Milind Tambe <[e-mail]> writes: Many researchers have explored
the possible integration of constraint satisfaction techniques/methods
and production (rule-based) systems. The integration has been explored
in the context of both backward chaining[1] and forward-chaining
systems (see below).

This short note focuses on one aspect of this integration: constraints
and forward-chaining production systems. These forward chaining systems
execute tasks by going through recognize-act cycles: in the recognize
or match phase, productions or rules match with working memory (a
database of facts) and in the act phase, the matched productions are
fired, causing changes to working memory, in turn causing the system to
execute the next recognize act cycle. Integration of constraints with
such systems is possible at multiple levels. At a higher level, the
integration with constraints may involve a shift in the recognize-act
cycle. For instance, constraint-satisfaction techniques may be used in
addition to the recognize-act cycle to define values in working
memory[2]. At this higher level, constraints do not change the
recognize-act cycle itself. At a lower level, however, the integration
with constraints may involve a change in the recognition procedure,
i.e., the procedure used to match productions with working memory. More
specifically, the problem of matching conditions of productions with
working memory can be mapped over onto constraint satisfaction
problems. Techniques such as arc-consistency, path-consistency or
others may then be used either to reduce the match cost of productions
by quickly eliminating easily detectably inconsistencies, or
alternatively even to substitute for the matching procedure[3].

1. "Concurrent constraint programming languages", V. Saraswat, PhD
Thesis, 1989, School of Computer Science, Carnegie Mellon University,
Pittsburgh, PA.

2. "Constrained heuristic search" M. Fox, N. Zadeh & C. Baykan,
IJCAI-89, pp 309-315.

3. "Investigation production system representations for non-
combinatorial match" M. Tambe & P. Rosenbloom, Artificial Intel.,
Volume 68, Number 2, 1994.

----------------------------------------------------------------
Subject: [1-14] Interval Constraints and Newton's Approximation

Michael Jampel asked: Would anyone like to comment on the integration
of Newton's approximation method with interval constraint solvers?

Pascal Van Hentenryck <[e-mail]> replied: You may want to look
at our recent technical report CS-94-18:
 CLP(Intervals) Revisited
 F. Benhamou, D. McAllester, and P. Van Hentenryck
which describes precisely a smooth integration of Newton method into a
CLP(Intervals) language. The language, called Newton, was applied to
some traditional benchmarks in this area and compared with specific
tools. You may get a copy of the report by anonymous ftp from
wilma.cs.brown        b/techreports/94/cs94-18.ps.Z

----------------------------------------------------------------
Subject: [1-15] Dynamic CSPs (Constraint Satisfaction Problems)

Thomas Schiex <[e-mail]> writes: A definition: A dynamic
constraint satisfaction problem P is a sequence P_0 ... P_alpha of
static CSPs each one resulting from a change in the preceding one [1].
This change may be a _restriction_ (a new constraint is imposed on a
subset of variables) or a _relaxation_ (a constraint is removed from
the CSP).

[2] and [3] contain many references to other papers in the field.

[1] Rina Dechter and Avi Dechter, ``Belief Maintenance in Dynamic
Constraint Networks'', Proceedings AAAI, 1988, pp 37-42.

[2] Gerard Verfaillie and Thomas Schiex, ``Solution reuse in dynamic
CSPS'', Proceedings AAAI, August 1994.

[3] Christian Bessiere, ``Arc-Consistency in Dynamic CSPs'',
Proceedings AAAI, 1991, pp 221-226.

----------------------------------------------------------------
Subject: [1-16] Glossary: definitions of some terms

Thanks to Patrick Prosser, Thomas Schiex, Berthe Choueiry, Alan Borning,
Warwick Harvey, Thom Fruehwirth. Please inform me of additions.

AC    Arc-Consistency: a method for reducing the amount of
    back-tracking in CSPs
AC-n    Different algorithms for enforcing arc consistency: AC-3, AC-4
    (Mackworth), AC-5 (van Hentenryck), AC-6+, AC6++ (Bessiere and
    Regin), AC-7 (Freuder). Also Hierarchical AC: HAC (Mackworth)
    and HAC-6 (Kokeny)
AKL    Agent Kernel Language: object-oriented concurrent constraints
    (previously called Andorra Kernel Language)
AND-    AND-PARALLEL means doing all the atomic goals in one clause (or
    query) of a logic program in parallel (all the nodes of one
    branch of the search tree). OR-PARALLEL means doing all the
    clauses in parallel (all the branches of the search tree).
ATMS    Assumption-Based Truth-Maintenance System
BJ    Backjumping (*)
BM    Backmarking (*)
BMJ    Backmarking with backjumping (*)
CBJ    Conflict-Directed Back-Jumping (*)
DB    Dynamic Backtracking (*)
CC(FD)    Concurrent Constraint Programming over Finite Domains
CCP    Concurrent Constraint Programming
CHR    Constraint Handling Rules (Fruehwirth)
CIP    Constraint Imperative Programming
CLP    Constraint Logic Programming
CLP(FD)    Constraint Logic Programming over finite domains
CLP(R)    Constraint Logic Programming over the domain of Real numbers
CLP(X)    Constraint Logic Programming over some domain X
COP    Constrained Optimization Problem
CSP    Constraint Satisfaction Problem
DBT    Dynamic backtracking
DCSP    Dynamic CSP
DnAC    Dynamic arc-consistency
DVO    Dynamic Variable Ordering heuristic (*)
FC    Forward-checking (*)
FF    First Fail principle: choose the variable with the
    smallest domain as the next instantiation (*)
FLA    Full Look Ahead
FOF    Factor Out Failure
FSL    Full Shallow learning (*)
GBJ    Graph based Backjumping (*)
GSAT    Selman's GSAT
HAC    Hierarchical Arc Consistency. See AC-n.
HCLP    Hierarchical CLP
IB    Intelligent Backtracking (*)
IDA*    Iterative Deepening A*
ILP    Integer Linear Programming
IP    Integer Programming
LC    Local changes
LP    Logic Programming or Linear Programming
MAC    Maintaining Arc-Consistency
NC    Node consistency (see AC). Not much used
NLP    Non-Linear Programming. (Natural Language Processing elsewhere)
NR    Nogood recording (*)
OR    Operations Research. see newsgroup sci.op-research
OR-    See AND-
PC    Path-Consistency. Not much used
PCSP    Partial CSP
PLA    Partial Look Ahead
RFLA    Real Full Look Ahead
SAT    The problem of deciding if a given logical formula is
    SATisfiable.
TMS    Truth-Maintenance System
TSP    Travelling Salesman Problem; a typical very hard problem

(*)    All these are different techniques/heuristics for improving the
    efficiency of constraint satisfaction

----------------------------------------------------------------
Subject: [1-17] Explanation of value ordering heuristics

> Can someone tell me what is the definition of VALUE ORDERING
> and what is its purpose, and are there any rules  to follow
> when doing value ordering or is it domain dependent?

In Constraint Satisfaction Problems, once you have decided which
_variable_ to instantiate next, say V, if V has more than one possible
value, you might ask which _value_ to choose first.

The simplest is to go systematically through the domain of V from
smallest to largest. But if V has domain [1,2,...10] and (by some
magic) you know that some/all the solutions to your CSP have V=10, then
it would be nice if you could try V=10 first, before wasting a lot of
work on 1,2,...

One well-known heuristic is to choose that value for V which is
consistent with the _greatest_ number of the constraints on V. If V is
only involved in constraints with X, and the possible values for (V,X)
are (1,2), (1,3), (2,3), then you should choose V=1 before trying V=2.

Unfortunately, it is quite expensive to keep on checking which is the
most popular value in this sense. (And there is no point doing it if
you want all solutions, as you will have to try V=1 and V=2 anyway.) It
is so expensive that it is usually not worth doing.

Of course, if you have problem-specific knowledge it might suggest a
different heuristic, which might be good in your particular circumstances.

In contrast, the first-fail heuristic for choosing which _variable_ to
instantiate next by choosing the one with smallest domain size, is (a)
very cheap (b) often gives good benefits.

----------------------------------------------------------------
Subject: [1-18] Explanation of constraint entailment

> Could anybody give me the definition of constraint entailment?

If we already have `X = 8' in the constraint store, we can ask three
questions about some other constraint C:

a) Is C entailed by the store?
    If C is, say, `X > 5' then the answer is `yes' -- X > 5 does
    not give you any extra information if you already know that
    X = 8.
b) Is the negation of C entailed by the store? (Is C `disentailed')
        If C is `X > 5' the answer is `no', but if C was, say, X < 2,
        it would be false in the context provided by the store
c) Is C neither entailed nor disentailed?
        The constraint `Y = 4' is consistent with the store, and so is
        its negation, but it is not entailed by it.

In the language of Concurrent Constraints, we can `ask' if a constraint
is entailed, and get `yes', `no' or `suspend' (i.e. the ask goes to
sleep until enough extra information is added to the store to give a
definite answer). If we want to add information to the store, we can do
a `tell' which only works if the constraint to be told is not
inconsistent with the store.

----------------------------------------------------------------
Subject: [1-19] Explanation of Don't Know / Don't Care nondeterminism

> Could anybody give me the definitions of committed choice, don't
> know, and don't care nondeterminism, please?

Don't know/don't care nondeterminism:
If I say to a class of students ``Write all your names on this piece of
paper'' then I know that I want ALL the names, but I don't KNOW which
ORDER they will be written in.

If I say to a class of students ``One of you must clean the board
before the lesson'' then I only want ONE of them to do it, and I don't
CARE who.

Or, in an operating system, when I save a file in the editor, I don't
care which particular block of the disk the file is written on.  But
once the OS has started writing the file to one block, I don't want it
to change its mind half-way through -- I want it to COMMIT to the
CHOICE it has made.

So don't know nondeterminism is what you get from Prolog's search rule
whereas don't care nondeterminism (sometimes called `indeterminism') is
what you would expect from an OS, or from ``Committed choice parallel
logic languages'' such as Parlog or FGHC. Committed choice is linked to
the idea of a `guard' or `commit' operator which is like the `cut' in
Prolog (but imagine having to have a cut at the begining of every
clause, so once you have selected it, you are committed to it and there
is no back-tracking).

Committed-choice and don't care --> you lose the link between
declarative (model-theoretic) and operational semantics which is one of
the nice things about Prolog.

----------------------------------------------------------------
;;; *EOF*

Archive-name: constraints-faq/part2
Last-Modified: Thu Feb  2 14:45:00 1995 by Michael Jampel
Version: 2.12

Important Changes (since last posting): Oz new release. Something
deleted (I could tell you what, but then I'd have to kill you :-)
`Topic' changed to `Subject'

Contributions and corrections should be sent to Michael Jampel
<[e-mail]>.

This is a list of Frequently Asked       ons (and answers) for the area
of constraints, including books, journal articles, ftp archives, and
systems & products. It is posted once a month to the newsgroups
comp.constraints, comp.answers, and news.answers.

NOTE: the WWW page associated with this FAQ now contains far more
information than the FAQ does, including meta-information, i.e. pointers
to other WWW pages and ftp sites. I strongly suggest you have a look at it:
    http://web.cs.city.ac.uk/archive/constraints/constraints.html

People who helped with this FAQ include Philippe Blache
<[e-mail]>, Mark Kantrowitz <[e-mail]>, Wm Leler
<[e-mail]>, Manfred Meyer <[e-mail]>, Milind Tambe
<[e-mail]>, Thomas Schiex <[e-mail]>, and Tad Hogg
<[e-mail]>.

Thanks to Mark Kantrowitz for allowing me to use large parts of his
FAQs and Resource Guides for comp.lang.prolog and comp.ai.

----------------------------------------------------------------
Table of Contents:
In this part of the FAQ:
 [2-1]  Introduction (same as in part 1)
 [2-2]  Free and Commercial Constraint Systems

In the other (first) part of this FAQ there are definitions, glossaries,
explanations, a short bibliography, pointers to FTP and WWW archives and
other resources, reviews and surveys of constraint systems, and
basically everything else which is not in this part.

Search for [#] to get to topic number # quickly. In newsreaders which
support digests (such as rn), [CTRL]-G will page through the answers.

----------------------------------------------------------------
Subject: [2-1] Introduction

This guide lists constraint-related resources: compilers and
interpreters (in this part), archives, newsgroups, books, magazines,
and anything else you can think of (all in part 1). Also included is a
list of suppliers of products and a list of publishers.

This guide is regularly posted in two parts to comp.constraints,
usually on the 17th or 18th of each month.

It may also be obtained by anonymous ftp from City University:
    ftp.cs.city.ac.uk [138.40.91.9],
 using username "anonymous" and password "name@host".
 The files part1 and part2 are located in the directory
    pub/constraints/constraints-faq/
 [The ftp site will also contain other items on constraints.]

WWW (World Wide Web) address:
    http://web.cs.city.ac.uk/archive/constraints/constraints.html
This is also a jumping-off point giving access to most of the ftp sites
mentioned in section [1-5].

The articles posted to the newsgroup are archived by month in the same
location as this FAQ, in subdirectory
ftp.cs.city.ac.uk:/pub/constraints/archive/comp.constraints

The FAQ postings are also archived in the periodic posting archive on
rtfm.mit.edu. Look in the anonymous ftp directory
/pub/usenet/news.answers/constraints-faq in the files part1 and part2.
If you do not have anonymous ftp access, you can access the archive by
mail server as well. Send an E-mail message to [e-mail]
with "help" and "index" in the body on separate lines for more
information.

FAQs and Resource Guides for other newsgroups will usually be available
on rtfm.mit.edu too.

Disclaimer: We are not responsible for anything at all. Ever. So there.

Copyright Michael Jampel 1994. Permission to do reasonable things
not for profit is given to anyone. Anything else, ask me.

----------------------------------------------------------------
Subject: [2-2] Free and Commercial Constraint Systems

See the comp.lang.prolog, comp.lang.lisp, comp.ai and comp.lang.scheme
FAQs and Resource Guides for possibly more up-to-date and complete
information.

Note on costs: there is a difference between FREE software (which may
have restrictions attached), Public Domain software (FREE-PD), CHEAP
software (arbitrarily and approximately: less than 100 pounds or 200
dollars or 300 deutschmarks), shareware (CHEAP-SH), and software which
is COMMERCIAL [to avoid calling it non-cheap or expensive]. Some
software may not be available for commercial use, although commercial
enterprises may be able to use it for their own research. These are
labelled C=N/A. Costs may also vary depending on whether the customer
is (A) academic, (E) Eastern European, or (C) a commercial enterprise.
So each section here will have a header of the following form:
[COST A=CHEAP,E=FREE,C=PRICE]. If something has the same cost for all
groups, I abbreviate the entry to e.g. [COST FREE-PD].

Warning: there is no guarantee that this information is correct and it
should not be treated as implying some kind of contract either on my
part (FAQ maintainer) or on the part of the supplier. Please notify me
of errors.

   AKL:                    [COST A=E=FREE,C=N/A]
AKL (previously Andorra Kernel Language, now Agent Kernel Language) is
a concurrent constraint programming language that supports both
Prolog-style programming and committed choice programming. Its control
of don't-know nondeterminism is based on the Andorra model, which has
been generalised to also deal with nondeterminism encapsulated in
guards and aggregates (such as bagof) in a concurrent setting. See, for
example,

 Sverker Janson and Seif Haridi, "Programming Paradigms of the Andorra
 Kernel Language", in Proceedings of ILPS'91. MIT Press, 1991.

 Torkel Franzen, "Logical Aspects of the Andorra Kernel Language", SICS
 Research Report R91:12, Swedish Institute of Computer Science, 1991.

 Torkel Franzen, Seif Haridi, and Sverker Janson, "An Overview of the
 Andorra Kernel Language", In LNAI (LNCS) 596, Springer-Verlag, 1992.

 Sverker Janson, Johan Montelius, and Seif Haridi, "Ports for Objects
 in Concurrent Logic Programs", in Research Directions in Concurrent
 Object-Oriented Programming, MIT Press, 1993 (forthcoming).

The above papers on AKL are available by ftp from
sics.se:/pub/ccp/papers.
An (as yet non-released) prototype implementation of AKL is available
for research purposes (contact [e-mail]).

   ALE:                    [COST FREE-PD]
ALE (Attribute Logic Engine), a public domain system written in
Prolog, integrates phrase structure parsing and constraint logic
programming with typed feature structures as terms. Types are arranged
in an inheritance hierarchy and specified for the features and value
types for which they are appropriate. Grammars may also interleave
unification steps with logic program goal calls (as can be done in
DCGs), thus allowing parsing to be interleaved with other system
components. While ALE was developed to handle HPSG grammars, it can
also execute PATR-II grammars, DCG grammars, Prolog, Prolog-II, and
LOGIN programs, etc. Grammars and programs are specified with a version
of Rounds-Kasper Attribute Value Logic with macros and variables. ALE
supports lexical rules and empty categories for grammars, using a
bottom-up, breadth-first dynamic chart parser. ALE supports last call
optimization, negation by failure and cuts in definite clauses, which
may be used independently or integrated into grammars. The system is
available free for research purposes, from Bob Carpenter
<[e-mail]>.

   BERTRAND:                [COST CHEAP-SH]
Bertrand is the language described by Leler in his book (see section
[1-6]). See [1-5] PTF for more details.

   BULL SOLVER:                [COST COMMERCIAL]
See ILOG SOLVER.

   CFSQP:                [COST A=E=FREE,C=FREEish]
See FSQP.

   CHARME:                [COST COMMERCIAL]
CHARME was a commercial product from Bull. The latest version is called
BULL SOLVER, but see also ILOG SOLVER.

   CHIP:                [COST COMMERCIAL]
CHIP V4 (Constraint Handling In Prolog) is designed as an extension to
Prolog offering three constraint solving domains: Integers, Rationals
and Booleans. The system was originally developed at ECRC in Munich and
now extended by the same team at COSYTEC in Paris. CHIP V4 includes
extensions to the three domains: symbolic constraints, update demons
and cumulative constraints. The system is available with optional
interfaces for X11 and DOS graphics (XGIP), Oracle or Ingres database
connection (QUIC), C language interface (CLIC) and embedded application
interface (EMC). CHIP V4 is written completely in C, and is available
on a range of workstations including SunSparc IBM RS6000, HP 9000/700,
Decstations and PC386/486 (Dos 5.0). An academic discount is offered
for educational and research purposes. For more information contact
COSYTEC, Parc Club Orsay Universite 4 rue Jean Rostand, 91893 Orsay
Cedex, France, phone [phone], fax [phone] or email
<[e-mail]>.

   CHR:                    [COST FREE with ECLIPSE]
Constraint Handling Rules (CHRs) is a library of ECLiPSe [see separate
entry] for writing custom constraint systems in a high-level language.
CHRs is essentially a committed-choice language consisting of guarded
rules that rewrite constraints into simpler ones until they are
solved. The usual formalisms to describe a constraint theory, i.e.
inference rules, rewrite rules, sequents, first-order axioms, can be
expressed as CHR programs in a straightforward way. The CHR release
includes a full colour demo involving geometric constraints, a compiler
(into ECLiPSe), two debuggers, a runtime system and 18 constraint
solvers. There are solvers for lists, sets, trees, terms, finite and
infinite domains, booleans, linear polynomials over reals and
rationals, for incremental path consistency, and for terminological and
temporal reasoning. CHR documentation is available by anonymous ftp
from ftp.ecrc.de:/pub/eclipse/doc in the extensions-manual. You can
also ftp a technical report describing constraint handling rules (file
ECRC-92-18.ps.Z in directory pub/ECRC_tech_reports/reports) and their
application to temporal and terminological reasoning (files
ECRC-94-05.ps.Z and ECRC-94-06.ps.Z). For more information on CHRs
contact Thom Fruehwirth ([e-mail]).

   CIAL 1.0 (Beta)            [COST FREE]
CIAL is an interval constraint logic programming language. The main
difference between CIAL and other CLP(Interval) languages is that a
linear constraint solver, which is based on preconditioned interval
Gauss-Seidel method, is embedded in CIAL in addition to the interval
narrowing solver. The main motivations for a linear solver are:
* Pure interval narrowing fails to narrow the intervals to any useful
  width even for such simple systems as {X+Y=5, X-Y=6}. Interval
  splitting may help but is costly.
* Pure interval narrowing cannot always detect inconsistency or halt
  (in a reasonable time). A simple example is {A+1=D, A+B=D, A>0, B<0}.
* Efficient linear constraint solver is also important to the study of
  efficient non-linear constraint-solving. Recent results show that
  interval Newton method works better than pure interval narrowing for
  solving non-linear constraints, but may require to solve many linear
  constraints in order to give the best results.
This version of CIAL prototype is implemented as an extension to CLP(R)
v1.2 and tested on Sun Sparc machines. You should have obtained CLP(R)
from IBM prior to installing CIAL. Our distribution is in the form of
patches to the CLP(R) sources. [See entry on CLP(R) below].

E-mail [e-mail] to request CIAL, and for more details.

[FAQ maintainer's note: I have deleted most of the references provided,
for space reasons, if they are in well-known journals and conferences;
the CIAL team have not simply cited only their own work. MBJ.]

C.K. Chiu and J.H.M. Lee. Towards practical interval constraint solving
in logic programming. (To appear) In Proceedings of the Eleventh
International Logic Programming Symposium, Ithaca, USA, Nov.1994.

J.H.M. Lee and T.W. Lee. A WAM-based abstract machine for interval
constraint logic programming and the multiple-trailing problem.
Proceedings Sixth IEEE International Conference on Tools with
Artificial Intelligence, New Orleans, Nov 1994.


   CLP(BNR):                [COST ???]
CLP(BNR) [Constraint Logic Programming with Booleans Naturals and
Reals] is an experimental CLP Language developed at the Bell-Northern
Research Computing Research Lab. CLP(BNR) is a Prolog-based language
that incorporates an arc-consistency propagation algorithm on
interval-bounded constraints which handles general algebraic
constraints over continuous, integer and boolean variables. This allows
programmers to express systems of non-linear equations on real
intervals that can be arbitrarily mixed with integer and boolean
constraints equations. For more information on CLP(BNR) contact
Andre' Vellino <[e-mail]> [phone], fax [phone]
Bell-Northern Research, Box 3511, Station C, Ottawa, CANADA K1Y 4H7
See also section [1-6] for papers by Benhamou/ Older/ Vellino.

   CLP(FD):                [COST FREE]
CLP(FD) 2.2 is a constraint logic programming language over Finite
Domains. It is based on the wamcc Prolog compiler which translates
Prolog to C. It provides several constraints "a la CHIP" on Finite
Domains and Booleans and some facilities to build new constraints.
clp(FD) is 4 times faster than CHIP v3.2 on average.  Available from
 ftp.inria.fr:/INRIA/Projects/ChLoE/LOGIC_PROGRAMMING/clp_fd
Requires GNU C (gcc) version 2.4.5 or higher. Ported to Sparc
workstations, PC under linux, sony mews, dec ultrix, portable generally
to 32-bit machines with gcc. See also under WAMCC, below. For more
details, contact the author Daniel Diaz <[e-mail]> INRIA
Rocquencourt, FRANCE.

   CLP(R):                [COST A=FREE,E=FREE,C=N/A]
                    [Commercial users: see next section]
CLP(R) is a constraint logic programming language with real-arithmetic
constraints. The implementation contains a built-in constraint solver
which deals with linear arithmetic and contains a mechanism for
delaying nonlinear constraints until they become linear. Since CLP(R)
subsumes PROLOG, the system is also usable as a general-purpose logic
programming language. It includes facilities for meta-programming with
constraints. The system consists of a compiler, byte-code emulator,
and constraint solver. CLP(R) is written entirely in C and runs on
Suns, Vaxen, MIPS-based machines (Decstations, Silicon Graphics), IBM
RS6000s and PS2s. Includes MS-DOS support. It is available free from
IBM for academic and research purposes only. For more information,
write to Joxan Jaffar, H1-D48, IBM Thomas J. Watson Research Center,
P.O. Box 704, Yorktown Heights, NY 10598, or send email to
[e-mail] or [e-mail]. Current version 1.2.

   CLP(R):                [COST CHEAP]
CLP(R) is a constraint system from Monash University for VAX, Sun, and
Pyramid (Unix). Costs $150. For more information, write to Monash
University, CLP(R) Distribution, Department of Computer Science,
Clayton, Victoria 3168, Australia, or send email to
[e-mail]. [Although the system is still available, it has
not been maintained or supported for about 5 years, and it will remain
that way.]

   COOLDRAW:                [COST FREE-PD]
A constraint-based drawing package from the same stable as ThingLabII.
See information on the Seattle ftp site in section [1-5].

   CONTAX:                [COST FREE-PD]
Public domain constraint system written by Manfred Meyer
<[e-mail]>. [More details soon.]

   CU-PROLOG:                [COST FREE]
cu-Prolog is an experimental constraint logic programming language
available free from Japan's Institute for New Generation Computer
Technology (ICOT). Unlike most conventional CLP systems, cu-Prolog
allows user-defined predicates as constraints and is suitable for
implementing a natural language processing system based on the
unification-based grammar. For example, the cu-Prolog developers
implemented a JPSG (Japanese Phrase Structure Grammar) parser in
cu-Prolog with the JPSG Working Group (the chairman is Prof. GUNJI,
Takao of Osaka University) at ICOT. cu-Prolog is a complete
implementation of Constraint Unification (cu), hence the name.
cu-Prolog is implemented in C for BSD UNIX 4.2/3. Professor Sirai of
Chukyo-University has also implemented cu-Prolog for the Apple
Macintosh and DJ's GPP (80386/486 MS-DOS machine with the DOS
extender). Available free by anonymous ftp: see section [1-5].

   DELTABLUE:                [COST FREE-PD]
A constraint-solving algorithm. See information on the Seattle ftp site
in section [1-5]. See paper by Freeman-Benson et al in section [1-6].

   ECLIPSE:                [COST A=CHEAP,E=FREE,C=see below]
ECLiPSe (ECRC Logic Programming System) combines the functionalities of
several ECRC systems, including Sepia, MegaLog and CHIP. ECLiPSe
includes a Prolog compiler with extended functionality that is Quintus
and SICStus compatible, a tightly connected database system based on
the BANG file system, a CLP system, and an interface to the Tcl/Tk X11
toolkit. The BANG database can store not only relations, but also any
Prolog structures and programs. The CLP system contains several
libraries with various types of constraint handling schemes, including
atomic finite domains, linear rational constraints, CHR (constraint
handling rules) and Propia (generalised propagation). See also the
separate entry for CHR.] It also supports writing further extensions
like new user-defined constraints or complete new constraint solvers.
ECLiPSe also includes a profiler, user-definable syntax, metaterms as
first-class citizens, coroutining, and unlimited precision integer and
rational numbers. ECLiPSe is available for a nominal fee of DM 300
(~$200) to all academic and government-sponsored organizations.
Commercial users may obtain ECliPSe for DM 7000, but for research
purposes only. It is distributed in binary form for Sun-3, Sparc, and
many other types of machine. Send orders or requests for further
information to [e-mail] or write to ECRC,
Arabellastrasse 17, 81925 Munich, Germany. The ECLiPSe documentation
(ASCII and dvi) and some shareware packages ported to ECliPSe are now
available by anonymous ftp from ecrc.de:/pub/eclipse. To subscribe to
the [e-mail] mailing list, send mail to
[e-mail].

   ECRC SEPIA:                [COST FREE with ECLIPSE]
See ECLIPSE. SEPIA is no longer delivered as a stand-alone system, but
as a part of ECLiPSe.

   FSQP/CFSQP:                [COST A=E=FREE,C=FREEish]
FSQP (Feasible SQP; FORTRAN; developed by J.L. Zhou and A.L. Tits) and
CFSQP (C version of same, with enhancements; port and enhancements due
to C.T. Lawrence) are software packages aimed at solving constrained
optimization problems, including constrained minimax problems (where
the max is taken over a finite number of smooth functions). (C)FSQP's
main distinguishing feature is that all the iterates it generates
satisfy the constraints, except for nonlinear equality constraints, for
which mere "semi-feasibility" is maintained (given a scalar constraint
h(x)=0, if h(x0)<=0 (resp. >=0), then h(xk)<=0 (resp. >=0) for all k.)
This is of value in many engineering related problems. Extensive
numerical tests show that FSQP's efficiency is comparable to that of
the most popular (non-"feasible") codes. Detailed User's Manuals are
available. (C)FSQP is available free of charge to academic and other
non-profit organizations (as well as, for an evaluation period, to
for-profit organizations) but may not be redistributed without the
authors' approval. To obtain FSQP or CFSQP, please contact Andre Tits
([e-mail]).

   GARNET:                [COST FREE]
The Garnet system is a fully functional user interface development
environment and toolkit implemented on top of a comprehensive one-way
constraint system. It is in CommonLisp for X/11. All widgets and other
user interface elements are implemented using the constraint. The
constraints are implemented as part of the object system, and the
object system with constraints can be used independently of the
user-interface components, if desired. Garnet is available for free by
anonymous FTP from a.gp.cs.cmu.edu (128.2.242.7). Retrieve
/usr/garnet/garnet/README. More information on Garnet is available from
http://www.cs.cmu.edu:8001/Web/Groups/garnet/garnet-home.html or in the
newsgroup comp.windows.garnet or e-mail [e-mail]. See also [1-5]
PTF for more details. See also Multi-GArnet, below.

   GOEDEL:                [COST FREE]
Goedel is intended to be a declarative successor to Prolog.
It is defined as supporting certain constraint domains, but these are
not yet implemented. See the comp.lang.prolog FAQ for more details.

   ICOT language CU-PROLOG:
See entry CU-PROLOG.

   ICOT language CAL in ESP:        [COST FREE]
To execute this system, SIMPOS Ver.7 must be running on your PSI.
CAL is a sequential constraint logic programming language which can
deal with various constraints including non-linear polynomial
equations.
In the CAL system, you can use Context. A context is a constraint set.
A new context is created whenever the constraint set is changed. The
history of changing contexts is manipulated by the Context Tree, and
Current Context is the target of the context manipulation. You can
set a context on the context tree arbitrarily as the current context.
Functions include finding real roots:
The query "find" computes real roots of the univariate equations
and returns one solution. The user can obtain other solutions by
backtrack, and branches of the context tree are created.
The CAL system has 4 constraint solvers,
 (1) Algebraic constraint solver
 (2) Boolean constraint solver
 (3) Linear constraint solver
 (4) Set constraint solver
Available free by anonymous ftp: see section [1-5].

 A. Aiba, K. Sakai, Y. Sato, D. J. Hawley, and R. Hasegawa:
 Constraint Logic Programming Language CAL. In Proceedings of the
 International Conference on Fifth Generation Computer Systems 1988,
 November 1988.

 Contrainte Avec Logique version 2.12 User's manual
 Institute for New Generation Computer Technology,
 in preparation.

   ICOT language CAL Common ESP version written in CESP:   [COST FREE]
Same as CAL in ESP, but can run on Unix, needing: UNIX machine, Emacs
CESP, C language compiler, GNU MP, 50Mbyte disk, 16Mbyte memory
Available free by anonymous ftp: see section [1-5].

   ICOT language Hierarchical CLP Language CHAL:    [COST FREE]
You need the SIMPOS/ESP environment to run CHAL.
Hierarchical Constraint Logic Programming Language: CHAL
A hierarchical constraint logic programming language processor
which introduces hierarchy in terms of strength of constraints.
Hierarchical constraint logic programming language CHAL
consists of constraint hierarchy solver which manipulates
various strength of constraints in various domains and
constraint language processor.
An Extension of Constraint Logic Programming Language
Usual constraint logic programming languages output nothing
if there is no solution for given constraints. On the other
hand, by introducing hierarchy of strength in constraints,
CHAL ignores some weak constraints in order to output some
better solutions. This function is important in planning
and design problems.
Available free by anonymous ftp: see section [1-5].

   ICOT language PCHAL:            [COST FREE]
Hierarchical Constraint Parallel Solver: P-CHAL
Similar to CHAL, above.
Parallel Solving of Constraint Hierarchy: P-CHAL reduces computational
costs by a bottom-up calculation of maximal consistent sets and
parallel processing of GDCC.
Available free by anonymous ftp: see section [1-5].

   ICOT language Knowledge Representation Language Quixote: [COST FREE]
Main documentation in Japanese.
Quixote is a DOOD (Deductive Object-Oriented Database) system
developed at ICOT. The following are outstanding Quixote features.
1. Object identity defined over extended terms (object terms).
2. Constraints in terms of subsumption relation among object terms.
3. Property inheritance among objects.
4. Modularized and hierarchical knowledge bases defined by modules
and rule inheritance between them.
5. Queries having additional assertions to knowledge bases, and
answers with assumed constraints.
Available free by anonymous ftp: see section [1-5].

Kazumasa Yokota, Deductive Object-Oriented Databases, Computer
Software, Vol.9, No.4, pp3--18, 1992 (in Japanese).

Hideki Yasukawa, Hiroshi Tsuda, and Kazumasa Yokota,
Object, Properties, and Modules in QUIXOTE,
Proc. of FGCS92, pp257--268, 1992.

Quixote Ver.III consists of (1) Quixote client on UNIX with C,
X-Window(X11R5), and GNU-Emacs, and (2) Quixote server on PIM/PIMOS
with KL1. Both UNIX workstation (such as SS2) and PIM/PSI are required
to run this version of Quixote.

   ICOT language Micro Quixote (Version 0.5):        [COST FREE]
Micro Quixote is another implementation of the language Quixote. It is
implemented with C. It eliminates many features of Quixote, and only
implements core feature of Quixote. However, it's small, and easy to
install. And more, it is expected that Micro Quixote could run on other
operating systems apart from Unix.
Available free by anonymous ftp: see section [1-5].

   ICOT language GDCC (Guarded Definite Clauses with Constraints):
                    [COST FREE]
GDCC is the parallel constraint logic programming experimental system.
GDCC has been developed on PIMOS and runs only on PIMOS. Therefore,
PIMOS needs to be installed on your machine before GDCC is installed.
Includes linear constraints, boolean constraints, and the find utility
(Algebraic constraint solver) which is used to find approximate real
roots from the results of solving algebraic constraints.
Available free by anonymous ftp: see section [1-5].

   IF/Prolog 5.0            [COST COMMERCIAL]
IF/Prolog 5.0 is a full ISO-compliant Prolog which incorporates
constraint solving technology. IF/Prolog is available on ALL UNIX
systems, VMS, OSF/1, MS-Windows and Mainframes. Constraint domains
include Boolean constraints, Rational terms, Linear terms, Equations
and Inequations, Finite Domain Constraints and Co-routines. Interfaces
to standard software packages and other programming languages including
C, C++ and FORTRAN, SQL (Ingres, Oracle and Informix) and X11 (Motif
and Athena widgetsets). IF/Prolog has full screen X11 and Windows based
debuggers and online hypertext help and quick reference guide.
IF/Prolog 5.0 is available on ALL UNIX, OSF/1, VMS and MS-Windows, OS/2
platforms. There is a 50% accademic discount and demo licences are
avilaible. Further information contact: Annette Kolb (marketing) or
Dr. Andrew Verden (technical) at IF Computer GmbH, Ludwig-Thoma-Weg
11a, D-82065 Baierbrunn, tel [phone], fax [phone].
E-mail [e-mail]

   ILOG SCHEDULE:            [COST COMMERCIAL]
ILOG SCHEDULE is an add-on to ILOG SOLVER, used to develop finite
capacity scheduling applications. ILOG SCHEDULE includes a natural
object model for representing schedules in terms of activities and
resources used and shared by these activities. Three categories of
constraints are predefined:
 - TEMPORAL CONSTRAINTS. Users may link any two activities together
   by any type of precedence constraint. Minimum and maximum delays
   between activities can be imposed.
 - CAPACITY CONSTRAINTS. Unary resources represent resources of
   capacity one. Volumetric resources represent resource pools of
   non-differentiated resources. State resources represent situations
   where an activity uses a resource only under specific conditions.
   The capacity of a resource can be constrained either at each time
   unit or over given time periods.
 - RESOURCE UTILIZATION CONSTRAINTS. An activity may require, consume,
   provide and produce resources, in an amount represented either
   as a constant or as an ILOG SOLVER variable. This allows the
   representation of the case where the duration of the activity
   varies with the amount of resources assigned to the activity.
ILOG SCHEDULE is available on the same platforms as ILOG SOLVER. For
further information and contact addresses, see entry on ILOG SOLVER.

   ILOG SOLVER:                [COST COMMERCIAL]
[Ilog and Bull have agreed to sell the same thing under different
names. Charme Object and Ilog Solver have been merged. M Jampel.]
ILOG SOLVER (formerly called PECOS) is a highly efficient C++ class
library that implements constraint programming. SOLVER has been used
to develop fielded applications handling large problems in areas such
as job shop scheduling, timetabling, configuration, transport,
logistic planning, network routing, and frequency allocation.
SOLVER implements integer variables, floating point variables, Boolean
variables, and set variables. Constraints include =, <=, >=, <, >, +,
-, *, /, subset, superset, union, intersection, member, Boolean or,
Boolean and, Boolean not, Boolean xor, cardinality, element, generic
constraints, and meta constraints (conjunction and disjunction of
constraints, order among constraints). You can add new constraints to
SOLVER by deriving new C++ classes.  SOLVER provides a backtracking
search and a branch-and-bound algorithm together with a large number
of search strategies. SOLVER also provides C++ classes and functions
that implement non-deterministic programming.
SOLVER is available on most Unix platforms and on MS-Windows.  For
further information, please contact:
- In the USA and Canada:        - Outside the USA:
  ILOG, Inc.                      ILOG SA
  2105 Landings Drive             12 avenue Raspail
  Mountain View, CA 94303.        94251 Gentilly Cedex, France
  Phone: [phone]            Phone: [phone]
  e-mail: [e-mail]           e-mail: [e-mail]
- The ILOG web server at the URL: http://www.ilog.fr/

   LIFE:                [COST FREE]
LIFE (Logic, Inheritance, Functions, and Equations) is an experimental
programming language with a powerful facility for structured type
inheritance. It reconciles styles from functional programming, logic
programming, and object-oriented programming. It subsumes the
functionality of its precursor languages LOGIN and Le_Fun, and may be
seen as an extension of Prolog. The syntax of Wild_LIFE has been kept
as close as possible to that of the Edinburgh standard for Prolog.
LIFE offers natively high-level abstraction facilities and convenient
data and control structures particularly well-suited for AI
programming. LIFE implements a constraint logic programming language
with equality (unification) and entailment (matching) constraints over
order-sorted feature terms. The interplay of unification and matching
provides an implicit coroutining facility thanks to an automatic
suspension mechanism. This allows interleaving interpretation of
relational and functional expressions which specify structural
dependencies on objects. The Wild_LIFE interpreter is the first
implementation of the LIFE language available to the general public.
It is a product of the Paradise project at Digital Equipment
Corporation's Paris Research Laboratory (DEC PRL). Wild_LIFE runs on
DECstations (Ultrix), SparcStations and RS/6000 systems and should be
portable to other Unix workstations. It is implemented in C, and
includes an interface to X Windows. Wild_LIFE is available by anonymous
ftp from gatekeeper.dec.com:/pub/plan as the file Life.tar.Z. To be
added to the mailing list ([e-mail]), send mail to
[e-mail]. Send bug reports to [e-mail].
See also [1-5] PTF for more details.

   OMEGA:                [COST FREE]
Version 0.90 of the Omega Calculator and Omega Library is now
available, including source code. The Omega library/calculator
manipulates sets of integer tuples and relations between integer
tuples. Some examples include:

{ [i,j] : 1 <= i,j <= 10};
{ [i] ->[i,j] : 1 <= i < j <= 10};
{ [i,j] ->[j,j'] : 1 <= i < j < j' <= n};

The conditions describing a set or tuple can be an formulas can
described by an arbitrary Presburger formula. Relations and sets can be
combined using functions such as composition, intersection, union and
difference. It also provides routines to generate code to iterate over
the points in an integer tuple set. The Omega library provides a
high-level, C++ interface to our routines. The Omega calculator is a
text-based interface to the Omega library. Omega is available for
anonymous ftp from ftp.cs.umd.edu:pub/omega/omega_library. More
information is available by email from [e-mail] on the www at
http://www.cs.umd.edu/projects/omega/.

   OZ:                    [COST FREE]
Oz is a concurrent constraint programming language designed for
applications that require complex symbolic computations, organization
into multiple agents, and soft real-time control. It is based on a new
computation model providing a uniform foundation for higher-order
functional programming, constraint logic programming, and concurrent
objects with multiple inheritance. From functional languages Oz
inherits full compositionality, and from logic languages Oz inherits
logic variables and constraints (including feature and finite domain
constraints). Search in Oz is encapsulated (no backtracking) and
includes one, best and all solution strategies.
DFKI Oz is an interactive implementation of Oz featuring a programming
interface based on GNU Emacs, a concurrent browser, an object-oriented
interface to Tcl/Tk, powerful interoperability features (sockets, C,
C++), an incremental compiler, a garbage collector, and support for
stand-alone applications. Performance is competitive with commercial
Prolog and Lisp systems. DFKI Oz is available for many platforms
running Unix/X, including Sparcs and 486 PCs. Applications DFKI Oz has
already been used for include simulations, multi-agent systems, natural
language processing, virtual reality, graphical user interfaces,
scheduling, placement problems, and configuration.
Version 1.0 of DFKI Oz (January 23, 1995) is available by anonymous ftp
from ps-ftp.dfki.uni-sb.de:/pub/oz, or through the WWW from
    http://ps-www.dfki.uni-sb.de/
Tutorials, reference manuals, and research papers are available from
the same sources. You may start with "A Survey of Oz" (8 pages) and
continue with "An Oz Primer" (110 pages). For specific questions mail
[e-mail]. To join the Oz users mailing list, contact
[e-mail].

   PROFIT:                 [COST FREE]
ProFIT (Prolog with Features Inheritance and Templates) is an extension
of Prolog with sorted feature structures (including multi-dimensional
inheritance), finite domains, feature search, cyclic terms, and
templates. ProFIT works as a pre-processor, which takes a file
containing a ProFIT program as input, and gives a file with a Prolog
program as output. Sorted feature terms and finite domains are
compiled into a Prolog term representation, and the usual Prolog term
unification is used at runtime, so that there is no slowdown through a
unification algorithm, and no meta-interpreter is needed. ProFIT uses
the same techniques for compiling sorted feature terms and finite
domains into Prolog terms as the Core Langauge Engine of SRI Cambridge
and the Advanced Linguistic Engineering Platform (ALEP 2.2) by the
European Community, BIM, and Cray Systems. ProFIT is not a grammar
formalism (although it is motivated by NLP), although it provides some
ingredients that are considered typical of grammar        sms. The goal
of ProFIT is to provide these datatypes without enforcing any
particular theory of grammar, parsing or generation. ProFIT can be used
to extend your favourite Prolog-based grammar formalism, parser and
generator with the expressive power of sorted feature terms. Cyclic
terms can be printed out and a user-configurable pretty-printer for
feature terms is provided. ProFIT is available free of charge by
anonymous ftp from coli.uni-sb.de:/pub/profit
Implemented in Sicstus Prolog (2.1 #9) by Gregor Erbach, Univ.
Saarlandes, Saarbruecken, Germany <[e-mail]>
<http://coli.uni-sb.de/~erbach>

   PROLOG III:                [COST COMMERCIAL]
Prolog III was the first commercial Constraint Logic Programming
language. It incorporates all the main features of PROLOG II+, but
also gives the user the ability to express constraints over various
different domains. In particular the fundamental concept of constraint
resolution allows for numerical processing and also a complete
treatment of Boolean algebra, in a logic programming style. Version
1.5 of PROLOG III is available on wide range of platforms including PC,
MAC, UNIX, ULTRIX, VMS, NeXTSTEP, ALPHA OSF1. For more information,
write to PrologIA, Luminy - case 919 - 13288 MARSEILLE cedex 09 -
FRANCE or contact Fabienne LELEU : ph (33) 91 26 86 36 fax (33) 91 41
96 37 e-mail [e-mail]

   QUANTUM LEAP:            [COST COMMERCIAL or CHEAP]
                    [See last paragraph]
The Quantum Leap Problem Solving Engine (PSE) works like a community of
competing and cooperating experts - each one using a different
methodology to obtain the best solution to a problem. Users employ the
Problem Representation Facility (PRF), an object based, graphical
interface, to build statements of their problems. Quantum Leap employs
a coordinated team of optimization methods, including: Linear
Programming, Quadratic Programming, Generalized Reduced Gradient,
Conjugate Direction, Evolutionary Programming, Simulated Annealing,
Zoomed Enumeration, Logical Reduction, Pseudo Boltzman, and Heuristic
Search. It also offers an object-oriented, tabular, multidimensional
representation, with inheritance and self-reference, both numeric and
symbolic constructs, an English-like language, internal and external
(C) user defined functions, and many built-in aggregates and numeric
functions. It has a Client-Server Architecture, with the PSE
implemented locally, on another LAN node, or remotely. A multi-PSE
version finds faster solutions to many problems via parallel
processing. Users can define multiple objectives, and priorities among
goals. The system finds "Best Balanced" points for infeasible problems,
and multiple solutions to some problems. APIs are available that allow
a compiled model to be used as a stand-alone application. Quantum
Development wants you to solve your problem, then grant the right to
publish your approach! In return, you become a member of the LEAPER
program, use Quantum Leap for only shipping and materials cost. Leapers
will receive the LEAPER LETTER, a moderated news-list for exchange of
technical information. To receive more information, send email to
[e-mail]. The body of the note should contain, as the first
line: GET <offer>

   SCREAMER:                [COST FREE]
Screamer is an extension of Common Lisp that adds support for
nondeterministic programming. Screamer consists of two levels. The
basic nondeterministic level adds support for backtracking and undoable
side effects. On top of this nondeterministic substrate, Screamer
provides a comprehensive constraint programming language in which one
can formulate and solve mixed systems of numeric and symbolic
constraints. Together, these two levels augment Common Lisp with
practically all of the functionality of both Prolog and constraint
logic programming languages such as CHiP and CLP(R). Furthermore,
Screamer is fully integrated with Common Lisp. Screamer programs can
coexist and interoperate with other extensions to Common Lisp such as
CLOS, CLIM and Iterate.

In several ways Screamer is more efficient than other implementations
of backtracking languages. The overhead to support backtracking is only
paid for those portions of the program which use the backtracking
primitives. Deterministic portions of user programs pass through the
Screamer to Common Lisp transformation unchanged. If only small
portions of your programs utilize the backtracking primitives, Screamer
can produce more efficient code than compilers for languages in which
backtracking is more pervasive.

Screamer is fairly portable across most Common Lisp implementations.
Screamer is available from ftp.ai.mit.edu:/pub/screamer.tar.Z. Contact
Jeffrey Mark Siskind <[e-mail]> for further information.

   SCREAMER TOOL REPOSITORY        [COST FREE]
There is a tools repository (ftp site) for user-contributed Screamer
code: ftp.cis.upenn.edu:/pub/screamer-tools. The repository is also
accessible at http://www.cis.upenn.edu/~screamer-tools/home.html
Questions about the repository to [e-mail].

   SEL:                    [COST FREE]
SEL is a declarative set processing language. Its main features are
subset and equational program clauses, pattern matching over sets,
support for efficient iteration and point-wise/incremental computation
over sets, the ability to define transitive closures through circular
constraints, meta-programming and simple higher-order programming, and
a modest user-interface including tracing. The language seems
well-suited to a number of problems in graph theory, program analysis,
and discrete mathematics. The SEL compiler is written in Quintus Prolog
and the run-time system is written in C. It generates WAM-like code,
extended to deal with set-matching, memoization, and the novel control
structure of the language. SEL is available by anonymous FTP from
ftp.cs.buffalo.edu:/users/bharat/SEL2/. The FTP release comes with a
user manual, bibliography of papers (including .dvi files), several
sample programs, and source code. For further information, write to
Bharat Jayaraman <[e-mail]>.

   SEPIA:                [COST FREE with ECLIPSE]
See ECLIPSE (also see 'ECRC SEPIA').

   SICSTUS PROLOG:            [COST A=CHEAP,E=??,C=COMMERCIAL]
SICStus Prolog is a Unix prolog by SICS. It is portable to most UNIX
machines (Berkeley UNIX is preferred over System V). SICS Aurora and
Echo is a parallel emulator for Sequent Balance, Sequent Symmetry,
Encore Multimax, and BBN Butterfly (Unix). For more information, write
to SICS, Swedish Institute of Computer Science, P.O. Box 1263, S-164
28 KISTA, Sweden, call [phone], fax [phone], or send
email to [e-mail] or [e-mail]. Bug reports
and tech support questions should be sent to [e-mail].
To subscribe to the users group and implementors mailing list, send
email to [e-mail].

   SKYBLUE:                [COST FREE-PD]
A constraint-solving algorithm. See information on the Seattle ftp site
in section [1-5]. See paper by Freeman-Benson et al in section [1-6].

   STEELE'S CONSTRAINT SYSTEM:        [COST FREE]
Chris Hanson's implementation of Steele's constraint system is
available by ftp from martigny.ai.mit.edu:/archive/cph/constraint.tar
or nexus.yorku.ca:/pub/scheme/new/constraint.tar.Z. A compressed
version is also stored there. The software is source code for MIT
Scheme. It should run in release 7.1.3. Most of the MIT Scheme
dependencies could be eliminated, but it also uses the following
procedures which aren't in standard Scheme: error, bkpt, macros,
dynamic binding, and string output ports. The code corresponds pretty
closely to Guy Steele's PhD thesis implementation, which you can obtain
in printed form from the MIT AI Lab publications office as AI-TR-595
for $15.00 (email [e-mail] for more information). For
more information, send email to Chris Hanson
<[e-mail]>.

   THINGLABII                [COST FREE-PD]
ThingLabII is a constraint-based package. See information on the Seattle
ftp site in section [1-5].

   TOUPIE:                [COST FREE]
Toupie is a finite domain $\mu$-calculus interpreter designed by A.
Rauzy <[e-mail]>. It uses Decision Diagrams to
represent relations and formulas. Decision Diagrams are an extension of
the BDD first introduced by Bryant. The original propositional
$\mu$-calculus interpreter was designed to express properties of finite
states machines. In addition to classical connectives of the
propositional calculus, it provides the two quantifications and the
possibility to define relations as least or greatest fixpoints of
equations. Toupie is a $\mu(\cal FD)$ interpreter, i.e. an extension to
finite domains handling numerical linear constraints. This language has
been successfuly used for abstract interpretation of Prolog, analysis
of mutual exclusion algorithms, classical logic puzzles and
model-checking a recent presentation can be found in ESOP'94 "Symbolic
Model Checking and Constraint Logic Programming: a Cross-
Fertilization". [Information kindly supplied by Marc-Michel
Corsini <[e-mail]>.]

   TRILOGY:                [COST CHEAP]
Trilogy is a constraint system developed by Complete Logic Systems. It
costs $100. For more information, write to Complete Logic Systems, Inc,
741 Blueridge Avenue, V7R 2J5, North Vancouver BC, Canada, or call
604-986-3234. [Does the company still exist?]

   VS TRILOGY:                [COST COMMERCIAL]
VS Trilogy is a Prolog compiler available from Vertical Software for
$395. For more information, write to Vertical Software Ltd., 14-636
Clyde Ave, W. Vancouver, BC, V7T 1E1, Canada, call 604-925-0321, or fax
604-688-8479.

   WAMCC:                [COST FREE]
WAMCC 2.2 is a WAM-based Prolog to C compiler. It conforms more or
less to the Edinburgh standard, and includes most of the usual built-in
predicates, a top-level, a Prolog debugger and a WAM debugger. It is
designed to be easily extended (for example see clp(FD)). WAMCC's
speed is halfway between SICStus emulated and SICStus native code on a
Sparc (1.5 times faster and 1.5 times slower, respectively). It
requires GCC 2.4.5 or higher and has been tested on Sparc workstations.
It should be easily ported to 32-bit machines with GCC. WAMCC is
available free by anonymous ftp from
ftp.inria.fr:/INRIA/Projects/ChLoE/LOGIC_PROGRAMMING/wamcc/
For more information, write to Daniel Diaz <[e-mail]>,
INRIA Rocquencourt, FRANCE.
----------------------------------------------------------------
;;; *EOF*