Arc consistency for factorable relations

An optimal arc consistency algorithm AC-4 was given by R. Mohr and T.C. Henderson (1986). AC-4 has costO(ea²), and cost(na²) for scene labeling. Although their algorithm is indeed optimal, under certain conditions a constraint satisfaction problem can be transformed into a less complex problem. Conditions and mechanisms are presented for such transformations, and it is shown how to factor relations into more manageable components. A description is given of how factorization can reduce AC-4´s cost to O(ea), and this result is applied to RETE match