Specification and Generation of Constraint Satisfaction Systems

Abstract......Page 4
Contents......Page 5
Dedication......Page 7
1 Introduction......Page 9
Assignment vs Equality......Page 10
Scope of the Research......Page 13
Problem Solving vs Constraint Programming......Page 15
Limitations of Existing Constraint Languages......Page 16
Proposed Solution......Page 19
Constraint Satisfaction Techniques......Page 22
Local  Propagation......Page 23
Relaxation......Page 26
Propagating Degrees of Freedom......Page 28
Redundant Views......Page 30
Graph Transformation......Page 32
Equation Solving......Page 33
Constraints Involving Time......Page 38
Default Values......Page 40
Summary......Page 41
Term Rewriting......Page 43
Algebra & Arithmetic......Page 46
Purdue Equational Interpreter......Page 47
Augmented Term Rewriting......Page 49
Binding Values to Atoms......Page 51
Name Spaces......Page 54
Labels......Page 55
Defining New Datatypes......Page 56
Constraints on Datatypes......Page 59
Variables & Declarations......Page 61
Types......Page 62
Bertrand......Page 65
Evaluation Order......Page 68
Comparison to Prolog......Page 69
Syntax......Page 72
Semantics......Page 74
Standard Term Rewriting......Page 75
Augmented Term Rewriting......Page 77
Differences......Page 81
Discussion......Page 82
Expressiveness......Page 83
Soundness......Page 84
Confluence......Page 85
5 Existing Constraint Languages......Page 88
Sketchpad......Page 89
ThlngLab......Page 91
TK!Solver......Page 96
Juno......Page 99
Languages with Symbolic Techniques......Page 100
Magritte......Page 101
Ideal......Page 102
Similar Systems......Page 104
Solving Linear Equations......Page 105
Interesting Answers......Page 107
Booleans......Page 108
Reasoning with Equations......Page 109
Word  Problems......Page 111
Electrical Circuits......Page 113
Input & Output......Page 117
Graphics......Page 118
Diagrams......Page 121
Describing Graphic Objects......Page 124
Streams......Page 128
Pattern Matching......Page 130
Instantiating Rules......Page 133
Types & Operators......Page 135
Preprocessing Rules......Page 136
Compilation......Page 138
Compiling simple Arithmetic Constraints......Page 139
Why Lambda......Page 141
Compiling Higher Order Constraints......Page 143
Code Generation & Optimization......Page 146
Execution on Parallel Processors......Page 147
Dataflow......Page 150
Limitations of the Equation Solver......Page 152
Summary & Contributions......Page 154
Computational Completeness......Page 155
Extensibility......Page 156
Efficiency......Page 157
Interaction......Page 158
More Powerlul Equation Solvers......Page 159
Acceptability of Non-procedural Languages......Page 160
BEEP......Page 162
Simultaneous Equations......Page 165
More Word Problems......Page 166
Temperatures......Page 167
BAG......Page 168
Diagrams......Page 169
Graphics Appflcatlons......Page 171
Interpreter in Scheme......Page 174
Biblio......Page 185
Index......Page 188