Expanding the Expressive Scope of Temporal Logic

20 concepts21 papers1 proposal

Temporal logic provides a mathematical language for describing how systems evolve over time. It allows us to specify that a robot should "eventually" reach a goal or that a safety condition must "always" hold. However, a recurring theme across decades of research is that the most common frameworks—often rooted in simple propositional logic—are frequently too restrictive to capture the complexity of the real world.

Researchers are currently working to bridge this "expressivity gap" by moving beyond basic propositional fragments toward first-order, relational, and highly specialized temporal formalisms.

The Relational Gap in Propositional Logic

Most foundational temporal reasoning systems are built on propositional logic, where facts are treated as simple true/false variables. As early as 1982, Mays argued in Monitors as Responses to Questions: Determining Competence that this approach is insufficient for modeling the complex entities and relationships found in actual databases. If a system cannot represent variables or quantified relationships (e.g., "for every patient, their fever must subside"), it cannot truly monitor sophisticated domain constraints.

This limitation is particularly acute in specialized fields like medicine. Godo et al. and Vila point out that propositional frameworks lack the ability to represent relational data between entities, which is essential for diagnostic patterns. Their work in Possibilistic Temporal Reasoning based on Fuzzy Temporal Constraints suggests that extending these systems to first-order logic structures is a necessary step for handling real-world uncertainty and relational complexity.

The Fragment Problem in System Verification

Even when using more modern logics like Linear Temporal Logic (LTL) or Signal Temporal Logic (STL), practical tools often restrict themselves to small "fragments" of the language to remain computationally feasible. This creates a bottleneck for autonomous systems:

These restrictions mean that while we can verify if a car "always stays in its lane," we struggle to verify more nuanced behaviors, such as complex interaction protocols or non-context-free properties that Belardinelli et al. identify as a major hurdle for formal reward design in reinforcement learning.

The Complexity Trade-off

The reason these restrictions exist is rarely an oversight; it is a deliberate trade-off for computational efficiency. Thomas et al. demonstrate in Model Checking CTL is Almost Always Inherently Sequential that most practical subsets of Computation Tree Logic (CTL) are P-complete, meaning they cannot be easily parallelized. By identifying even more restricted fragments, however, they find specific cases where model checking becomes efficiently parallelizable.

Similarly, Walega et al. show that while computing all facts entailed by a full LTL specification is doubly exponential in complexity, focusing on "Horn fragments" can reduce this to quadratic complexity. This suggests that the path forward involves identifying the right restrictions—those that are expressive enough for the task but restricted enough to be solved quickly.

Toward Richer Temporal Reasoning

Current research is actively pushing these boundaries. Hasanbeig et al. are extending reinforcement learning tools from LTL to the more continuous Signal Temporal Logic (STL). Meanwhile, Lange et al. have introduced "Strict First-Time Semantics" in Metric Linear-Time Temporal Logic with Strict First-Time Semantics, creating a logic that is more succinct than LTL for real-time systems while remaining computationally manageable.

Ultimately, the goal is to move away from "perfect" but limited propositional models toward frameworks that can handle the "approximate arguments" of human reasoning (Hunter) and the infinite-horizon tasks required for truly autonomous agents (Zhu et al.). By systematically expanding the supported fragments of temporal logic, researchers are enabling AI to reason about a world that is relational, continuous, and complex.

Key Foundational Work

Possibilistic Temporal Reasoning based on Fuzzy Temporal Constraints (1995) — contributed 1 concept elements to this direction.
Monitors as Responses to Questions: Determining Competence (1982) — contributed 1 concept elements to this direction.
Possibilistic Temporal Reasoning based on Fuzzy Temporal Constraints (1995) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_propositional_logic_restriction_067781f5,
  title = {propositional logic restriction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/propositional-logic-restriction/rdr_067781f5d2154961ba002e3b7a263541},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_propositional_logic_restriction_067781f5_v1,
  title = {propositional logic restriction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/propositional-logic-restriction/rdr_067781f5d2154961ba002e3b7a263541/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake