On the Trap Space Semantics of Normal Logic Programs
- URL: http://arxiv.org/abs/2601.03842v1
- Date: Wed, 07 Jan 2026 12:06:26 GMT
- Title: On the Trap Space Semantics of Normal Logic Programs
- Authors: Van-Giang Trinh, Sylvain Soliman, François Fages, Belaid Benhamou,
- Abstract summary: We introduce trap space semantics to arbitrary normal logic programs.<n>This new semantics admits both model-theoretic and dynamical characterizations.<n>Our results demonstrate that the trap space semantics offers a unified and precise framework for proving the existence of supported classes.
- Score: 2.274915755738124
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The logical semantics of normal logic programs has traditionally been based on the notions of Clark's completion and two-valued or three-valued canonical models, including supported, stable, regular, and well-founded models. Two-valued interpretations can also be seen as states evolving under a program's update operator, producing a transition graph whose fixed points and cycles capture stable and oscillatory behaviors, respectively. We refer to this view as dynamical semantics since it characterizes the program's meaning in terms of state-space trajectories, as first introduced in the stable (supported) class semantics. Recently, we have established a formal connection between Datalog^\neg programs (i.e., normal logic programs without function symbols) and Boolean networks, leading to the introduction of the trap space concept for Datalog^\neg programs. In this paper, we generalize the trap space concept to arbitrary normal logic programs, introducing trap space semantics as a new approach to their interpretation. This new semantics admits both model-theoretic and dynamical characterizations, providing a comprehensive approach to understanding program behavior. We establish the foundational properties of the trap space semantics and systematically relate it to the established model-theoretic semantics, including the stable (supported), stable (supported) partial, regular, and L-stable model semantics, as well as to the dynamical stable (supported) class semantics. Our results demonstrate that the trap space semantics offers a unified and precise framework for proving the existence of supported classes, strict stable (supported) classes, and regular models, in addition to uncovering and formalizing deeper relationships among the existing semantics of normal logic programs.
Related papers
- Distilling Formal Logic into Neural Spaces: A Kernel Alignment Approach for Signal Temporal Logic [6.419602857618508]
We introduce a framework for learning continuous neural representations of formal specifications.<n>We distill a symbolic robustness kernel into a Transformer encoder.<n>The encoder produces embeddings in a single forward pass, effectively mimicking the kernel's logic at a fraction of its computational cost.
arXiv Detail & Related papers (2026-03-05T14:08:25Z) - Explainable Chain-of-Thought Reasoning: An Empirical Analysis on State-Aware Reasoning Dynamics [69.00587226225232]
We introduce a state-aware transition framework that abstracts CoT trajectories into structured latent dynamics.<n>To characterize the global structure of reasoning, we model their progression as a Markov chain.<n>This abstraction supports a range of analyses, including semantic role identification, temporal pattern visualization, and consistency evaluation.
arXiv Detail & Related papers (2025-08-29T18:53:31Z) - Semantic Attractors and the Emergence of Meaning: Towards a Teleological Model of AGI [0.0]
This essay develops a theoretical framework for a semantic Artificial General Intelligence (AGI) based on the notion of semantic attractors in complex meaning spaces.
arXiv Detail & Related papers (2025-08-21T19:57:52Z) - Fuzzy Propositional Formulas under the Stable Model Semantics [7.052794276153519]
We define a stable model semantics for fuzzy propositional formulas, which generalizes both fuzzy propositional logic and the stable model semantics of classical propositional formulas.<n>The syntax of the language is the same as the syntax of fuzzy propositional logic, but its semantics distinguishes stable models from non-stable models.
arXiv Detail & Related papers (2025-06-15T10:38:56Z) - Modal Logic for Stratified Becoming: Actualization Beyond Possible Worlds [55.2480439325792]
This article develops a novel framework for modal logic based on the idea of stratified actualization.<n>Traditional Kripke semantics treat modal operators as quantification over fully determinate alternatives.<n>We propose a system Stratified Actualization Logic (SAL) in which modalities are indexed by levels of ontological stability, interpreted as admissibility.
arXiv Detail & Related papers (2025-06-12T18:35:01Z) - On the Boolean Network Theory of Datalog$^\neg$ [0.9374652839580183]
We establish a formal link between Datalog$neg$ and Boolean network theory.<n>We show that in the absence of odd cycles in a Datalog$neg$ program, the regular models coincide with the stable models.<n>This connection also gives new upper bounds on the numbers of stable partial, regular, and stable models of a Datalog$neg$ program.
arXiv Detail & Related papers (2025-04-21T20:02:59Z) - The Stable Model Semantics for Higher-Order Logic Programming [4.106754434769354]
We propose a stable model semantics for higher-order logic programs.
Our semantics is developed using Approximation Fixpoint Theory (AFT), a powerful formalism.
We provide examples in different application domains, which demonstrate that higher-order logic programming under the stable model semantics is a powerful and versatile formalism.
arXiv Detail & Related papers (2024-08-20T06:03:52Z) - An Encoding of Abstract Dialectical Frameworks into Higher-Order Logic [57.24311218570012]
This approach allows for the computer-assisted analysis of abstract dialectical frameworks.
Exemplary applications include the formal analysis and verification of meta-theoretical properties.
arXiv Detail & Related papers (2023-12-08T09:32:26Z) - LOGICSEG: Parsing Visual Semantics with Neural Logic Learning and
Reasoning [73.98142349171552]
LOGICSEG is a holistic visual semantic that integrates neural inductive learning and logic reasoning with both rich data and symbolic knowledge.
During fuzzy logic-based continuous relaxation, logical formulae are grounded onto data and neural computational graphs, hence enabling logic-induced network training.
These designs together make LOGICSEG a general and compact neural-logic machine that is readily integrated into existing segmentation models.
arXiv Detail & Related papers (2023-09-24T05:43:19Z) - Guiding the PLMs with Semantic Anchors as Intermediate Supervision:
Towards Interpretable Semantic Parsing [57.11806632758607]
We propose to incorporate the current pretrained language models with a hierarchical decoder network.
By taking the first-principle structures as the semantic anchors, we propose two novel intermediate supervision tasks.
We conduct intensive experiments on several semantic parsing benchmarks and demonstrate that our approach can consistently outperform the baselines.
arXiv Detail & Related papers (2022-10-04T07:27:29Z) - Infusing Finetuning with Semantic Dependencies [62.37697048781823]
We show that, unlike syntax, semantics is not brought to the surface by today's pretrained models.
We then use convolutional graph encoders to explicitly incorporate semantic parses into task-specific finetuning.
arXiv Detail & Related papers (2020-12-10T01:27:24Z) - Temporal Answer Set Programming [3.263632801414296]
We present an overview on Temporal Logic Programming under the perspective of its application for Knowledge Representation and declarative problem solving.
We focus on recent results of the non-monotonic formalism called Temporal Equilibrium Logic (TEL) that is defined for the full syntax.
In a second part, we focus on practical aspects, defining a syntactic fragment called temporal logic programs closer to ASP, and explain how this has been exploited in the construction of the solver TELINGO.
arXiv Detail & Related papers (2020-09-14T16:13:36Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.