💻 computer science

An Elementary Proof of the FMP for Kleene Algebra

This paper presents a novel, elementary proof of the finite model property for Kleene Algebra using transformation automata, which establishes the completeness of Kleene Algebra with respect to finite relational models and subsumes previous results by Palka, Pratt, and Kozen.

Original authors: Tobias Kappé

Published 2026-03-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tobias Kappé

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery: Are two computer programs actually doing the same thing?

In the world of computer science, programs are often built from simple blocks: doing one thing, then another (sequencing), choosing between paths (branching), or repeating a task (looping). Mathematicians call the rules governing these blocks Kleene Algebra. It's like a universal grammar for how programs behave.

For decades, we've known a powerful rule: If two programs are equivalent according to the laws of Kleene Algebra, they are equivalent in every possible scenario. But the reverse question was tricky: If two programs behave the same way in every specific scenario we can build, does that mean they are equivalent according to the universal laws?

This paper, written by Tobias Kappé, answers "Yes" with a fresh, simpler approach. Here is the story of how he did it, explained without the heavy math jargon.

The Problem: The Infinite Library vs. The Finite Workshop

Imagine you have a massive library of all possible programs (the "Language Model"). Proving two programs are equal here is the gold standard. But this library is infinite and hard to check.

However, computer scientists often work in smaller, finite workshops:

The Relational Workshop: Where programs are just maps connecting "Start" states to "End" states.
The Finite Workshop: Where the number of possible states is limited (like a game with a fixed number of levels).

Previously, we knew that if two programs are equal in the Finite Workshop, they are equal in the Infinite Library. But the proof for this was like trying to climb a mountain using a complex, winding path involving heavy machinery (minimality and bisimilarity of automata). It worked, but it was hard to understand and teach.

The New Path: The "Transformation" Map

Kappé's paper offers a new, "elementary" (meaning simpler and more direct) path up the mountain. Instead of using heavy machinery, he uses a clever tool called Transformation Automata.

Here is the analogy:

1. The Original Program as a Recipe

Think of a regular expression (a program) as a recipe for a cake.

a is "add flour."
b is "add sugar."
a + b is "add flour OR sugar."
a* is "add flour as many times as you want."

2. The Transformation Automaton as a "State Machine"

Imagine you have a robot that follows this recipe. As the robot reads the recipe, it changes its internal state.

If it reads a, it moves from "State 1" to "State 2."
If it reads b, it moves from "State 2" to "State 3."

Now, Kappé introduces a Transformation Automaton. This isn't just a robot following a single path; it's a robot that tracks how the whole group of states changes.

Instead of asking "Where does the robot go if I press 'a'?", we ask "How does the entire map of the robot's possible locations change if I press 'a'?"

It's like looking at a map of a city. Instead of tracking one car, you are tracking how the entire traffic flow shifts when a traffic light turns green.

3. The "Finite" Trick

The brilliant part of Kappé's proof is realizing that for any specific recipe (program), the number of ways the "traffic flow" (the transformation) can change is finite. Even though the recipe could theoretically run forever, the patterns of how it rearranges the states repeat in a limited set of ways.

He builds a Finite Model (a small, manageable workshop) based on these transformation patterns.

If two recipes produce the exact same traffic flow patterns in this small workshop, they are effectively the same recipe.
If they are different in the workshop, they are different in the infinite library.

Why This Matters

1. It's Simpler:
Previous proofs were like trying to prove a theorem by building a skyscraper. Kappé's proof is like building a sturdy bridge. It relies on basic algebra (solving systems of equations) rather than complex geometric comparisons of machines.

2. It's More Intuitive:
By using "Transformation Automata," the proof connects the abstract math directly to the idea of how programs transform data. It feels more like watching a machine work and less like solving a riddle.

3. It Unifies the Theory:
The paper shows that the "Finite Workshop," the "Relational Workshop," and the "Infinite Library" are all perfectly aligned. If you can prove two programs are equal in a small, finite world, you have proven they are equal everywhere.

The Takeaway

Think of this paper as a new, clearer map for a territory that was previously foggy. Tobias Kappé showed us that we don't need to check every single infinite possibility to know if two programs are the same. We just need to look at how they rearrange a finite set of states.

If two programs shuffle a deck of cards in the exact same way in a small, finite game, they will shuffle any deck of cards in the exact same way in the real world. This simple, powerful insight makes it easier for computer scientists and software engineers to verify that their code is correct, safe, and bug-free.

1. Problem Statement

Kleene Algebra (KA) is a foundational algebraic structure used to reason about the equivalence of regular expressions and programs. A central question in KA theory is determining which equations are provable using the axioms of KA versus which are only true in specific models (e.g., relational models or finite models).

Key concepts include:

Completeness: An equation $e = f$ is provable in KA ( $e \equiv f$ ) if and only if it holds in a specific class of models.
Kozen's Theorem (1994): KA is complete with respect to the language model (regular languages). If an equation holds for all regular languages, it is provable in KA.
Pratt's Observation (1980): KA is complete with respect to relational models (relations on a set).
Palka's Theorem (2005): KA possesses the Finite Model Property (FMP). If an equation holds in all finite KAs, it is provable in KA.

The Gap: While these results are known, the standard proofs for completeness (Kozen) and the FMP (Palka) rely on complex machinery involving the minimality of automata, bisimilarity, or cyclic proof systems. Palka noted that an "independent proof" of the FMP using purely logical or algebraic tools, without relying on Kozen's theorem or automata minimality, was an open challenge. This paper aims to provide such a proof and unify the understanding of KA's model theory.

2. Methodology

The author employs a novel algebraic approach centered on Transformation Automata and Linear Systems over Kleene Algebras, avoiding the traditional reliance on automata minimization or bisimulation.

Core Techniques:

Transformation Automata:
- Instead of analyzing the minimal automaton for a language, the paper utilizes the transformation automaton of a given automaton $A$ .
- The states of this transformation automaton are relations on the states of $A$ (specifically, the set of all possible state transformations induced by reading words).
- This structure forms a monoid under relational composition.
Lifting to a Finite KA:
- The power set of the monoid of relations, $P(R(Q))$ , naturally forms a star-continuous Kleene Algebra.
- For any regular expression $e$ , the author constructs a specific finite KA, denoted $K_e$ , derived from the transformation automaton of the Antimirov automaton for $e$ .
- This $K_e$ is finite because the set of reachable relations in the transformation automaton is finite.
Linear Systems and Least Solutions:
- The paper utilizes the fact that KAs allow for the solution of linear systems (systems of equations of the form $x = Mx + b$).
- Theorem 4.5 establishes that least solutions to linear systems over a finite set of variables can be computed algebraically.
- This allows the construction of "solutions" to automata (expressions representing the language accepted from a state) without needing to minimize the automaton.
Antimirov's Construction:
- The paper uses Antimirov's construction to generate a finite automaton $A_e$ for any expression $e$ .
- Crucially, the proof does not require proving that $A_e$ is minimal or that the expression is equivalent to the solution of its Antimirov automaton in the traditional sense. Instead, it uses the algebraic properties of the transformation automaton of $A_e$ .

3. Key Contributions

A. Unification of Model Theories (Section 3)

The paper first establishes a comprehensive map of the relationships between different classes of KA models:

Language Models ( $\mathcal{L}$ )
Star-continuous KAs ( $\mathcal{C}$ )
Relational Models ( $\mathcal{R}$ )
Finite KAs ( $\mathcal{F}$ )
Finite Relational Models ( $\mathcal{FR}$ )

The author proves that completeness with respect to any one of these classes implies completeness with respect to all others. Specifically, the paper introduces the Finite Relational Model Property (FRMP): If an equation holds in all finite relational KAs, it is provable in KA. This subsumes both Palka's FMP and Pratt's Relational Model Property.

B. New Elementary Proof of the Finite Model Property (Section 7)

This is the paper's main contribution. The author provides a self-contained proof that if $e = f$ holds in all finite KAs, then $e \equiv f$ (is provable in KA).

The Construction: For any expression $e$ , a finite KA $K_e$ is constructed based on the transformation automaton of the Antimirov automaton for $e$ .
The Logic:
1. If $e = f$ holds in all finite KAs, it must hold in $K_e$ .
2. The interpretation of $f$ in $K_e$ can be bounded above by a sum of expressions derived from solving the transformation automaton of $e$ with specific accepting states (Lemmas 7.6 and 7.7).
3. Algebraic manipulation shows that if $e$ and $f$ are equivalent in $K_e$ , then $f \leq e$ and $e \leq f$ in the general KA theory, implying $e \equiv f$ .
Distinction: Unlike previous proofs, this method does not rely on:
- Minimality of automata.
- Bisimilarity arguments.
- Kozen's completeness theorem (it proves FMP independently, which then implies Kozen's theorem).
- Cyclic proof systems.

4. Results

Theorem 2.11 (FMP): Proven via the new algebraic construction. If $F \models e = f$ , then $e \equiv f$ .
Theorem 2.12 (Relational Model Property): Proven as a consequence of the FMP and the FRMP.
Theorem 2.14 (Language Completeness): Re-derived as a consequence of the FMP.
Corollary 3.6 (Finite Relational Model Property): Established that finite relational models are sufficient to characterize KA.
Formalization: All results have been formalized in Coq, ensuring the correctness of the algebraic manipulations and the construction of the finite models.

5. Significance

Simplicity and Accessibility: The proof is described as "elementary" because it avoids the heavy machinery of automata minimization and bisimulation, which are often difficult for students to grasp. It relies instead on standard algebraic properties of KAs (linear systems) and finite monoids.
Independence: It provides a standalone proof of the FMP that does not depend on Kozen's theorem, fulfilling a specific request by Palka for a proof based on "purely logical tools."
Pedagogical Value: The paper serves as a self-contained reference for graduate students, offering a clear, step-by-step derivation of KA's model theory.
Future Directions: The techniques open new avenues for investigating:
- Representation Theory: Whether every KA can be represented as a subalgebra of a relational KA.
- Concurrent Kleene Algebra (CKA): Whether these algebraic transformation techniques can be adapted to prove completeness for concurrent programs.
- Guarded Kleene Algebra with Tests (GKAT): Applying these methods to improve completeness results for guarded systems.

In summary, Kappé's paper refines the theoretical landscape of Kleene Algebra by providing a streamlined, algebraic proof of the Finite Model Property, unifying various completeness results, and offering a new toolkit for reasoning about program equivalence without relying on complex automata-theoretic reductions.