💻 computer science

Decidability Results for Fragments of First-Order Logic via a Symbolic Model Property

This paper generalizes symbolic structures to arbitrary base theories and leverages the resulting symbolic model property to prove the decidability of several first-order logic fragments that extend stratified formulas by permitting self-looping functions under specific restrictions.

Original authors: Neta Elad, Sharon Shoham

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Neta Elad, Sharon Shoham

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 trying to verify that a computer program works correctly. To do this, you write a set of logical rules (a "specification") describing how the program should behave. If the program is simple, you can check every possible state it could be in. But many real-world programs deal with infinite possibilities—like a list that can grow forever or a tree structure that can branch endlessly.

Checking these infinite systems is usually impossible because there are too many states to count. This is where the paper comes in. The authors, Neta Elad and Sharon Shoham, propose a clever way to represent these infinite worlds using finite, symbolic blueprints.

Here is the breakdown of their work using simple analogies:

1. The Problem: The Infinite Library

Think of a computer system as a massive library with an infinite number of books. You want to know if a specific rule (like "Every book must have a red cover") is true for the whole library.

The Old Way: You try to look at every single book. Since there are infinite books, you get stuck. You can never finish checking.
The Limitation of Previous Methods: Some previous methods only worked if the library was actually finite (a small, manageable room). But many real systems are infinite, so those methods failed.

2. The Solution: The "Symbolic Blueprint"

The authors introduce a new way to represent the infinite library. Instead of listing every book, they create a symbolic blueprint.

The Nodes (The Boxes): Imagine you group similar books together into boxes. One box might contain "all books with red covers," another "all books with blue covers." Even though each box holds an infinite number of books, the blueprint only has a few boxes.
The Rules (The Labels): Inside each box, you don't write down every book. Instead, you write a simple mathematical rule (like a recipe) that describes exactly which books belong in that box.
The Magic: The authors prove that if a rule is true for the infinite library, it is also true for this finite blueprint. If the blueprint satisfies the rule, the infinite library does too. If the blueprint fails the rule, you have found a "counter-example" (a proof that the system is broken) without needing to check the infinite library.

3. The "Ordered Self-Cycle" (The New Playground)

The authors focus on a specific type of logical rule called the Ordered Self-Cycle (OSC) family.

The Old Rules (Stratified Formulas): Previously, logicians had strict rules about how you could mix "for all" and "there exists" in your sentences. It was like a game where you could only move forward in a straight line. If you tried to loop back, the game broke.
The New Rules (OSC): The authors relaxed these rules. They allowed a specific "loop" in the logic, but only if the items in the loop follow a specific order (like a timeline or a family tree).
- Total Order (The Line): Imagine a straight line of people waiting in a queue. Everyone has a clear position relative to everyone else.
- Prefix Order (The Tree): Imagine a family tree or a file system on a computer. A folder is "before" the files inside it, but two different folders might not be comparable (neither is "before" the other).

The authors proved that even with these loops and complex tree-like structures, you can still build a finite symbolic blueprint to check if the rules hold.

4. The Two Tools They Used

To build these blueprints, the authors used two different "languages" (mathematical theories) depending on the shape of the system:

Linear Integer Arithmetic (The Ruler): For systems that look like a straight line (Total Order), they used standard math with numbers (integers). They treated the infinite elements as points on a number line.
String Theory (The Tree Builder): For systems that look like trees (Prefix Order), they used the theory of strings (sequences of letters). They represented the infinite branches of the tree as infinite strings of characters. This allowed them to handle the complex branching of data structures like linked lists or file systems.

5. The "Generic Recipe"

The paper's biggest contribution is a universal recipe for building these blueprints.

Instead of inventing a new method for every single type of system, they created a step-by-step guide.
Step 1: Take any valid model (a working version of the system).
Step 2: Group the elements into "equivalence classes" (putting similar things in the same box).
Step 3: Translate the relationships between these boxes into the language of the base theory (numbers or strings).
Step 4: Prove that this new, finite blueprint behaves exactly like the original infinite system.

6. Why This Matters

The authors built a prototype tool (a software program) to test this idea. They showed that:

You can now verify systems with infinite loops and tree structures that were previously too hard to check.
If the system is broken, the tool can generate a symbolic counter-example. Instead of saying "I couldn't find a proof," it says, "Here is a blueprint of a scenario where the rule fails," giving the programmer a clear target to fix.

Summary

In short, the authors found a way to shrink infinite, complex logical worlds into finite, manageable blueprints. By doing this, they proved that we can automatically check if certain complex computer systems are safe and correct, even when those systems involve infinite loops and tree-like data structures. They did this by creating a general "recipe" that works for both straight-line orders and branching tree orders.

Technical Summary: Decidability Results for Fragments of First-Order Logic via a Symbolic Model Property

Problem Statement

First-order logic (FOL) is a powerful formalism for specifying verification conditions for systems with unbounded domains, such as those involving linked lists or tree-shaped data structures. However, FOL is generally undecidable. While the finite model property (where every satisfiable formula has a finite model) implies decidability, many useful fragments of FOL do not possess this property; they may only admit infinite models. Consequently, verification tools relying on FOL may fail to find counter-models for invalid formulas, leaving users without actionable feedback.

Existing decidable fragments, such as the Stratified Formulas (SF) fragment (a many-sorted variant of EPR), enforce strict acyclicity constraints on quantifier alternation graphs to guarantee a finite model property. These constraints are often too restrictive for modeling complex systems, requiring significant user effort to adapt specifications. This paper addresses the challenge of establishing decidability for FOL fragments that do not enjoy a finite model property, specifically those allowing self-cycles in the quantifier-alternation graph over a specific sort, provided certain order-theoretic restrictions are met.

Methodology

The authors propose a generalization of symbolic structures, originally introduced in [15] using Linear Integer Arithmetic (LIA), to arbitrary base theories that admit a standard model.

1. Generalized Symbolic Structures

A symbolic structure is a finite representation of a potentially infinite first-order structure. It consists of:

Nodes: A finite set of nodes representing subsets of the domain of a standard model of a base theory $T$ .
Bound Formulas: Each node is associated with a formula in the language of $T$ that defines the set of elements it represents.
Symbolic Interpretations: Interpretations of constants, functions, and relations are defined symbolically using terms and formulas from $T$ .

The key property of symbolic structures is that model checking (determining if a structure satisfies a formula) reduces to the validity of a formula in the base theory $T$ . If $T$ is decidable, model checking for symbolic structures is decidable.

2. The Symbolic Model Property

The paper establishes a symbolic model property for specific fragments of FOL. A fragment admits this property if every satisfiable formula in the fragment has a satisfying symbolic structure over a decidable base theory. Since model checking is decidable for such structures, the existence of this property implies the decidability of the fragment's satisfiability problem.

3. The Ordered Self-Cycle (OSC) Family

The authors define a family of fragments called Ordered Self-Cycle (OSC), parameterized by an axiomatization $\alpha$ of a strict order relation $\prec$ over a distinguished sort $s_\infty$ .

Relaxation of SF: OSC extends the Stratified Formulas fragment by relaxing the acyclicity requirement. It allows function symbols to introduce self-loops (cycles) over the sort $s_\infty$ , provided the quantifier-alternation graph contains no other cycles.
Base Theories: The paper utilizes two primary base theories:
- Linear Integer Arithmetic (LIA): Used for total orders.
- Decidable Theory of Strings (STR): Used for prefix orders.

4. Proof Construction

The decidability proofs follow a generic "proof recipe" that constructs a symbolic model $S$ from an arbitrary model $M$ of a formula $\phi$ . The construction involves:

Partitioning: Dividing the domain of $M$ into equivalence classes based on the atomic formulas they satisfy (atoms). These classes become the nodes of the symbolic structure.
Interpretation: Defining the interpretations of constants, unary relations, and the order $\prec$ to "observe" the atoms satisfied in $M$ .
Handling Mixed Order Atoms: The core difficulty lies in satisfying mixed order atoms (e.g., $f(x) \prec g(x)$ $f (x) ≺ g (x)$ ) and the order axioms $\alpha$ $α$ . This is achieved by defining specific internal shapes for the nodes (summary nodes) and function terms within the base theory.
- For Total Orders (tot), summary nodes are modeled as bidirectionally infinite lines (integers), allowing for "universal finite embeddability" of term orderings.
- For Prefix Orders (pref), summary nodes are modeled as "universal trees" (bidirectionally infinite trees with specific branching factors) to accommodate the non-linear nature of prefix orders.

Key Contributions

General Definition of Symbolic Structures: The paper provides a parametric definition of symbolic structures over any base theory with a standard model, generalizing previous work limited to LIA.
Introduction of the OSC Family: It defines the Ordered Self-Cycle family of fragments, which extends Stratified Formulas by allowing self-cycles over an ordered sort under specific axioms.
New Decidability Results: The authors prove decidability for several new fragments within the OSC family, specifically:
- OSC[pref]: Prefix-Ordered Self-Cycle, using the theory of strings. This fragment models reachability in acyclic tree-shaped data structures and linked lists with sharing.
- Variants with Successors/Predecessors: Fragments combining total/prefix orders with axioms guaranteeing the existence of successors (prosucc) or predecessors (regpred).
Generic Proof Framework: A unified proof technique is presented that constructs symbolic models for these fragments, demonstrating that satisfiability reduces to the validity of formulas in the respective decidable base theories (LIA or STR).
Implementation: A proof-of-concept tool extending the open-source FEST library is implemented to support generic symbolic structures, including model checking over the theory of strings.

Results

The paper establishes that the satisfiability problem is decidable for the following fragments (where $\alpha$ is the order axiom):

$\alpha \in \{ \text{tot}, \text{tot} \land \text{prosucc}, \text{tot} \land \text{regpred}, \text{pref}, \text{pref} \land \text{prosucc}, \text{pref} \land \text{regpred} \}$ .

The result for tot restates prior work [15], while the results for pref and its variants are new. The decidability of OSC[pref] is particularly significant as it handles structures that do not admit a finite model property but can be represented symbolically using string theory.

Significance and Claims

The paper claims that this work offers a new approach to decidability that goes beyond the finite model property. By utilizing symbolic structures, it enables the verification of systems with unbounded domains that were previously intractable due to the lack of finite counter-models.

Theoretical Impact: It bridges the gap between finite model properties and infinite model representations, showing that decidability can be achieved even when infinite models are necessary, provided they can be captured by a decidable base theory.
Practical Relevance: The OSC[pref] fragment directly addresses common verification scenarios involving tree-shaped data structures and linked lists with sharing, which are difficult to model in strictly stratified fragments.
Generality: The framework is designed to be extensible to other base theories and order relations, suggesting a pathway for discovering further decidable fragments.

The authors note that while the decision procedure reduces satisfiability to the validity of formulas in the base theory (which can be non-elementary for string theories), the primary contribution is the establishment of decidability and the ability to generate symbolic counter-models when verification fails. The implementation serves as a proof of concept for the feasibility of this approach.