Arc consistency for factorable relations

✍ Scribed by Mark Perlin

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 610 KB
• Volume: 53
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(92)90077-b

✦ Synopsis

Perlin, M., Arc consistency for factorable relations (Research Note), Artificial Intelligence 53 (1992) 329-342.

An optimal arc consistency algorithm AC-4 was given by Mohr and Henderson [8]. AC-4 has cost O(ed2), and cost (nd 2) for scene labelling. Although their algorithm is indeed optimal, under certain conditions a constraint satisfaction problem can be transformed into a less complex problem. In this paper, we present conditions and mechanisms for such representational transformations, and show how to factor relations into more manageable components. We describe how factorization can reduce AC-4's cost to O(ed), and apply this result to RETE match. Further, with our factorization, the cost of scene labelling is reduced to O(nd).