Masami Takikawa and Lawrence A. Crowl, "Multiworld Augmented Term Rewriting", Technical Report 94-60-06, Department of Computer Science, Oregon State University, Corvallis, Oregon, 97331-3202, November 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 possible values that may satisfy the constraints. The selection of a possible 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.