Path: news1.ucsd.edu!ihnp4.ucsd.edu!swrinde!newsfeed.internetmci.com!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!faqserv
From: jampel@cs.city.ac.uk (Michael Jampel)
Newsgroups: comp.constraints,comp.answers,news.answers
Subject: comp.constraints FAQ 1/2 Frequently Asked Questions [Monthly posting]
Supersedes: <constraints-faq/part1_813948566@rtfm.mit.edu>
Followup-To: comp.constraints
Date: 16 Nov 1995 23:22:22 GMT
Organization: Department of Computer Science, City University
Lines: 1171
Approved: news-answers-request@MIT.Edu
Expires: 30 Dec 1995 23:20:30 GMT
Message-ID: <constraints-faq/part1_816564030@rtfm.mit.edu>
Reply-To: jampel@cs.city.ac.uk (Michael Jampel)
NNTP-Posting-Host: bloom-picayune.mit.edu
Summary: Frequently asked questions about constraints
X-Last-Updated: 1995/10/02
Originator: faqserv@bloom-picayune.MIT.EDU
Xref: news1.ucsd.edu comp.constraints:734 comp.answers:12785 news.answers:49443
Archive-name: constraints-faq/part1
Last-Modified: Mon Oct 2 15:40:00 1995 by Michael Jampel
Version: 1.79
Important Changes (since last posting): CLP(R) and analog circuits.
Additional info on TOC: Theory of Constraints
Contributions and corrections should be sent to Michael Jampel
<jampel@cs.city.ac.uk>.
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
<pb@llaor.unice.fr>, Mark Kantrowitz <mkant@cs.cmu.edu>, Wm Leler
<wm@ithaca.com>, Manfred Meyer <meyer@dfki.uni-kl.de>, Milind Tambe
<tambe@isi.edu>, Thomas Schiex <schiex@cert.fr>, and Tad Hogg
<hogg@parc.xerox.com>.
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 and Journals
[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 and LISP 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
[1-20] Survey of CLP with Non-Linear Constraints (architectures)
[1-21] TOC: The management "Theory of Constraints"
[1-22] Global, specific, structural, continuous & symbolic constraints
[1-23] CLP(R) and analog circuit diagnosis
In the second part of this FAQ:
[2-1] Introduction (same as in part1)
[2-2] Introduction to Systems for Non-Linear Constraints
[2-3] 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 mail-server@rtfm.mit.edu
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 and Journals
Constraint Logic Programming
clp-request@cis.ohio-state.edu
For those interested in the CLP(R) Language:
clpr-users-request@cis.ohio-state.edu
Both the above lists are maintained by Spiro Michaylov
<spiro@cis.ohio-state.edu>. E-mail the given addresses for more info.
The list clp-request.All_Areas@xerox.com, 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 listserver@saturne.cert.fr in the form
"SUB CSP-LIST <name>". (Send submissions to <csp-list@saturne.cert.fr>.)
List maintained by Thomas Schiex <schiex@cert.fr>. 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 <IDSS@socs.uts.EDU.AU>. Subscription requests
should be sent to <idss-request@socs.uts.EDU.AU>
The Journal of Functional and Logic Programming (JFLP) is a new
electronic journal that covers a broad scope of topics from functional
and logic programming. It is specially concerned with the integration
of the functional and logic paradigm as well as their common
foundations. The Journal expects articles ranging from the theoretical
foundations of functional and logic programming up to the application
of such languages ``in the real world''. The Journal is published by
The MIT Press. See either of the following URL's for more details
http://mitpress.mit.edu/jrnls-catalog/jflp.html
http://www.cs.tu-berlin.de/~chak/jflp/
Various AI and Logic Programming journals are likely to have articles on
constraints, including `AI Journal'.
There will soon be a new journal called CONSTRAINTS, pulished by Kluwer:
Editor-in-Chief: Eugene C. Freuder, University of New Hampshire
(ecf@cs.unh.edu)
CONSTRAINTS will be available both as a conventional paper journal and
in electronic form. Publication will commence in the second half of 1996.
Aims and Scope: The journal seeks to provide a common forum for the
many disciplines interested in constraint satisfaction and
optimization, and the many application domains interested in employing
constraint technology. It will cover all aspects of computing with
constraints: theory and practice, algorithms and systems, reasoning
and programming, logics and languages. Relevant disciplines and
application domains include, but are not limited to:
Disciplines
Artificial Intelligence
Programming Languages
Operations Research
Combinatorial Algorithms
Discrete Mathematics
Databases
Computational Logic
Symbolic Computation
Parallel/Distributed Computing
Neural Networks
Domains
Scheduling, Planning, Resource Allocation
Design and Configuration
Graphics, Visualization, Interfaces
Hardware Verification and Software Engineering
Robotics, Machine Vision and Computational Linguistics
Temporal and Spatial Reasoning
Qualitative and Diagnostic Reasoning
Human-Computer Interaction and Decision Support
Real-Time Systems
Molecular Biology
Papers that cut across disciplinary lines, or that combine theory and
practice, are especially welcome. The journal will also consider
tutorial and survey papers.
The Instructions for Authors can be obtained from Miss Kelly Riddle
via e-mail: krkluwer@world.std.com.
----------------------------------------------------------------
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.
Mark_Kantrowitz@cs.cmu.edu 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 <brian@daimi.aau.dk>.
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}
Originally maintained by Spiro Michaylov <spiro@cis.ohio-state.edu>
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].
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
<jwg@ceres.cray.com> 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 ifs@icot.or.jp, 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 +81-3-4456-1618. 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
<ptf@cfcl.com> 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 <borning@cs.washington.edu> for details.
ftp.cs.washington.edu:/pub/constraints or, on WWW,
http://www.cs.washington.edu/research/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/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 <hogg@parc.xerox.com>.
----------------------------------------------------------------
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 <pb@llaor.unice.fr>, 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
<micha@ecrc.de> 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, University 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 <mohan@yoko.rutgers.edu>, 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 and LISP Programs
Patrick Prosser <pat@cs.strath.ac.uk> discusses various standard
algorithms in the journal Computational Intelligence vol 9(3), 1993.
Scheme versions available from Pat on request; Lisp implementations
are available from ftp://ftp.cs.strath.ac.uk/local/pat/csp-lab.
Peter Van Beek <vanbeek@cs.ualberta.ca> has written a set of libraries
for C. This package is available from ftp://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 <tambe@isi.edu> 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 1, 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 <pvh@cs.brown.edu> 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.edu:/pub/techreports/94/cs94-18.ps.Z
----------------------------------------------------------------
Subject: [1-15] Dynamic CSPs (Constraint Satisfaction Problems)
Thomas Schiex <schiex@saturne.cert.fr> 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.
----------------------------------------------------------------
Subject: [1-20] Survey of CLP with Non-Linear Constraints
by Olga Caprotti <Olga.Caprotti@risc.uni-linz.ac.at>
Systems (discussed individually in Part 2 of this FAQ):
CAL
CLP(F)
GDCC
ILOG Solver
Newton
QUAD-CLP(R)
RISC-CLP(Real)
Architectures (discussed here):
Cooperative Constraint Solvers
Symbolic Representation Scheme
----------------------------------------------------------------
Cooperative Constraint Solvers
------------------------------
Michel Rueher <rueher@essi.fr>
For solving constraints over the reals, we have defined a cooperating
architecture based on an asynchronous communication between
heterogeneous solvers. It enables to put together both symbolic and
numerical solvers for tackling systems of constraints that none of them
could solve alone. Solutions provided by such a cooperating system are
always at least as accurate than the one which could individually be
computed by the different solvers. A prototype for a cooperative system
including a solver of linear equations and inequalities, a solver of
polynomial equalities, and a solver based on interval propagation is
under development.
References:
[1] Michel Rueher. An Architecture for Cooperating Constraint Solvers
on Reals. In "Constraint Programming: Basics and Trends". LNCS 910,
231-250, March 1995.
[2] Philippe Marti and Michel Rueher. A Distributed Cooperating
Constraints Solving System, Research Report I3S, Bat. 4,
250 av. A. Einstein, 06560 Valbonne, France, March 1995
----------------------------------------------------------------
Symbolic Representation Scheme
------------------------------
Leon Sterling <leon@ces.cwru.edu>
This paper describes experience in using constraint logic programming
to reason about mechanical parts. A prototype program was written in
the language CLP(R) which verified whether a part met specific
tolerances in its dimensions. The program is interesting in that the
same code can be used with any mixture of symbolic and numeric values.
A symbolic representation scheme, underlying the program, which allows
both symbolic and numeric values, is described. Examples are given of
defining generic parts and toleranced parts, and checking whether a
part meets its tolerances. Finally, a design rule checker is sketched
to show how the logical representation of logic representation
languages facilitates higher level reasoning.
Reference:
[1] L.S. Sterling. Of Using Constraint Logic Programming for Design of
Mechanical Parts. Intelligent Systems - Concepts and Applications, (ed.
L. Sterling), 107-116, Plenum Press, 1993
----------------------------------------------------------------
Subject: [1-21] TOC: The management "Theory of Constraints"
The "Theory of Constraints" has got nothing to do with CLP, CSP, or
comp.constraints. However, for those who want to find out a little bit
more about it, there is a file containing some email from Thomas McMullen
<75564.310@compuserve.com> (also mentions the 1995 APICS Symposium):
ftp://ftp.cs.city.ac.uk/pub/constraints/management-theory-of-constraints.Z
There is also a WWW page at http://www.rudy.org.il/toc/index.html
----------------------------------------------------------------
Subject: [1-22] Global, specific, structural, continuous & symbolic constraints
[questions and answers edited by MBJ; delimited by `>>>>>>']
From: Peter.Schotman@USERS.INFO.WAU.NL
Newsgroups: comp.constraints
Subject: Question: constraint terminology
Date: Fri, 30 Jun 95 10:37:51
Organization: Wageningen Agricultural University
Question: Could somebody explain the following terms:
- Global constraints
(the FAQ says: "constraints with maximum arity", does that mean that if
the problem contains N variables only N-ary constraints are considered
global?)
- Specific and structural constraints
(in: CHIC lessons on CLP methodology, ECRC-report)
A lot of applications (I think) contain both a set of reasonably stable
(permament) constraints as well as constraints that change from problem
to problem instance, is that what is ment here?
Also I would appriciate pointers to papers that explicitly deal with
problem solving systems for a combination of continuous and symbolic
constraints.
Thanks in advance,
Peter Schotman
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Newsgroups: comp.constraints
From: leconte@ilog.fr (Michel Leconte)
Subject: Re: Question: constraint terminology
Organization: ILOG S.A., France
Date: Mon, 3 Jul 95 12:44:52 GMT
|> Question: Could somebody explain the following terms:
|> - Global constraints
The term "global constraint" is related with the level of consistency
achieved by the propagation engine. A classical example is the "alldiff"
constraint:
alldiff(x1,...xi,...xn)
setting that, in any solution, all the values of the xi must be
pairwise distinct.
The traditionnal (local) handling of this constraint ensures that, each
time a variable is instantiated to a value, this value does not appear
in the domains of the other variables.
More formally, the following holds:
forall xi, forall xj != xi, forall u belonging to the domain of xi,
there exists a value v in the domain of xj such that u != v.
The global handling of this constraint should maintain the following
property:
forall xi, forall u in the domain of xi, there exist values from
domains of {x1,...,xj,...xn | xj != xi} such that u and these values
are pairwise distinct.
In other words, the global consistency of a constraint is: any value in
the domain of a variable belongs to a solution.
The global consistency of the alldiff constraint has been shown by J-C
Regin in: "A filtering algorithm for constraint of difference in CSPs.
Jean-Charles Regin, AAAI 94, Seattle, Washington".
The paper "Beyond the Glass Box: Constraints as Objects. Jean-Francois
Puget, Michel Leconte, ILPS'95", discusses what kind of constructs are
needed to implement global constraints. Experimental results are also
given, demonstrating significant speedups vs local propagation
implementations.
|> - Specific and structural constraints
|> (in: CHIC lessons on CLP methodology, ECRC-report)
The CHIC project (Constraint Handling in Industry and Commerce, Esprit
project number 5291) was finished at the end of 1994. One of its result
concerns the CLP methodology, with a big emphasis on the qualification
phase: given a (instance of a) problem, (try to) predict if:
- it is feasible,
- it needs the coding of new constraints (e.g. the cooperation
of OR [operations research] algorithms and propagations).
One of the first phases of the methodology is to differentiate specific
and structural constraints:
Structural constraints deals with global properties of the problem and
act on variables playing similar roles (the sub-problem is homogeneous).
For example, you can easily encode a flow transportation problem in a
CLP using elementary arithmetic constraint. Netherless, there is a more
global structure (a graph) that represents the problem together with a
_structural_ constraint (flow conservation) to express it.
At the opposite, specific constraints depends on the instance of the
application.
|> Also I would appreciate pointers to papers that explicitly deal with
|> problem solving systems for a combination of continuous and symbolic
|> constraints.
You could have a look at "H. Beringer and B. De Backer. Combinatorial
Problem Solving in Constraint Logic Programming with cooperating
Solvers. In C. Beierle and L. Plumers Editors, Logic Programming:
Formal methods and Practical Applications, Elsevier Science B.V. 1995"
----------------------------------------------------------
Michel Leconte net : leconte@ilog.fr
ILOG S.A. tel : +33 1 49 08 35 00
9, rue de Verdun - BP 85 fax : +33 1 49 08 35 10
F-94253 Gentilly Cedex url : http://www.ilog.com
FRANCE url : http://www.ilog.fr
----------------------------------------------------------
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Newsgroups: comp.constraints
From: micha@ecrc.de (Micha Meier)
Subject: Re: Question: constraint terminology
Organization: European Computer-Industry Research Centre
Date: Tue, 4 Jul 1995 08:10:44 GMT
The term 'global constraints' has been used in CHIP to actually denote
constraints that subsume a set of other constraints. It does not
necessarily mean that complete global consistency is being achieved,
but just the fact that more consistency is being achieved than by
considering each constraint in this set separately. This concerns
mainly finite domain constraints where global consistency is hard to
obtain. The term 'global constraints' is quite misleading, and it
should be replaced by something more appropriate like e.g. 'composite
constraints'. Note that you can have several global constraints with
the same declarative reading, but with different algoritm being used
and thus different levels of consistency being achieved.
---
Micha Meier ------------------------------------------------
ECRC, Arabellastr. 17 The opinions expressed above are private
D-81925 Munich 81 and may not reflect those of my employer.
micha@ecrc.de, Tel. +49-89-92699-108, Fax +49-89-92699-170
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
From: walter@wolf.uni-koblenz.de (Walter Hower)
Newsgroups: comp.constraints
Subject: Re: Question: constraint terminology
Date: 03 Jul 1995 09:27:39 GMT
Organization: University Koblenz / Germany
@Article{David:95,
author = "Philippe David",
title = "{Using Pivot Consistency to Decompose and Solve
Functional CSPs}",
journal = "Journal of Artificial Intelligence Research",
year = 1995,
volume = 2,
pages = "447--474",
month = "May",
note = "AI Access Foundation and Morgan Kaufmann Publishers"
}
@InProceedings{Dechter:vanBeek:95,
author = "Rina Dechter and Peter {van Beek}",
title = "{Local and Global Relational Consistency---Summary
of Recent Results}",
editor = "Ugo Montanari",
series = "Lecture Notes in Computer Science",
booktitle = "Principles and Practice of Con\-straint Programming",
year = "1995",
publisher = "Proceedings, Springer-Verlag, Berlin/Heidel\-berg",
month = "September 19-22,",
note = "CP95, First International Conference, Cassis, France",
}
@InProceedings{Haroud:Faltings:PPCP94,
author = "Djamila Haroud and Boi Faltings",
title = "{Global Consistency for Continuous Constraints}",
editor = "Alan Borning",
volume = "874",
series = "Lecture Notes in Computer Science",
pages = "40--50",
booktitle = "Principles and Practice of Con\-straint Programming",
year = "1994",
publisher = "Proceedings, Springer-Verlag, Berlin/Heidel\-berg",
month = "May 2-4,",
note = "Second International Workshop, PPCP '94,
Rosario, Orcas Island, WA, USA",
}
@InProceedings{Jeavons:et:al:95,
author = "Peter Jeavons and David Cohen and Marc Gyssens",
title = "{A Unifying Framework for Tractable Constraints}",
editor = "Ugo Montanari",
series = "Lecture Notes in Computer Science",
booktitle = "Principles and Practice of Con\-straint Programming",
year = "1995",
publisher = "Proceedings, Springer-Verlag, Berlin/Heidel\-berg",
month = "September 19-22,",
note = "CP95, First International Conference, Cassis, France",
}
@InProceedings{Liu:95,
author = "Bing Liu",
title = "{Increasing Functional Constraints Need to Be Checked Only Once}",
booktitle = "{IJCAI-95, Proceedings of the Fourteenth International
Joint Conference on Artificial Intelligence}",
year = "1995",
editor = "Chris Mellish",
organization = "IJCAII",
address = "Montr{\'{e}}al, Qu{\'{e}}bec, Canada",
month = "August 20--25,",
note = "Distributed by Morgan Kaufmann Publishers, Inc., San
Francisco, California, USA"
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Abderrahmane Aggoun (aggoun@cosytec.fr) sent the following references by
email to Peter, concerning global constraints in CHIP:
@Article{Aggoun:Beldiceanu:93,
author = "Abderrahmane Aggoun and Nicolas Beldiceanu",
title = "{Extending CHIP in order to solve complex scheduling and
placement problems}",
journal = "Mathl. Comput. Modelling",
year = 1993,
volume = 17,
month = "no. 7",
pages = "57--73",
}
@Article{Beldiceanu:Contejean:94,
author = "N. Beldiceanu and E. Contejean",
title = "{Introducing global constraints in CHIP}",
journal = "Mathl. Comput. Modelling",
year = 1994,
volume = 20,
month = "no. 12",
pages = "97--123",
}
----------------------------------------------------------------
Subject: [1-23] CLP(R) and analog circuit diagnosis
Entry by Franc Novak, Jozef Stefan Institute, Ljubljana, Slovenia
franc.novak@ijs.si http://martin.ijs.si/novak/novak.html
F.Novak, I.Mozetic, M.Santo-Zarnik, A.Biasizzo.
Enhancing design-for-test for active analog filters using CLP(R).
Journal of Electronic Testing: Theory and Applications, Kluwer Ac. Publ.
Vol.4, No. 4, 1993, pp.315-329.
We describe a computer-aided approach to automatic fault isolation in
active analog filters which enhances the design-for-test (DFT)
methodology proposed by Soma (1990). His primary concern was in
increased controllability and observability while the fault isolation
procedure was sketched only in general terms. We operationalize and
extend the DFT methodology by using CLP(R) to model analog circuits and
by a model-based diagnosis approach to implement a diagnostic
algorithm. CLP(R) is a logic programming language which combines
symbolic and numeric computation. The diagnostic algorithm uses
different DFT test modes and results of voltage measurements for
different frequencies and computes a set of suspected components.
Ranking of suspected components is based on a measure of (normalized)
standard deviations from predicted mean values of component parameters.
The diagnosis is performed incrementally, in each step reducing the set
of potential candidates for the detected fault. Presented case studies
show encouraging results in isolation of soft faults of a given low
pass biquad filter.
----------------------------------------------------------------
;;; *EOF*
----------------------------------------------------------------------
Path: news1.ucsd.edu!ihnp4.ucsd.edu!swrinde!newsfeed.internetmci.com!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!faqserv
From: jampel@cs.city.ac.uk (Michael Jampel)
Newsgroups: comp.constraints,comp.answers,news.answers
Subject: comp.constraints FAQ 2/2 Frequently Asked Questions [Monthly posting]
Supersedes: <constraints-faq/part2_813948566@rtfm.mit.edu>
Followup-To: comp.constraints
Date: 16 Nov 1995 23:23:49 GMT
Organization: Department of Computer Science, City University
Lines: 1092
Approved: news-answers-request@MIT.Edu
Expires: 30 Dec 1995 23:20:30 GMT
Message-ID: <constraints-faq/part2_816564030@rtfm.mit.edu>
References: <constraints-faq/part1_816564030@rtfm.mit.edu>
Reply-To: jampel@cs.city.ac.uk (Michael Jampel)
NNTP-Posting-Host: bloom-picayune.mit.edu
Summary: Free and Commercial Constraint Systems
X-Last-Updated: 1995/10/12
Originator: faqserv@bloom-picayune.MIT.EDU
Xref: news1.ucsd.edu comp.constraints:735 comp.answers:12789 news.answers:49469
Archive-name: constraints-faq/part2
Last-Modified: Thu Oct 12 11:50:00 1995 by Michael Jampel
Version: 2.21
Important Changes (since last posting): Ilog France address change.
QUAD CLP(R) ftp address change.
Contributions and corrections should be sent to Michael Jampel
<jampel@cs.city.ac.uk>.
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
<pb@llaor.unice.fr>, Mark Kantrowitz <mkant@cs.cmu.edu>, Wm Leler
<wm@ithaca.com>, Manfred Meyer <meyer@dfki.uni-kl.de>, Milind Tambe
<tambe@isi.edu>, Thomas Schiex <schiex@cert.fr>, and Tad Hogg
<hogg@parc.xerox.com>.
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] Introduction to Systems for Non-Linear Constraints
[2-3] 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 mail-server@rtfm.mit.edu
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] Introduction to Systems for Non-Linear Constraints
A survey by Olga Caprotti <Olga.Caprotti@risc.uni-linz.ac.at>
Systems (discussed individually in this part):
CAL
CLP(F)
GDCC
ILOG Solver
Newton
QUAD-CLP(R)
RISC-CLP(Real)
The information has been added to the end of the entry for each
individual system. Search for the phrase NON-LINEAR.
Architectures (discussed in Part 1 of the FAQ):
Cooperative Constraint Solvers
Symbolic Representation Scheme
----------------------------------------------------------------
Subject: [2-3] 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 from <ftp://sics.se:/pub/ccp/papers>.
An (as yet non-released) prototype implementation of AKL is available
for research purposes (contact sverker@sics.se).
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
<carp@lcl.cmu.edu>.
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 +33-1-60-19-37-38, fax +33-1-60-19-36-20 or email
<cosytec@cosytec.fr>.
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 (thom@ecrc.de).
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 cial@cs.cuhk.hk 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 <vellino@bnr.ca> (613)763-7513, fax (613)763-4222
Bell-Northern Research, Box 3511, Station C, Ottawa, CANADA K1Y 4H7
See also section [1-6] for papers by Benhamou/ Older/ Vellino.
CLP(F): NON-LINEAR [unavailable]
This extension of CLP(Intervals) has an underlying domain that consists
of boolean, integers, reals, real-valued functions of one variable, and
vectors of domain elements. Function variables are constrained by
functional equations and by putting interval constraints on the values
of their derivatives at points and intervals. The system can be used to
solve constraint problems involving ordinary differential equations.
Contact Tim Hickey <tim@cs.brandeis.edu>
Reference:
[1] T. Hickey. CLP(F) and Constrained ODE's, T. Proceedings of the 1994
Workshop on Constraints and Modelling, Ithica, NY, November, 1994.
Available at: ftp://ftp.ecrc.de/pub/faculty/tim/Papers/islp94.ps
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 <Daniel.Diaz@inria.fr> 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
joxan@watson.ibm.com or joxan@yktvmh.bitnet. 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
clp@moncsbruce.oz.au. [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
<meyer@dfki.uni-kl.de>. [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].
ECHIDNA: [COST FREE]
Echidna is an object oriented constraint logic programming language
developed by the Intelligent Systems Lab at Simon Fraser University
between 1990 and 1993. Constraints in Echidna include finite domain
constraints (as in CHIP) and disjoint real interval domain constraints.
Real domains are implemented by interval hierarchies which allow for
the representation of domains with disjoint sets of intervals.
Hierarchical domains also allow control of the precision of constraint
processing. Since complete search procedures exist for all levels of
precision, it is possible to quickly search through regions with no
solutions at low precision. Where low precision constraint processing
indicates a possible solution, precision can be increased to ensure
convergence on a real solution.
Echidna supports a form of incremental intelligent backtracking for
multiple user queries which provides an effective interactive
mixed-initiative control regime. Users can issue and selectively
retract queries to arrive at a solution to their problem.
Development and support for Echidna v1.0 were halted in 1993. For more
information, go to <http://fas.sfu.ca/cs/research/groups/ISL/> or
<ftp://ftp.fas.sfu.ca/pub/css/esl/echidna> or contact Bill Havens
<havens@cs.sfu.ca>. See:
[1] W.S. Havens: Intelligent Backtracking in the Echidna CLP Reasoning
System, International Journal of Expert Systems: Research and
Applications 5(4), 1992, M. Harandi (ed.), Jai Press, London, 21-45.
[2] Greg Sidebottom and W.S. Havens: Hierarchical Arc Consistency for
Disjoint Real Intervals in Constraint Logic Programming. Computational
Intelligence 8(4), 1992. 601-623. Also available as
<ftp://ftp.fas.sfu.ca/pub/cs/theses/1993/GregSidebottomMSc.ps>.
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 eclipse_request@ecrc.de 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 eclipse_users@ecrc.de mailing list, send mail to
eclipse_request@ecrc.de.
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
(andre@eng.umd.edu).
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 garnet@cs.cmu.edu. 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].
CAL: NON-LINEAR
CAL was developed at ICOT (Institute for New Generation Computer
Technology) in a Japanese national project, Fifth Generation Computer
Project. CAL utilizes Buchberger algorithm to deal with linear and
non-linear algebraic equation constraints. See previous entries for more
details or contact Akira Aiba <aiba@icot.or.jp>
References:
[1] Ko Sakai, Akira Aiba. CAL : A Theoretical Background of Constraint
Logic Programming and Its Application. Journal of Symbolic Computation
(1989) 8, pp. 589 -- 603
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].
GDCC: NON-LINEAR
GDCC was developed at ICOT in a Japanese national project, Fifth
Generation Computer Project. GDCC utilizes Buchberger algorithm to
deal with linear and non-linear algebraic equation constraints.
Different from CAL, GDCC is a parallel CLP language based on cc
paradigm. There are two versions of GDCC, one is a system written in
KL1, a parallel logic programming language, that runs on a parallel
inference machine called PIM developed in the project, and the other
is a system written in KLIC that is a KL1 language processor for UNIX
workstations. See previous entry or contact Akira Aiba <aiba@icot.or.jp>
References:
[1] Satoshi Terasaki, David J. Hawley, Hiroyuki Sawada, Ken Satoh,
Satoshi Menju, Tarou Kawagishi, Noboru Iwayama, and Akira Aiba.
Parallel Constraint Logic Programming Language GDCC and Its Parallel
Constraint Solvers. International Conference on Fifth Generation
Computer Systems 1922, Tokyo
[2] Hiroyuki Sawada, Satoshi Terasaki, and Akira Aiba. Parallel
Computation of Groebner Bases on Distributed Memory Machines. Journal
of Symbolic Computation, Vol.18, No.3, pp.207--222, September 1994.
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 +49 89 7936 0037, fax +49 89 7936 0039.
E-mail prolog@mch.sni.de
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). Non-linear constraints can be
solver by interval approximation methods. 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
2005 Landings Drive 9, rue de Verdun, BP 85,
Mountain View, CA 94303. 94253 Gentilly Cedex, France
Phone: +415 390-9000 Phone: +33 1 4908 3500
e-mail: info@ilog.com e-mail: info@ilog.fr
URL: http://www.ilog.com 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 (life-users@prl.dec.com), send mail to
life-request@prl.dec.com. Send bug reports to life-bugs@prl.dec.com.
See also [1-5] PTF for more details.
NEWTON: NON-LINEAR [unavailable]
The constraint group at Brown University has developed a CLP language
called Newton to solve
- systems of nonlinear equations and inequalities
- unconstrained optimization
- constrained optimization
The language uses interval arithmetic and is based on a box-consistency
on various interval extensions. It is competitive with continuation
methods on their benchmarks, outperforms all interval methods we know
of, and has solved traditional benchmarks from numerical analysis
containing hundreds of variables. Contact Pascal Van Hentenryck
<pvh@cs.brown.edu>
References:
[1] F. Benhamou, D. McAllister, P. Van Hentenryck. CLP(Interval)
Revisited, in ILPS'94, Ithaca, NY, November 1994.
[2] P. Van Hentenryck, D. McAllister, D. Kapur. Solving Polynomial
System using A branch and Prune Approach. Forthcoming.
[3] P. Van Hentenryck, L. Michel. The Design and Implementation of
Newton. In CCP'95, Venice, Italy, May 1995.
NICOLOG: [COST FREE]
Nicolog is a CLP language with the capabilities of CLP(BNR) and most
of the capabilities of cc(FD). Constraints in Nicolog are compiled
into a generalization the indexical constraints found in cc(FD) and
clp(FD). This generalization of indexical constraints is called
projection constraints. Projection constraints add conditional
operators which allow the implementation of the cardinality, blocking
implication, and constructive disjunction constraints found in cc(FD).
Nicolog has a very simple implementation (5000 lines of Prolog for the
compiler and 5000 lines of C++ for the extended WAM emulator) and yet
runs as fast as emulator based CLP languages such as cc(FD) and CLP(BNR).
Moreover, the possibility of programming directly in projection
constraints makes Nicolog more flexible than other CLP systems. For
more information, go to <http://fas.sfu.ca/cs/research/groups/ISL/> or
<ftp://ftp.fas.sfu.ca/pub/css/esl/nicolog> or contact Greg Sidebottom
<gsidebot@mprgate.mpr.ca> or see
<ftp://ftp.fas.sfu.ca/pub/cs/theses/1993/GregSidebottomPhD.ps>.
OPBDP: [COST FREE]
opbdp is an implicit enumeration algorithm for solving linear 0-1
optimization problems, including a bunch of heuristics for selecting a
branching literal. Several preprocessing techniques (coefficient
reduction, fixing, equation detection). Preprocessed problem can
written to a file readable by CPLEX and lp_solve. Technical report
included. If your favorite linear-programming based solver fails on
your problem you might give opbdp a chance. Needs a C++ compiler which
supports templates. Contact Peter Barth (barth@mpi-sb.mpg.de).
ftp://ftp.mpi-sb.mpg.de/pub/guide/staff/barth/opbdp/
http://www.mpi-sb.mpg.de/~barth
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 omega@cs.umd.edu 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
oz@dfki.uni-sb.de. To join the Oz users mailing list, contact
oz-users-request@dfki.uni-sb.de.
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 formalisms. 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 <erbach@coli.uni-sb.de>
<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 prologia@prologianet.univ-mrs.fr
PROLOG IV: NON-LINEAR ? [COST COMMERCIAL]
Prolog IV is an ISO-compliant replacement for the Prolog III language.
It incorporates all the main features of Prolog III with some important
changes. Prolog IV allows programmers to express a wide variety of
constraints over real and rationnal numbers, integers (finite domains),
booleans and lists. In addition to expressing classical linear
programming problems on discrete and continuous quantities this permits
among other things the adressing of mixed real/integers problems and
the use of boolean operations to formalize constraint disjunctions.
The algorithms include a non-optimised algorithm for lists (different
from Prolog III), Gauss and Simplex algorithms for equations and linear
inequalities over rationals, and an interval method for approximate
solving of non-linear constraints over reals. The compiler is
integrated into a complete graphic programming environnment featuring
the following tools: project editor, multi-window text editor, grapher,
debugger, and on-line help.
Prolog IV is available on Unix Platforms (for about $11400) and
PC's with Windows (about $6400). These prices include two days of
training. For sales, contact Fabienne LELEU, Case 919 - Luminy 13288
Marseille cedex 09, France. Phone +33 91 26 86 36 - Fax +33 91 41 96
37. Email: prologia@prologianet.univ-mrs.fr For more information, you
can contact Andre Touraivane, Prologia Director of Research at the
same address, or email touraivane@prologianet.univ-mrs.fr
QUAD-CLP(R): NON-LINEAR [COST FREE]
QUAD-CLP(R) is an experimental constraint logic programming system
developed in the course of PhD research by Gilles Pesant. The CLP(R)
version 1.1 source code was used as a platform for the implementation.
The system provides a further treatment of non-linear _arithmetic_
constraints over the reals as opposed to delaying them unconditionally.
It concentrates on quadratic constraints, rewriting them so that they
can actually be decided upon or generating a conservative approximation
of them (while still delaying them), potentially improving control over
the computation. In both cases the idea is to fall back on linear
constraints, more easily handled.
QUAD-CLP(R)'s incomplete solver for non-linear constraints caters for
problems of respectable size which require a certain amount of
reasoning on these constraints but cannot afford the prohibitive cost
of a complete treatment. Contact Gilles Pesant <pesant@IRO.UMontreal.CA>
ftp://ftp.iro.umontreal.ca/pub/incognito/Logiciels/QUAD_CLP_R/
The file "qclpr_tar.Z" contains the whole package: executable file
(for Sparc/SunOS and Sparc/Solaris platforms), some rudimentary pages
information and a directory containing examples.
Reference:
[1] G. Pesant, M. Boyer. QUAD-CLP(R): Adding the Power of Quadratic
Constraints. Principles and Practice of Constraint Programming:
Proceedings of the Second International Workshop (Rosario, Orcas
Island, Washington, USA) (Alan Borning, ed.), Lecture Notes in Computer
Science, vol. 874, Springer-Verlag, Rosario, Orcas Island, Washington,
USA, 1994, pp. 95--108.
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
leapers@qdc.com. The body of the note should contain, as the first
line: GET <offer>. Or contact Joseph Elad (President) jelad@qdc.com
or Wenming Kuai wkuai@qdc.com. Phone USA (302) 798-0899, fax (302)
798-6813.
RISC-CLP(REAL): NON-LINEAR [unavailable]
RISC-CLP(Real) is a logic programming language with constraints over
the real numbers and exact arithmetic. The core-solver of the language
is the partial Quantifier Elimination Algorithm for real closed fields.
This is an improvement of the original quantifier elimination algorithm
due to Collins'. RISC-CLP also employs the Groebner Basis algorithm of
Buchberger. The system was intended as a study of a CLP solver based on
purely algebraic methods, generally too slow for such an application,
and is not meant for distribution. The interpreter and the solver are
implemented on top of the computer algebra system SACLIB in C language.
Contact Hoon Hong <Hoon.Hong@risc.uni-linz.ac.at> (SACLIB and GROEBNER
are available at ftp://ftp.risc.uni-linz.ac.at and
http://www.risc.uni-linz.ac.at)
References:
[1] H. Hong. Non-linear real Constrains in Constraint Logic
Programming. International Conference on Algebraic and Logic
Programming, Springer Lecture Notes in Computer Science 632, 201-212.
1992.
[2] H. Hong. RISC-CLP(Real): Constraint Logic Programming over Real
Numbers. Constraint Logic Programming: Selected Research. Eds. F.
Benhamou and A. Colmerauer. MIT Press. 1993.
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 <qobi@ai.mit.edu> 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 screamer-repository@cis.upenn.edu.
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 <bharat@cs.buffalo.edu>.
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 +46 8 752 15 02, fax +46 8 751 72 30, or send
email to sicstus-request@sics.se or sicstus@sics.se. Bug reports
and tech support questions should be sent to sicstus-bug@sics.se.
To subscribe to the users group and implementors mailing list, send
email to sicstus-users-request@sics.se.
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 publications@ai.mit.edu for more information). For
more information, send email to Chris Hanson
<cph@martigny.ai.mit.edu>.
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 <rauzy@labri.u-bordeaux.fr>. 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 <Marc.Corsini@labri.u-bordeaux.fr>.]
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 <Daniel.Diaz@inria.fr>,
INRIA Rocquencourt, FRANCE.
----------------------------------------------------------------
;;; *EOF*