From jampel@cs.city.ac.uk Mon Oct  3 16:01:44 EDT 1994
Article: 308 of comp.constraints
Path: cantaloupe.srv.cs.cmu.edu!das-news.harvard.edu!news2.near.net!MathWorks.Com!europa.eng.gtefsd.com!howland.reston.ans.net!agate!doc.ic.ac.uk!cs.city.ac.uk!not-for-mail
From: jampel@cs.city.ac.uk (Michael Jampel)
Newsgroups: comp.constraints
Subject: Glossary of constraints
Date: 3 Oct 1994 14:22:22 +0100
Organization: School of Informatics, City University
Lines: 70
Message-ID: <36p0ie$2jq@toves.cs.city.ac.uk>
NNTP-Posting-Host: toves.cs.city.ac.uk

We were asked for a glossary of the field. Here is a first attempt.
Thanks to Patrick Prosser and Thomas Schiex for help.

I would like to put references to key papers in here (if you think it
is a good idea) but am worried: if, out of ignorance, I put in
references for some but not others, people might be offended.

Comments to me by e-mail please, then I will post a new version if you
think it is a good idea.

Michael Jampel

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
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
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
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
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 (*)
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


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