2021/04/12 by Valeriu Motroi, Motroi, Valeriu, Ştefan Ciobâcă +1
Computer Science · Mathematics · #Artificial Intelligence in Games #Commutative Algebra and Its Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Performance (cs.PF)
paper · pdf · doi:10.48550/arxiv.2104.05200
openalex publication_date 2021/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We implement four algorithms for solving linear Diophantine equations in the naturals: a lexicographic enumeration algorithm, a completion procedure, a graph-based algorithm, and the Slopes algorithm. As already known, the lexicographic enumeration algorithm and the completion procedure are slower than the other two algorithms. We compare in more detail the graph-based algorithm and the Slopes algorithm. In contrast to previous comparisons, our work suggests that they are equally fast on small inputs, but the graph-based algorithm gets much faster as the input grows. We conclude that implementations of AC-unification algorithms should use the graph-based algorithm for maximum efficiency.