# The algebra of Krom logic programs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 16 references that are in the map.
- First posted on arXiv 14 Jun 2026.

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

- [Logic program proportions](https://mlsanity.com/paper/1809.09938/) (2018)
- [Sequential composition of propositional logic programs](https://mlsanity.com/paper/2009.05774/) (2020)
- [Sequential composition of answer set programs](https://mlsanity.com/paper/2104.12156/) (2021)
- [Set-like operations on propositional logic programs](https://mlsanity.com/paper/2605.03613/) (2026)

## Abstract (arXiv)

This paper investigates the algebraic structure of Krom logic programs, consisting only of facts and rules with at most one body atom. We show that sequential composition endows the class of Krom programs with a natural monoid structure and that this structure admits rich algebraic extensions to Krom seminearrings, Krom quemirings, Krom-Conway seminearrings, and Krom-Conway omegaseminearrings. Furthermore, we establish explicit generating sets and canonical decompositions, study the associated ω-operator, characterize the Kleene star in graph-theoretic terms, and relate finite Krom monoids to transformation monoids and finite-state automata. These results provide new connections between logic programming, algebraic automata theory, and algebraic graph theory.