# Algebraic anti-unification

arXiv: https://arxiv.org/abs/2407.15510 · HTML: https://mlsanity.com/paper/2407.15510/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 47 references that are in the map.
- First posted on arXiv 22 Jul 2024.

## Builds on (most cited first, 13 of 13)

- [Inductive logic programming at 30: a new introduction](https://mlsanity.com/paper/2008.07912/) (2020)
- [Learning programs by learning from failures](https://mlsanity.com/paper/2005.02259/) (2020)
- [Inductive logic programming at 30](https://mlsanity.com/paper/2102.10556/) (2021)
- [babble: Learning Better Abstractions with E-Graphs and Anti-Unification](https://mlsanity.com/paper/2212.04596/) (2022)
- [Analogical proportions](https://mlsanity.com/paper/2006.02854/) (2020)
- [Logic program proportions](https://mlsanity.com/paper/1809.09938/) (2018)
- [Learning Quick Fixes from Code Repositories](https://mlsanity.com/paper/1803.03806/) (2018)
- [Omission-based Abstraction for Answer Set Programs](https://mlsanity.com/paper/2004.01410/) (2020)
- [Anti-unification and Generalization: A Survey](https://mlsanity.com/paper/2302.00277/) (2023)
- [E-Generalization Using Grammars](https://mlsanity.com/paper/1403.8118/) (2014)
- [Analogical proportions in monounary algebras](https://mlsanity.com/paper/2208.06829/) (2022)
- [Generalization-baed similarity](https://mlsanity.com/paper/2302.10096/) (2023)
- [Analogical proportions II](https://mlsanity.com/paper/2405.13461/) (2024)

## Abstract (arXiv)

Abstraction is key to human and artificial intelligence as it allows one to identify common structure in otherwise distinct objects or situations. Anti-unification (or generalization) is the branch of theoretical computer science and artificial intelligence that studies abstraction and has found applications in areas such as inductive logic programming, program synthesis, and analogy-making. To date, anti-unification has been studied almost exclusively from a syntactic perspective. In this paper, we initiate an algebraic (i.e. semantic) theory of anti-unification in the general setting of universal algebra, thereby extending anti-unification from term-based representations to arbitrary algebras and beyond equational theories. In particular, we introduce the notions of algebraic generalization ordering and minimally general generalization, establish basic structural properties, prove compatibility with homomorphisms and isomorphisms, and investigate computability in finite unary algebras and finite algebras via automata-theoretic methods.