Multiworld Augmented Term Rewriting
Masami Takikawa, Lawrence A. Crowl · 1994
Augmented term rewriting (ATR) is a simple, uniform, and extensible computational model for constraint programming. Unfortunately, ATR cannot solve combinatorial constraint satisfaction problems (CCSPs). To enable solution of CCSPs, we introduce (don''t know) nondeterminism into ATR via the choice expression, which identifies a set of values that may satisfy the constraints. The selection of a value from the expression represents one of many possible worlds in which the constraints may be satisfied. We show that our extended ATR, multiworld augmented term rewriting (MATR), is capable of expressing CCSPs concisely and readably via examples and via our experience with a significant application. We also show that an implementation of MATR can use the efficient constrain-and-generate technique for solving CCSPs, and describe our prototype implementation.