CIMe[1] might be useful to solve the generated diophantine equations.

It also has AC unification, and it probably wouldn't be all that hard
to translate our code into OCaml.  I think CiME isn't supported
anymore.  Still it's worth considering.  It's quite large.  The source
distribution compiled effortlessly on Ubuntu.  That's about all I know
now.