Abstract

Many artificial intelligence problems are formulated as backtracking tree searches. In general, these problems have exponential time complexity, and many researchers have concentrated on developing practical tree-pruning techniques to improve the efficiency of the search algorithm. Consistent labeling (CL) techniques (variously known as constraint satisfaction and forward checking techniques) use the relational constraints of the problem in local graph operations to reduce the complexity of the search tree. The appropriate data structures for some CL operations are Boolean tables which can be manipulated by Boolean matrix algebraic techniques.¹ For some problems, their implementation on sequential machines may be impractical.

© 1987 Optical Society of America