CS Paper Radar

The Largest Tractable Subclass of Multi-Scale Allen Temporal Reasoning

Quentin Cohen-Solal

cs.AI ·submitted 2026-11-18 14:26 UTC · v1

Abstract

In this paper, we propose a novel model for temporal reasoning over multi-scale intervals. We show that this model yields a complete reasoning framework and exhibits other particularly interesting properties. Furthermore, we identify the maximal tractable subalgebra for this model, as well as for the other complete model, in the qualitative scales context, which exhibits weaker properties but whose results can be derived by transfer from our new model.

Closest papers

Nearest neighbours by meaning across the whole index.

A simplified temporal logic completeness proof

cs.LO math.LO ·2026-11-15 ·Robert Goldblatt
similarity 0.63
Abstract

A temporal logic discussed in the author's book "Logics of Time and Computation" is given a simpler proof of semantic completeness, eliminating some flaws in the original.

0.28

PAA: The Probabilistic Allen Algebra: A Generative and Complete Probabilistic Extension of Allen's Interval Relations

cs.AI cs.CL ·2026-09-17 ·Julian Eggert
publishedcode/dataunusual similarity 0.60
Abstract · 41 pages, 7 figures. Open-source implementation at https://github.com/HRI-EU/probabilistic-allen-algebra

Allen's interval algebra is a qualitative calculus for temporal relations, but its thirteen base relations are crisp predicates over exact interval boundaries. This is inadequate for temporal information from language, perception, databases, or uncertain histories, where times, durations, and boundaries are uncertain and expressions such as "just before" or "roughly during" have graded meaning. We develop the probabilistic Allen algebra (PAA): a generative and complete extension in which relation probabilities are derived from distributions over interval boundaries rather than assigned as scores. Time points are Gaussian; intervals have Gaussian midpoints and truncated-Gaussian durations. Every relation is a boundary-ordering predicate in one common probability space: point-point relations reduce to error functions, and point-interval and interval-interval relations to multivariate Gaussian orthant probabilities induced by linear inequalities. Contact relations (meets, starts, finishes, equals) receive positive measure through a tolerance band, and under a single tolerance the thirteen relations form a true partition that recovers crisp Allen as the tolerance vanishes. The construction derives Allen's taxonomy rather than positing it: coarse predicates such as precedence, overlap, and containment are unions of leaves whose probabilities are leaf sums, and this hierarchy is preserved as intervals collapse to points and thirteen relations reduce to five and then three. Each relation further decomposes into correlation-aware temporal primitives in the spirit of CIDOC CRM. The algebra is scale-invariant and separates graded expressions such as "shortly before" from contact relations. All results are Monte-Carlo validated and shipped as an open, tested Python package.

0.55

STAIR: Semantic-Temporal Automaton for Interpretable Reasoning in Temporal Question Answering

cs.CL cs.AI ·2026-08-17 ·Xinlong Dai, Jinchuan Zhang, Lei Gao, Xinzhe Hu, Yuefeng He +1 more
similarity 0.59
Abstract

By leveraging large-scale pretraining, LLMs can interpret diverse temporal expressions and question formulations without task-specific training. However, existing prompt-based neuro-symbolic systems continue to rely on LLMs for both semantic interpretation and exact temporal inference. Consequently, discrete decisions regarding intervals, time anchors, and ordered states remain vulnerable to probabilistic errors and difficult to verify. We present STAIR, a \textbf{S}emantic-\textbf{T}emporal \textbf{A}utomaton for \textbf{I}nterpretable \textbf{R}easoning. STAIR separates semantic interpretation from precise temporal inference: an answer-free LLM adapter maps complex question formulations to normalized temporal intents, while a deterministic temporal automaton with finite control and guarded transitions executes the corresponding policies over canonicalized evidence. Following a rule-first design, STAIR resolves standard questions without invoking an LLM and applies semantic adaptation only when the rule path fails to produce an executable intent. This approach reduces free-form reasoning, making temporal decisions verifiable and interpretable. Specifically, guarded execution supports precise point-time containment and before/after selection, while semantic adaptation handles non-exact intervals and time-anchored queries. Across the TimeQA-Easy, TimeQA-Hard, TempReason-L2, and TempReason-L3 datasets, STAIR consistently outperforms strong baselines in the TQA task using matched model settings, achieving average F1 improvements of 16.57\% and 3.10\% when utilizing the Qwen2.5-7B and GPT-4o-mini models, respectively. Furthermore, ablations and diagnostic analyses demonstrate that STAIR excels at handling both boundary-sensitive and order-sensitive queries, while its guarded execution and semantic adaptation ensure precise point-time reasoning and inexact intervals, respectively.

0.21

Differentiable Ternary Temporal Logic Semantics with Polynomial Surrogate Networks

eess.SY cs.RO ·2026-10-03 ·Ryan Matheu, Sai Sandeep Damera, John S. Baras, Calin Belta
similarity 0.59
Abstract · 9 pages, 6 figures

Temporal logic provides designers a formal reasoning tool for specifying complex spatio-temporal behaviors and tasks for autonomous systems. Many techniques exist for control synthesis according to temporal logic specifications, spanning a large variety of systems, including robotics. However, the vast majority of implementations are limited to Boolean temporal logics. Boolean temporal logic does not have an innate mechanism for quantifying abstention, rather verdicts are either definitively \textit{True} or \textit{False}. Recent work demonstrates that ternary logic is a capable formalism for reasoning about robotic behaviors, with the natural ability to classify uncertainty with the \textit{Unknown} literal. Ternary temporal logic is still in its infancy, with work limited to synthesis for linear systems and monitoring. This work proposes a probabilistic relaxation of ternary temporal logic that allows for value and gradient computation through the same network while retaining exact verdicts on actual data. The relaxed network can be used as an objective in gradient-based control synthesis for both offline and online robotic control applications. We demonstrate the utility of our framework with two robotic manipulator tasks, one offline and one online, involving intermediate checking and sequencing of subtasks to demonstrate the benefit of our approach in terms of correct and timely execution.

0.20

SABET-QA: Temporal Knowledge Graph Question Answering

cs.CL cs.AI ·2026-08-20 ·Brahim Touayouch, Mirette Moawad, Dmitry Akulov
similarity 0.58
Abstract

Question Answering over Temporal Knowledge Graphs (TKGQA) requires reasoning over time-sensitive facts, yet existing embedding-based methods struggle with multi-step queries due to single-pass reasoning pipelines. We propose SABET-QA, a framework that iteratively refines reasoning states across multiple hops via a bidirectional entity-temporal scoring mechanism and a slot-aware contextualization module that aligns question semantics with temporal KG embeddings. A differentiable working memory enables progressive hypothesis refinement, while auxiliary temporal boundaries serve as coarse supervision when available. Experiments on CronQuestions, Complex-CronQuestions, MultiTQ, and TimeQuestions demonstrate consistent improvements over strong baselines, particularly on complex multi-step temporal queries.

0.11

Linear Temporal Logic Translation via Human-Inspired Self-Constrained Reasoning for Robot Task Specification

cs.RO ·2026-08-28 ·Haofei Hou, Fanxu Meng, Shunyi Zhao, Kairui Yang, Mengchen Cai +2 more
similarity 0.57
Abstract

Many robotic tasks are temporally extended and demand precise specifications of subgoals, constraints, and their temporal ordering. Yet human operators typically communicate such tasks in natural language, which is inherently ambiguous, underspecified, and context dependent. Translating human instructions into formal task specifications, such as Linear Temporal Logic (LTL), is therefore essential for verifiable and safe robotic execution. Existing LLM-based translators attempt to bridge this gap through open-ended reasoning or post-hoc constraint enforcement, but the former may violate domain constraints, whereas the latter can disrupt the reasoning needed for novel instructions. This paper proposes Self-Constrained Reasoning (SCR), a framework that mitigates this trade-off by internalizing structural knowledge into the model's decision-making process rather than imposing it as an external filter. By combining a structural constraint representation with a hierarchical decision-making formulation, SCR guides reasoning within a formally grounded space while preserving adaptability to unseen instructions. Experiments show that SCR improves both domain-constraint satisfaction and generalization, providing an effective and interpretable approach for translating human intent into verifiable specifications for robotic execution.

0.16

SCoP: Structured Constraint Parsing for Evidence-Space Control in Temporal Knowledge Graph Question Answering

cs.CL ·2026-09-02 ·Xiaokun Guo, Zhen Xu, Dongdong Huo, Yanqiu Zhang, Dongjin Yu +1 more
top venue similarity 0.57
Abstract

Temporal Knowledge Graph Question Answering (TKGQA) requires answer inference from evidence that is both structurally valid and temporally admissible. Existing methods often leave anchor-event binding, temporal admissibility, and ordinal selection implicit in model reasoning, task-specific training, or similarity-driven retrieval, allowing locally relevant but invalid facts to enter the answer context. We formulate complex TKGQA as evidence-space control and propose SCoP (Structured Constraint Parsing), a constraint-centric framework that externalizes temporal decisions before answer inference. Instead of treating retrieved facts as admissible evidence by default, SCoP separates answer-seeking event patterns from temporal anchor events, conservatively grounds them to canonical TKG entities and relations, and translates temporal intent into executable constraints with optional ranking requirements. These constraints operate over normalized point and interval ranges, enabling deterministic filtering of structurally compatible candidates and producing a compact evidence space for generation. Experiments on MultiTQ and TimelineCronQ-R assess SCoP across timestamped point-fact and interval-oriented settings with richer temporal relations and ordering dependencies. Without task-specific parameter updates, SCoP achieves 0.825 Hits@1 on MultiTQ and 0.761 Hits@1 on TimelineCronQ-R, with gains on constraint-intensive question types. These results support explicit evidence-space control over unconstrained retrieval or implicit temporal reasoning.

0.23

Time to Reason: Scalable Neurosymbolic Learning for LTLf via Fuzzy Semantics

cs.AI ·2026-08-17 ·Riccardo Andreoni, Andrei Buliga, Alessandro Daniele, Paolo Felli, Chiara Ghidini +2 more
similarity 0.56
Abstract

Neurosymbolic (NeSy) Artificial Intelligence aims to integrate Deep Learning (DL) architectures with symbolic reasoning. While initial NeSy approaches have targeted mainly symbolic reasoning in propositional and first-order logics, recent works have started to address the construction of neurosymbolic frameworks for Temporal Logics, and in particular for LTLf. These approaches have established temporal NeSy as a promising research direction, laying the foundations for learning under temporal constraints. Nonetheless, they leave many questions unanswered. From a theoretical perspective, several differentiable semantics for interpreting LTLf have been proposed but have not yet been formally and systematically defined within a unified framework. Moreover, existing approaches commonly rely on automata to represent temporal knowledge, resulting in limited scalability. Motivated by this research gap, this paper provides the following contributions: (i) formally defining different fuzzy semantics for LTLf, and systematically analysing theoretical properties regarding equivalences and dualities of temporal operators; (ii) showing how these semantics can be directly integrated within a novel NeSy framework, called DiffLTLf, enabling flexible and scalable learning without relying on the usage of automata; and (iii) introducing a novel evaluation protocol of increased complexity of learning tasks w.r.t. existing benchmarks. Our results show that the choice of fuzzy semantics has a significant impact on predictive performance. Moreover, DiffLTLf achieves performance on par with, and sometimes superior to, state-of-the-art probabilistic approaches while substantially improving scalability. Taken together, these results establish direct fuzzy interpretations as a competitive and scalable alternative to existing temporal NeSy frameworks.

0.41