💻 computer science

Equational and Inductive Reasoning for Maude in Athena

This paper introduces maude2athena, a framework that translates Maude's equational specifications into the Athena theorem prover to enable inductive and deductive reasoning, including induction modulo structural axioms, while preserving semantic fidelity and ensuring a compact translation.

Original authors: Mateo Sanabria, Carlos Varela, Camilo Rocha, Nicolas Cardozo

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mateo Sanabria, Carlos Varela, Camilo Rocha, Nicolas Cardozo

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 have two very different tools in your toolbox: a high-speed construction robot (Maude) and a meticulous architectural inspector (Athena).

The Robot (Maude) is amazing at building things quickly. It follows strict blueprints (equations) to assemble data, handle complex shapes, and even understand that a "square" is a type of "rectangle" (subsorting). It's great for running programs and checking if a design works in practice. However, the robot doesn't really "think" about why its design is perfect for every possible future scenario. It just builds.
The Inspector (Athena) is a master of logic. It can prove, with absolute certainty, that a bridge will never collapse, no matter how many cars drive over it. It uses a method called "induction" (proving a rule works for the first step, then proving that if it works for step $N$ , it works for step $N+1$ ). But the inspector is picky: it only understands simple, flat blueprints. It gets confused by the robot's fancy "subsort" features (like the square/rectangle relationship) and can't read the robot's native language.

The Problem:
You want to build a complex system using the Robot's speed and flexibility, but you also need the Inspector's guarantee that it's 100% safe. Previously, you couldn't use them together easily. You'd have to manually redraw the Robot's complex blueprints into the Inspector's simple language, a process that was slow, error-prone, and often lost the original design's nuance.

The Solution: maude2athena
This paper introduces a new "Universal Translator" called maude2athena. It acts as a bridge between the Robot and the Inspector.

Here is how it works, using a few analogies:

1. The "Cast" Translator (Handling Subsorting)

In the Robot's world, a "Non-Zero Natural Number" is just a special kind of "Natural Number." The Robot knows this implicitly. The Inspector, however, sees them as two completely different boxes and gets confused.

The translator solves this by adding "Cast Operators." Think of these as adapters.

If the Robot says, "Here is a Non-Zero Number," the translator doesn't just pass it over. It attaches a little tag (a cast) that says, "This is a Non-Zero Number, but I am explicitly treating it as a Natural Number for the Inspector."
This allows the Inspector to understand the Robot's complex hierarchy without getting lost, ensuring that the logic remains sound.

2. The "Flat" Map (Flattening the Structure)

The Robot builds in 3D (order-sorted), where objects have layers and relationships. The Inspector only understands 2D (many-sorted) maps.

The translator takes the Robot's 3D structure and "flattens" it onto a 2D map.
The Trick: Usually, flattening a 3D object destroys its shape. But this translator is smart. It uses a concept called "Strictly Sensible" logic. Imagine it's like a puzzle where every piece has a unique "master piece" it belongs to. By picking the best representative for every overloaded function, it ensures the flattened map is a perfect, non-distorted reflection of the original 3D object.

3. Rebuilding the "Ladder" (Inductive Reasoning)

This is the most critical part. When you flatten the Robot's 3D structure into a 2D map, you lose the ladder.

In the Robot's world, you can climb a ladder: "If I prove it for the bottom rung, and I prove that if I'm on rung $N$ , I can get to rung $N+1$ , then I've proved it for the whole ladder." This is Induction.
When the translator flattens the map, the ladder disappears. The Inspector sees a flat field and doesn't know how to climb.
The Innovation: The authors didn't just translate the blueprints; they re-invented the ladder. They created a new "Primitive Method" (a custom tool) for the Inspector. This tool looks at the flattened map and says, "Okay, even though this looks flat, I know these specific points act like the rungs of a ladder. I will now prove the bottom, then prove the step-up, and thus prove the whole thing."

The Real-World Test: The Compiler

To prove this works, the team tested it on a Toy Compiler (a program that translates math expressions into machine code).

The Challenge: The compiler had to handle integers, expressions, and instructions, with complex rules about how they fit together (e.g., an instruction is a type of program).
The Result: The translator took the Robot's complex compiler code, added the necessary "adapters" (casts), flattened the structure, and built a custom "ladder" for the Inspector.
The Outcome: The Inspector was able to mathematically prove that the compiler always works correctly. It verified that if you compile a math expression and run it, you get the exact right answer, every single time.

Why This Matters

Before this, you had to choose: Speed (use Maude) or Safety (use Athena).
Now, you can have both. You can write your system in the flexible, powerful language of Maude, and then automatically translate it to Athena to get a rigorous, human-readable mathematical proof that your system is bug-free.

It's like giving your high-speed construction robot a safety inspector that speaks its language, ensuring that the skyscrapers it builds are not just standing up, but are mathematically guaranteed to never fall.

1. Problem Statement

The paper addresses a significant gap in formal verification between executable specification and interactive theorem proving.

Maude: A high-performance language based on Rewriting Logic and Membership Equational Logic (MEL). It excels at defining deterministic functional behavior, abstract data types, and executing specifications using order-sorted algebras (subsorts, overloading) and structural axioms (associativity, commutativity, identity). However, Maude lacks native, robust support for interactive inductive reasoning and fine-grained proof control.
Athena: An interactive theorem prover based on many-sorted first-order logic (FOL) with natural deduction. It offers powerful support for inductive reasoning, proof structuring, and equational chaining. However, it lacks native support for order-sorted features (subsorts) and structural axioms (ACU) essential to many Maude specifications.
The Challenge: Directly reusing Maude specifications in Athena is impossible without a careful reconciliation of their logical foundations. Existing translations often fail to preserve the inductive structure of order-sorted datatypes or suffer from exponential blowup when flattening subsort hierarchies.

2. Methodology: The `maude2athena` Framework

The authors present maude2athena, a framework that systematically translates Maude functional modules into Athena modules. The translation is grounded in a semantics-preserving mapping from Membership Equational Logic to many-sorted FOL.

A. Theoretical Foundation: Strictly Sensible Signatures

To ensure the translation is linear and avoids exponential blowup, the framework relies on the concept of strictly sensible order-sorted algebras.

Argument Compatibility: Overloaded function symbols are grouped into classes where arguments share a common supersort.
Maximal Representative: For each class, a unique "maximal" representative is selected.
Result: This guarantees that every function symbol in Maude maps to a single, consistent function symbol in Athena, preserving soundness without ambiguity.

B. The Translation Function ($tr$)

The translation maps a Maude theory $E = (\Sigma, E \cup A)$ to an Athena theory $(\beta, \gamma, \rho)$ through five components:

Sort Translation ( $tr_S$ ):
- Sorts with constructors and no subsort relations are translated into Athena datatypes (preserving native induction).
- Sorts involved in subsort relations (e.g., Even < Nat) are translated into Athena domains (sets).
Function Symbol Translation ( $tr_F$ ):
- Selects maximal representatives for overloaded operators.
- Introduces explicit cast operators (e.g., Cast_Even_to_Nat) to handle implicit subsort coercions in Maude.
- Translates structural axioms (Associativity, Commutativity, Identity) into explicit equational assertions in Athena.
Term Translation ( $tr_T$ ):
- Rewrites terms by inserting cast operators wherever a subsort coercion is required to match the expected sort of an operator.
Equation Translation ( $tr_E$ ):
- Translates Maude equations into Athena assertions.
- Adds core equality axioms to ensure transitivity of casts (e.g., casting $A \to B \to C$ is equivalent to $A \to C$ ).
Membership Translation ( $tr_M$ ):
- Since Athena's many-sorted logic does not natively support membership predicates ( $t : s$ ), the framework introduces unary predicates (e.g., is_even) and translates membership axioms into implications guarded by these predicates.

C. Inductive Reasoning Recovery ( $tr_\eta$ )

A critical challenge is that translating order-sorted sorts to domains removes the native inductive structure required for proofs.

Solution: The framework generates custom primitive induction methods in Athena.
Mechanism: For each connected component of the sort hierarchy, the tool constructs a method that explicitly encodes:
- Base Cases: Proofs for minimal elements (constructors).
- Inductive Steps: Proofs that if a property holds for recursive arguments, it holds for the constructed term.
This allows users to perform structural induction on domains that were originally order-sorted datatypes in Maude.

3. Key Contributions

Semantics-Preserving Translation: A formal mapping from Membership Equational Logic (Maude) to many-sorted FOL (Athena) that preserves equational provability. Theorem 1 proves that $t =_E u$ in Maude if and only if their translations are provably equal in Athena.
Inductive Reasoning for Domains: The development of a parametric induction framework that reconstructs structural induction principles for translated domains, overcoming the limitation that Athena's native by-induction only works on datatypes.
Handling Structural Axioms: A systematic method for translating ACU (Associativity, Commutativity, Identity) axioms into explicit equational assertions, enabling reasoning modulo these axioms in a standard FOL setting.
Implementation: A working tool (maude2athena) available as an open-source framework that automates the translation and induction method generation.

4. Results and Validation

The framework was validated through theoretical proofs and a non-trivial case study:

Theoretical Correctness: The paper provides rigorous proofs for the correctness of the equational translation (Theorem 1) and the soundness of the generated inductive proofs (Theorem 2).
Case Study (Toy Compiler):
- Subject: A compiler for numeric expressions targeting a Stack Machine.
- Complexity: The specification heavily relies on subsorting (Int < Exp, Instr < Program) and structural axioms (Program is associative with nil as identity).
- Verification: The authors successfully proved the compiler's correctness: Compiling an expression and executing it yields the same result as evaluating the expression directly.
- Outcome: The proof required handling explicit casts (e.g., Cast_Int_to_Exp) and using the custom exp-induction method, demonstrating that the framework can handle deep inductive structures and operator overloading while maintaining rigorous mathematical consistency.

5. Significance

Bridging the Gap: The work effectively bridges the gap between model checking (Maude's strength in execution and state exploration) and theorem proving (Athena's strength in deductive verification).
Human-Readable Proofs: Unlike native Maude provers (like NuITP) that generate metalevel search traces, maude2athena produces proofs in a natural deduction style that are structured, transparent, and readable by humans.
Complementarity: It offers a complementary approach to automated tools. While SMT solvers and narrowing are excellent for safety properties, this framework enables complex inductive arguments and case-based reasoning that are difficult to automate fully.
Future Impact: The authors outline future work to extend this to rewrite rules (concurrent systems) by mapping Maude's system modules to logical transition relations, potentially bringing temporal reasoning capabilities to Athena.

In summary, maude2athena provides a robust, theoretically grounded pipeline that allows developers to write executable, order-sorted specifications in Maude and verify their inductive properties using the powerful, structured proof environment of Athena.