Decidability Thresholds in Logic and Concrete Domains

This direction is split into other directions: uniform equivalence undecidability. Its last version stays readable and citable here.

Version 1 of 146 papers65 conceptsfrozen 2026-10-04

In Knowledge Representation, there is a fundamental tension between expressivity (how much a logic can describe) and decidability (whether a computer can actually compute an answer in finite time). Researchers aim to build systems that can reason about both abstract concepts—like "every employee must have a manager"—and "concrete" data—like "an employee's salary must be greater than $50,000."

However, as we combine these two worlds, we frequently hit a "decidability threshold." Small, seemingly innocent additions to a logic can suddenly make the system powerful enough to simulate a Turing machine or encode unsolvable mathematical problems, rendering automated reasoning impossible.

The Arithmetic Trap

The most common way to break a logic is by adding arithmetic. In his foundational work, Carsten Lutz and Franz Baader demonstrated that combining general terminological constraints (Description Logics) with concrete domains that support addition and equality frequently leads to undecidability [The complexity of description logics with concrete domains].

The intuition is that recursion (logic) plus addition (arithmetic) allows a system to "count" and "store" values in a way that mimics the tape of a Turing machine. Once a logic can simulate a Turing machine, the Halting Problem applies: no algorithm can guarantee it will ever finish checking if a statement is true. This same boundary appears in declarative data analysis. Bernardo Cuenca Grau, Boris Motik, and Ian Horrocks found that while recursive logic with general integer arithmetic is undecidable, we can stay decidable by restricting numeric predicates to track only minimum or maximum bounds, a fragment they call Limit Datalog [Foundations of Declarative Data Analysis Using Limit Datalog Programs].

The String-Number Boundary

A similar threshold exists in software verification, where tools must reason about strings (like URLs or passwords). A solver might need to handle three things simultaneously:

  1. Concatenation: Joining strings together.
  2. Regular Expressions: Checking if a string matches a pattern.
  3. Length/Conversion: Reasoning about how many characters are in a string or converting a string like "123" into the number 123.

Individually, these are manageable. But Murphy Berzish and Vijay Ganesh have shown that the moment you integrate string-to-number conversion with concatenation and linear arithmetic over lengths, the theory becomes undecidable [String Theories Involving Regular Membership Predicates: From Practice to Theory and Back].

The reason this combination is so "toxic" for decidability is that it allows the logic to encode Diophantine equations (polynomial equations with integer solutions). Since solving general Diophantine equations is known to be undecidable (Hilbert's tenth problem), any logic that can represent them inherits that impossibility [Cooking String-Integer Conversions with Noodles]. Anthony W. Lin and colleagues observed a similar collapse when combining global string replacement (replaceAll) with numerical length constraints [What Is Decidable about String Constraints with the ReplaceAll Function].

The Danger of Unrestricted Negation

Negation is a third major driver of undecidability. In many logics, saying "X is true" is easy, but saying "it is not the case that X is true" adds immense complexity, especially when combined with recursion.

In Propositional Dynamic Logic (PDL), adding full negation to program expressions makes the logic undecidable. However, Dirk Walther proved that if you restrict negation to only atomic programs, the logic remains decidable [PDL with Negation of Atomic Programs].

In the world of Datalog, Bernardo Cuenca Grau and his team showed that while unrestricted negation in Limit Datalog leads to undecidability by simulating unsolvable mathematical problems, a "numerically stratified" version—where negation cannot be used in a cycle with numeric operations—remains decidable and efficient [Complexity and Expressive Power of Disjunction and Negation in Limit Datalog].

Finding the Goldilocks Zone

To navigate these boundaries, researchers look for "robustly decidable" fragments. These are versions of logic that are expressive enough for real-world use but restricted enough to avoid the arithmetic or negation traps.

  • Guarded Negation: Balder ten Cate introduced "Guarded Negation" (GNFO), where negation is only allowed if it is "guarded" by an atomic predicate. This prevents the logic from creating the complex, interlocking constraints that lead to undecidability while still allowing for powerful queries [Guarded Negation].
  • Unary Negation: Similarly, restricting negation to formulas with only one free variable (Unary Negation) keeps the logic "nice" and decidable [Unary negation].
  • Approximate Reasoning: When exact reasoning is fundamentally undecidable—such as reasoning about transcendental functions like $\sin(x)$ or $e^x$—researchers like André Platzer have proposed "approximate axiomatization." This allows for a complete logic that is provable up to an arbitrary numerical precision ($\delta$), bypassing the undecidability of exact real-number arithmetic [Approximate Axiomatization for Differentially-Defined Functions].

By identifying these specific thresholds, researchers can design languages that are as powerful as possible without crossing the line into computational impossibility.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_decidability_thresholds_in_logic_and_con_e4d016b0,
  title = {Decidability Thresholds in Logic and Concrete Domains},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decidability-thresholds-in-logic-and-concrete-domains/rdr_e4d016b0838d4c33884e2fbcfa4f7de0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_decidability_thresholds_in_logic_and_con_e4d016b0_v1,
  title = {Decidability Thresholds in Logic and Concrete Domains},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decidability-thresholds-in-logic-and-concrete-domains/rdr_e4d016b0838d4c33884e2fbcfa4f7de0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}