Abstract: Based on the principle that cartesian product compression could effectively reduce the scale of negative table constraint, we proposed an efficient algorithm STRC-N to maintain generalized arc consistency on compressed negative table, which solved the problem of traversal of all tuples and low efficiency in the process of maintaining generalized arc consistency on negative table constraint. Experimental results show that when the compression rate of negative table is large, the new algorithm has higher efficiency and better performance than the mainstream negative table constraint processing algorithm due to the reduction of table size. Thus, the negative table constraints processing algorithm is improved.

Key words: constraint satisfaction problem, negative table constraint, table compression, arc consistency