  In this work we target the problem of provably computing the equivalence
between two programs represented as dataflow graphs. To this end, we formalize
the problem of equivalence between two programs as finding a set of
semantics-preserving rewrite rules from one into the other, such that after the
rewrite the two programs are structurally identical, and therefore trivially
equivalent. We then develop the first graph-to-sequence neural network system
for program equivalence, trained to produce such rewrite sequences from a
carefully crafted automatic example generation algorithm. We extensively
evaluate our system on a rich multi-type linear algebra expression language,
using arbitrary combinations of 100+ graph-rewriting axioms of equivalence. Our
system outputs via inference a correct rewrite sequence for 96% of the 10,000
program pairs isolated for testing, using 30-term programs. And in all cases,
the validity of the sequence produced and therefore the provable assertion of
program equivalence is computable, in negligible time.

Machine Learning;Formal Languages and Automata Theory;Machine Learning