Acronyms

This page explains what various acronyms stand for, without much detail on any of them.

• 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)
• ATMS -- Assumption-Based Truth-Maintenance System
• BJ -- Backjumping (*)
• BM -- Backmarking (*)
• BMJ -- Backmarking with backjumping (*)
• CBJ -- Conflict-Directed Back-Jumping (*)
• CC(FD) -- Concurrent Constraint Programming over Finite Domains
• CCP -- Concurrent Constraint Programming
• CDI -- Context Dependent Interchangeability
• CHR -- Constraint Handling Rules (Fruehwirth)
• CIP -- Constraint Imperative 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
• CLP -- Constraint Logic Programming
• CNG -- Complete No-Good
• COP -- Constrained Optimization Problem
• CSP -- Constraint Satisfaction Problem
• DB -- Dynamic Backtracking (*)
• DBT -- Dynamic backtracking
• DCSP -- Dynamic CSP
• DVO -- Dynamic Variable Ordering heuristic (*)
• DnAC -- Dynamic arc-consistency
• FC -- Forward-checking (*)
• FF -- First Fail principle: choose the variable with the smallest domain as the next instantiation (*)
• FI -- full interchangeability
• FLA -- Full Look Ahead
• FOF -- Factor Out Failure
• FSL -- Full Shallow learning (*)
• GBJ -- Graph based Backjumping (*)
• 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
• MNG -- Minimal No-Good
• NC -- Node consistency (see AC). Not much used
• NG -- No-Good
• NI -- neighborhood interchangeability
• NLP -- Non-Linear Programming. (Natural Language Processing elsewhere)
• NPI -- neighborhood partial interchangeability
• NR -- Nogood recording (*)
• NSUB -- Neighborhood Substitutability
• OR -- Operations Research. see newsgroup sci.op-research
• PC -- Path-Consistency. Not much used
• PCSP -- Partial CSP
• PI -- partial interchangeability
• PLA -- Partial Look Ahead
• RFLA -- Real Full Look Ahead
• SAT -- The problem of deciding if a given logical formula is SATisfiable.
• SUB -- Substitutability
• TMS -- Truth-Maintenance System
• TSP -- Travelling Salesman Problem; a typical very hard problem
• VAD -- value assignment delay (*)

(*) Denotes techniques/heuristics for improving the efficiency of constraint satisfaction
Thanks to Michael Jampel, Patrick Prosser, Thomas Schiex, Berthe Choueiry, Alan Borning, Warwick Harvey, Thom Fruehwirth.