Termination and Completion modulo Associativity, Commutativity and Identity


Rewriting with associativity, commutativity and identity has been an open problem for a long time. In 1989, Baird, Peterson and Wilkerson introduced the notion of constrained rewriting, to avoid the problem of non-termination inherent to the use of identities. We build up on this idea in two ways: by giving a complete set of rules for completion modulo these axioms; by showing how to build appropriate orderings for proving termination of constrained rewriting modulo associativity, commutativity and identity.

full paper