Unified Computation over Generalized Semirings

69 concepts49 papers1 proposal

Imagine you are writing a program to find the shortest path between two cities on a map. Your code loops through the roads, adds their lengths together to find total path distances, and keeps the minimum value found.

Now, imagine a completely different problem: you want to find the most reliable path through a network, where each road has a probability of survival, and you want to maximize the product of these probabilities. Finally, imagine a third problem: you simply want to know if any path exists at all, using Boolean logic.

Traditionally, these would be treated as three distinct algorithms. But if you look closely at their control flow, they are identical. They all traverse a graph, accumulate weights along a path, and aggregate those weights to select a result. The only things that change are the data types and the arithmetic operations.

This deep structural equivalence is the core insight behind generalized semiring abstraction. By decoupling the control flow of an algorithm from its underlying arithmetic, a single computational engine can solve problems across graph analytics, relational databases, formal logic, and machine learning.


The Anatomy of a Semiring

A semiring is an algebraic structure consisting of a set of values and two binary operations: an "additive" operator ($\oplus$) and a "multiplicative" operator ($\otimes$). Crucially, these do not have to be standard addition and multiplication. They just need to satisfy a few intuitive properties, most notably that $\otimes$ distributes over $\oplus$ (just as $a \times (b + c) = (a \times b) + (a \times c)$).

When we apply this to paths, sequences, or logical deductions, the operators take on specific roles:

  • The multiplicative operator ($\otimes$) accumulates weights along a single path or conjunction of steps.
  • The additive operator ($\oplus$) aggregates weights across alternative paths or disjunctions.
Computational Domain Semiring Name Set $\oplus$ (Aggregate Across Paths) $\otimes$ (Accumulate Along a Path)
Standard Arithmetic Real / Linear $\mathbb{R}$ $+$ (Sum) $\times$ (Product)
Shortest Path Tropical $\mathbb{R} \cup \{\infty\}$ $\min$ (Minimum) $+$ (Addition)
Connectivity Boolean $\{0, 1\}$ $\lor$ (Logical OR) $\land$ (Logical AND)
Network Bandwidth Bottleneck $\mathbb{R}^+$ $\max$ (Maximum) $\min$ (Minimum)

Because the distributive property holds across all these pairs, any algorithm that relies on distributing accumulation over aggregation will work perfectly, regardless of which row of the table you choose.


Graph Traversals as Matrix Multiplication

The most direct application of this abstraction is treating graph algorithms as sparse linear algebra. A graph can be represented as an adjacency matrix, where rows and columns correspond to vertices, and cell values represent edge weights.

In standard linear algebra, multiplying two matrices computes a dot product for each cell:

$$C_{ij} = \sum_k A_{ik} \times B_{kj}$$

If we swap the standard arithmetic semiring for the Tropical semiring, the formula transforms into:

$$C_{ij} = \min_k (A_{ik} + B_{kj})$$

This is exactly one step of a shortest-path calculation. Multiplying the adjacency matrix by itself repeatedly computes the shortest paths across the entire graph.

As formalized by the authors of Mathematical Foundations of the GraphBLAS, this equivalence means that a single, highly optimized sparse matrix multiplication engine can execute hundreds of diverse graph algorithms. Tim Mattson et al. and Jeremy Kepner et al. argue that this abstraction provides a clean separation of concerns: hardware vendors can focus on optimizing low-level sparse matrix primitives, while algorithm designers can build versatile graph applications by simply swapping the underlying semiring.

Standard Matrix Multiplication:
[ Row i ]  -->  (A_i1 * B_1j) + (A_i2 * B_2j) + ...  -->  Sum of Products

Tropical Matrix Multiplication:
[ Row i ]  -->  min(A_i1 + B_1j, A_i2 + B_2j, ...)  -->  Min of Sums (Shortest Path)

This framework scales seamlessly from single machines to massive distributed systems. Ariful Azad et al. demonstrate that template-based semiring abstractions allow distributed graph libraries to execute complex, heterogeneous operations without altering the underlying parallel communication logic. Furthermore, Enrique Fita Sanmartín et al. show that this algebraic path framework can smoothly interpolate between entirely different graph metrics—such as shortest paths and commute costs—by defining a continuous family of log-norm distances within the semiring structure. Even complex metrics like betweenness centrality can be parallelized effectively by replacing traditional semirings with commutative monoids to track path lengths and counts simultaneously, as shown by Edgar Solomonik et al..


The Duality of Databases and Matrices

If graph traversals are just matrix multiplications, and database tables are fundamentally collections of sparse records, then relational databases can be transformed into powerful linear algebra engines.

Consider a standard SQL query that joins two tables and aggregates the result:

SELECT A.row, B.col, SUM(A.val * B.val)
FROM A JOIN B ON A.col = B.row
GROUP BY A.row, B.col

Mathematically, this relational sequence is identical to matrix multiplication. The JOIN represents the multiplicative operator ($\otimes$), and the SUM aggregation represents the additive operator ($\oplus$).

Jeffrey Xu Yu et al. and Kangfei Zhao et al. exploit this duality by introducing specialized relational operators (such as MM-join and MV-join) directly into Relational Database Management Systems (RDBMSs). These operators treat database tables as sparse matrices, allowing standard relational engines to execute graph analytics like PageRank or Floyd-Warshall at native speeds.

This algebraic bridge works in both directions:

  1. Matrix Operations to Relational Algebra: The compiler framework SPORES, designed by Yisu Remy Wang et al., translates linear algebra expressions into relational algebra. By treating matrices as relations, the compiler can use database optimization techniques like equality saturation to discover fine-grained rewrites that are completely invisible at the matrix level.
  2. Relational Queries to Matrix Operations: Conversely, Shaleen Deep et al. demonstrate that complex database "join-project" queries can be evaluated using fast Boolean matrix multiplication. Instead of explicitly materializing massive intermediate tables, the system counts connections through matrix math, avoiding memory explosions.

By embedding these abstractions into modern code-generating databases, systems can seamlessly unify tabular data and multi-dimensional arrays. Maximilian E. Schüle et al. showed that by mapping array indices to primary keys and array values to attributes, a relational query optimizer can execute complex linear algebra tasks faster than specialized array databases.


Algebraic Logic Programming and Neuro-Symbolic AI

The power of semiring abstraction extends beyond numbers and matrices into formal logic and artificial intelligence. In traditional logic programming (like Prolog), facts are discrete and binary: a statement is either true ($1$) or false ($0$).

By replacing binary truth values with elements from an arbitrary commutative semiring, Angelika Kimmig et al. introduced aProbLog (Algebraic Prolog). In this generalized framework, logical facts are annotated with semiring labels. The rules of logic map directly to semiring operations:

  • Conjunction ($\land$): The multiplication operator ($\otimes$) combines labels along a chain of deductions within a single possible world.
  • Disjunction ($\lor$): The addition operator ($\oplus$) aggregates labels across alternative, independent proofs.
Traditional Logic:   Fact A (True)  AND Fact B (True)  --> True
Probabilistic Logic: Fact A (0.8)   AND Fact B (0.5)   --> 0.8 * 0.5 = 0.4
Shortest-Path Logic: Fact A (Cost 4) AND Fact B (Cost 2) --> 4 + 2 = 6

As synthesized by Robin Manhaeve et al., this abstraction proves that discrete logic, continuous probability distributions, and neural network outputs are not fundamentally different paradigms—they are mathematically identical when viewed through the lens of Algebraic Model Counting (AMC). By simply swapping the underlying semiring, the exact same logical execution graph can find the most probable explanation, perform sensitivity analysis, or compute gradients.

To make this practical for machine learning, Jaron Maene et al. introduced the algebraic gradient ($\nabla$AMC). This framework provides a unified backpropagation algorithm that operates across different semirings, allowing neuro-symbolic reasoning engines to compute gradients, Shannon entropy, and information gain orders of magnitude faster than standard deep learning frameworks like PyTorch or Jax.


Unifying Sequences and Automata

Long before its adoption in databases and neuro-symbolic AI, semiring abstraction was a cornerstone of sequence modeling and natural language processing. Weighted Finite-State Transducers (WFSTs), popularized by Fernando Pereira et al., rely on semirings to decouple graph-search logic from specific scoring metrics.

When a speech recognition or translation system searches for the best sentence, it traverses an alignment graph. By swapping the semiring, the same traversal engine can switch from Viterbi decoding (finding the single most likely sequence using a Tropical semiring) to calculating partition functions (summing the probabilities of all possible sequences using a Real semiring).

This modularity is heavily leveraged in translation decoders like cdec. Adam Lopez et al. implemented a formal semiring framework within cdec to support both decoding and discriminative training inside a single engine. Similarly, Corinna Cortes et al. introduced Rational Kernels, which extend kernel-based machine learning (like SVMs) to variable-length sequences. By using semiring-annotated transducers, they created a unified way to compute similarity scores over complex data structures like speech lattices and biological sequences.

To support these diverse applications, single-author toolkits have historically driven the field forward by prioritizing clean algebraic abstractions. Lee Hetherington developed the MIT FST toolkit using generalized semirings to unify speech and language representations, while Julien Quint provided generalized algorithms for testing the equivalence of transducers regardless of their underlying weight system. Beyond sequences, Maciej Besta demonstrated that even complex graph mining tasks—like finding cliques and motifs—can be completely decoupled from low-level data layouts by expressing them as abstract set algebras.


Why It Works

The reason generalized semiring abstraction is so widely successful across graphs, databases, logic, and language comes down to a simple software engineering principle: the separation of topology from arithmetic.

Whether you are navigating a social network, joining relational tables, evaluating a logical formula, or decoding a sentence, the structural skeleton of the computation is a graph of possibilities. The distributive law of semirings guarantees that you can push aggregations inside accumulations, optimizing the traversal path once, and then reuse that exact same optimized path for any data type in existence. By programming to the abstraction of a semiring, we write code that is fundamentally reusable, highly parallelizable, and mathematically unified.

Key Foundational Work

Weighted Rational Transductions and their Application to Human Language Processing (1994) — contributed 1 concept elements to this direction.
Rational Kernels (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_algebraic_logic_programming_fe602a1e,
  title = {algebraic logic programming},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algebraic-logic-programming/rdr_fe602a1e6ff74979b8ab1550279905a1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_algebraic_logic_programming_fe602a1e_v1,
  title = {algebraic logic programming},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algebraic-logic-programming/rdr_fe602a1e6ff74979b8ab1550279905a1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake