  Parity constraints, common in application domains such as circuit
verification, bounded model checking, and logical cryptanalysis, are not
necessarily most efficiently solved if translated into conjunctive normal form.
Thus, specialized parity reasoning techniques have been developed in the past
for propagating parity constraints. This paper studies the questions of
deciding whether unit propagation or equivalence reasoning is enough to achieve
full propagation in a given parity constraint set. Efficient approximating
tests for answering these questions are developed. It is also shown that
equivalence reasoning can be simulated by unit propagation by adding a
polynomial amount of redundant parity constraints to the problem. It is proven
that without using additional variables, an exponential number of new parity
constraints would be needed in the worst case. The presented classification and
propagation methods are evaluated experimentally.
