💻 computer science

The TPTP Format for Interpretations

This paper introduces and details the TPTP format for representing Tarskian, Herbrand, and Kripke interpretations, covering its syntax, semantics, verification, and tool support to ensure adequacy for various applications.

Original authors: Geoff Sutcliffe, Alexander Steen, Pascal Fontaine, Lydia Kondylidou

Published 2026-06-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Geoff Sutcliffe, Alexander Steen, Pascal Fontaine, Lydia Kondylidou

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

The Big Picture: Finding the "What If" Scenario

Imagine you are a detective trying to solve a mystery. You have a set of rules (axioms) and a theory (a conjecture) about what happened. Usually, your job is to prove that the theory must be true based on the rules.

But sometimes, you want to prove the theory is wrong. To do that, you need to find a specific scenario—a "counterexample"—where the rules hold true, but your theory falls apart. In the world of computer logic, this scenario is called an interpretation or a model.

For a long time, computers could find these "wrong" scenarios, but they kept the results to themselves. They would just say, "I found a counterexample!" without showing you what it looked like. This was like a detective saying, "The butler didn't do it," but refusing to show you the alibi.

This paper introduces a new, standardized way for computers to write down these scenarios so humans and other computers can read, check, and understand them. It's like creating a universal "blueprint" for these alternative realities.

The Three Types of Blueprints

The paper explains that there are three main ways to build these scenarios, and the new format handles all of them:

1. The Finite World (Tarskian Interpretations)
Imagine a small, closed room with a specific number of people and objects.

The Analogy: Think of a board game like Clue. You have a fixed set of characters (Colonel Mustard, Mrs. Peacock), a fixed set of rooms, and a fixed set of weapons.
The Format: The computer writes down a list: "In this world, there are exactly 4 people. Colonel Mustard is in the library. The candlestick is in the kitchen." It explicitly lists every single connection.
Why it matters: This is great for checking if a system works with a small, manageable number of items.

2. The Infinite World (Infinite Interpretations)
Now, imagine a world that never ends, like the number line (1, 2, 3, 4... forever).

The Analogy: You can't write down an infinite list of numbers. Instead, you write a recipe or a rule: "Start with zero. To get the next number, add one."
The Format: The computer doesn't list every number. Instead, it writes a rule like, "For any number $X$ , the next person is $X+1$ ." It uses math formulas to describe the infinite crowd.
Why it matters: This is needed when dealing with things like time, money, or data that can grow without limit.

3. The Multiverse (Kripke Interpretations)
Sometimes, the rules change depending on where you are or when you look.

The Analogy: Think of a "Choose Your Own Adventure" book or a multiverse movie. In one room (World A), it's raining. In the next room (World B), it's sunny. The characters might be different in each room, or they might stay the same. There are doors connecting these rooms (accessibility).
The Format: The computer writes down a map of all the rooms, which doors are open, and what the weather is in each room. It says, "In World 1, it rains. In World 2, it's sunny. You can walk from World 1 to World 2, but not back."
Why it matters: This is crucial for things like security protocols or AI reasoning, where the truth depends on the context.

The "Recipe" for the Format

The paper details exactly how to write these blueprints using a specific language called TPTP. Think of TPTP as a universal programming language for logic.

The Ingredients: The format requires you to define the "domain" (who is in the room), the "mappings" (who is doing what), and the "rules" (what is true or false).
The Flexibility: The format is smart. It can be coarse-grained (a big, messy paragraph describing the whole world) or fine-grained (a detailed spreadsheet breaking down every single person and object).
The "Herbrand" Special Case: Sometimes, the "world" is just a list of words and sentences generated by the computer itself. The paper calls these "Herbrand interpretations." It's like a dictionary where the definitions are built entirely out of the words in the dictionary.

Why Do We Need This? (The "Trust Me" Problem)

The paper argues that just finding a solution isn't enough; we need to verify it.

The Old Way: A computer says, "I found a bug!" You have to trust the computer. If the computer made a mistake, you're stuck with a broken system.
The New Way: The computer hands you the blueprint (the interpretation). You (or another computer) can read the blueprint and check the math.
- Can you read it? Yes, the format is designed to be human-readable.
- Can you check it? Yes, you can run a simple test to see if the blueprint actually makes the rules work.
- Is it useful? Yes, because if you find a bug, the blueprint shows you exactly where the fault is (e.g., "John is in the kitchen, but the rules say he should be in the library").

The "Toolbox"

The paper mentions that tools already exist to help with this:

Visualizers: Imagine a 3D map where you can click on a "World" and see the characters inside it. The paper mentions a tool called the "Interactive Interpretation Viewer" (IIV) that does exactly this for finite worlds.
Verifiers: Tools that take the blueprint and the original rules and automatically check if they match.

Summary

In short, this paper is about standardizing the way computers share their "what if" scenarios.

Before, computers found counterexamples but kept them hidden in a black box. Now, they can write them down in a clear, standardized "blueprint" language. This allows humans to look at the blueprint, understand why a system failed, and verify that the computer didn't make a mistake. It turns a "trust me" moment into a "show me" moment.

Technical Summary: The TPTP Format for Interpretations

Problem Statement
Automated Theorem Proving (ATP) has historically focused on deriving theorems from axioms. However, disproving conjectures by finding countermodels (interpretations that satisfy axioms but falsify the conjecture) is a critical facet of ATP, essential for applications such as formal verification, consistency checking, and operations research. While the TPTP World has long supported a format for finite Tarskian interpretations, the existing format was insufficient for:

Representing interpretations with infinite domains.
Representing Kripke interpretations (used in non-classical logics like modal logic).
Providing a unified, standardized representation for Herbrand interpretations and saturations.

The lack of a standardized format for these diverse interpretation types hinders the ability to verify models, analyze counterexamples, and integrate model finding into broader reasoning pipelines.

Methodology
The authors developed a new TPTP format for interpretations based on the principle that interpretations should be represented as formulae written in the TPTP language itself. This approach leverages the existing TPTP syntax (supporting CNF, FOF, TFF, THF, etc.) and the annotated formula structure language(name, role, formula, source, useful_info).

The methodology involves:

Defining the interpretation role: A new formula role is introduced to distinguish interpretation-formulae from problem axioms or conjectures.
Structuring Tarskian Interpretations: The format defines interpretations as conjunctions of domain specifications and symbol mappings.
- Finite Domains: Specified via universally quantified disjunctions of equalities (enumerating elements) and distinctness constraints (using $distinct or double-quoted terms).
- Infinite Domains: Specified via existential quantification to capture infinite disjunctions (e.g., Peano numbers) or by utilizing defined types (e.g., $int).
- Type Handling: For typed logics (TFF, THF), the format employs "type-promotion bijections" to map domain elements (which may have distinct internal types) to the problem's types, ensuring well-typedness.
- Herbrand Interpretations: Represented using interpretation-herbrand subroles, often utilizing predicate definitions over term algebras or saturations.
Structuring Kripke Interpretations: The format extends the Tarskian model by adding a layer of "worlds." It introduces defined symbols: $world (type), $accessible_world` (relation), `$ local_world (constant), and $in_world (predicate). A Kripke interpretation is a conjunction specifying the set of worlds, the accessibility relation, and the Tarskian interpretation within each world.
Granularity and Modularity: The format supports splitting interpretations into multiple formulae using subroles (e.g., interpretation-domains, interpretation-mappings) at medium and fine-grained levels to separate concerns or compact representations using quantification.
Verification: The paper outlines a verification methodology where the interpretation-formulae are treated as axioms, and the original problem formulae are treated as conjectures (or negated conjectures). If the problem formulae can be proved from the interpretation-formulae, the interpretation is verified as a valid model.

Key Contributions

Unified Syntax: A single, extensible TPTP format capable of representing Tarskian (finite and infinite), Herbrand, and Kripke interpretations.
Infinite Domain Support: Mechanisms to represent infinite domains using term algebras (e.g., Peano numbers) or built-in types (e.g., integers), moving beyond the previous limitation to finite models.
Kripke Model Representation: A formal specification for representing modal logic countermodels, including world structures and accessibility relations, within the TPTP framework.
Verification Framework: A concrete method for verifying models by reducing the task to theorem proving, ensuring that the output of a model finder is not merely trusted but verifiable.
Tooling and Visualization: Identification of tools that support the format, including the AGMV model verifier and the Interactive Interpretation Viewer (IIV), which allows for the visualization of finite Tarskian and Kripke models.

Results and Capabilities
The paper does not present new experimental data or benchmarks but rather defines the specification and demonstrates its utility through numerous examples (provided in the appendices). These examples illustrate:

The representation of finite countermodels for untyped (FOF) and typed (TFF, THF) problems.
The representation of infinite models using both term domains and defined types.
The representation of Kripke models for non-classical logics (NXF).
The ability to split and compact these representations for readability and modularity.
The successful construction of verification problems that can be discharged by trusted ATP systems.

Significance and Claims
The authors claim that this work ensures the TPTP representation format is adequate for the diverse needs of the ATP community. The significance lies in the shift from "black box" model finding to transparent, verifiable, and analyzable model representation.

The paper modestly claims that the format provides the necessary properties for interpretation representation:

Evaluability: Formulas can be evaluated with respect to the interpretation.
Tractability: Evaluation is tractable for finite interpretations; infinite interpretations may be intractable but are representable.
Verifiability: Models can be verified by checking if the problem formulae follow from the interpretation-formulae.
Comprehensibility: The format is designed to be human-readable, though the authors note that complex representations (like saturations or infinite domains) may remain difficult for humans to comprehend.

The work serves as a foundation for ATP systems to output richer, more diverse models, facilitating better debugging in verification and deeper analysis in logic research. The authors note that the format is currently being adopted, with plans to extend it to cover more non-classical languages in the future.