Title: Algebraic Anti-Unification

Abstract:

The capacity to identify shared structures among disparate entities or scenarios is fundamental to both human cognition and artificial intelligence, serving as the cornerstone of abstraction. Anti-unification, also known as generalization, constitutes the branch of theoretical computer science and AI dedicated to the study of this phenomenon. It has already demonstrated utility in diverse fields, including analogy-making, program synthesis, and inductive logic programming. Historically, research into anti-unification has been confined largely to syntactic approaches. This work, however, lays the groundwork for an algebraic, or semantic, theory of anti-unification within the broader framework of universal algebra. By doing so, it expands the scope of anti-unification beyond term-based representations to encompass arbitrary algebras and general equational theories. Specifically, we define the concepts of algebraic generalization ordering and minimally general generalization, outlining their fundamental structural characteristics. We further demonstrate their compatibility with homomorphisms and isomorphisms, and explore computability issues within finite unary algebras and finite algebras using automata-theoretic techniques.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC