On the Trap Space Semantics of Normal Logic Programs
Van-Giang Trinh Sylvain Soliman François Fages, Belaid Benhamou · 2026
Read On the Trap Space Semantics of Normal Logic Programs by Van-Giang Trinh Sylvain Soliman François Fages, Belaid Benhamou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-03842.txt.
Introduction
Van-Giang Trinh and three co-authors propose a new semantics for normal logic programs based on trap spaces, a concept borrowed from the study of Boolean networks. Traditionally, logic program meaning rests on canonical models such as supported, stable, and well-founded models. Another view treats interpretations as states evolving under the program's update rule, where fixed points and cycles in the transition graph mean stable and oscillatory behavior.
The team had already connected function-free logic programs with Boolean networks and imported trap spaces for that case. Here they generalize trap spaces to arbitrary normal logic programs, introducing trap space semantics as a new approach. Trap spaces capture regions of the state space that dynamics cannot leave, which for logic programs translates into durable partial conclusions, a useful lens for analyzing program behavior over time.
Catalog record
| CREATOR | Van-Giang Trinh Sylvain Soliman François Fages, Belaid Benhamou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-03842
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Trap Space Semantics of Normal Logic Programs Van-Giang Trinh Sylvain Soliman François Fages, Belaid Benhamou 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 ¬ programs (i.e., normal logic programs without function symbols) and Boolean networks, leading to the introduction of the trap space concept for Datalog ¬ 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. keywords logic programming, normal logic program, Clark’s completion, model-theoretic semantics, dynamical semantics, trap space, Boolean network, infinite structure 1 Introduction The meaning of a Normal Logic Program ( NLP )—its declarative semantics—is typically defined by a class of models of a logical formula associated with the program, such as the Herbrand models of the Clark’s completion of the program [ 14 ] . This was later shown to be equivalent to the supported model semantics [ 3 ] . For NLPs with negation, the Clark’s completion may have no model, or several minimal models; therefore, there is generally no unique least Herbrand model. In this setting, the stable model semantics was introduced by [ 25 ] to provide a canonical notion of two-valued models, defined by an elegant fixed‑point definition based on the least model of a reduct transformation. Stable models were later characterized as well-supported models [ 22 ] , i.e., models with circuit-free finite justifications—which led to graphical conditions for the existence of stable models [ 21 , 2 ] , and equivalence results with other forms of non-monotonic logics [ 44 , 32 , 33 , 8 ] . A three-valued logic approach was introduced, where the third value denotes ignorance [ 24 , 34 , 36 ] . Subsequent research expanded the semantic landscape of NLPs through additional three-valued logic transformations [ 4 ] . The stable (supported) partial model semantics —also known as the three-valued stable (supported) model semantics—extends the two-valued stable (supported) model semantics [ 35 , 20 , 34 ] . Under this framework, all models are minimal, and every NLP possesses at least one stable (supported) partial model. Notably, two specific types of stable partial semantics are distinguished by their informational content: the well-founded partial model semantics [ 23 , 34 ] , representing the unique model with minimal information, and the regular model semantics [ 43 ] , encompassing models with maximal information. It is worth noting that these three-valued semantics (e.g., stable partial models, regular models) in normal logic programs have been shown to correspond to several extension-based semantics (e.g., complete extensions, preferred extensions, respectively) in Dung’s frameworks [ 18 , 42 ] and assumption-based argumentation [ 11 ] , which are two prominent formalisms in symbolic AI. Alternatively, an NLP can be viewed as a state-transition system in which each rule in the program represents how a component (here an atom) is affected by other components [ 5 , 9 ] . The dynamical behaviors of the program, including its oscillating behavior [ 28 ] , are characterized by a directed graph called the (stable or supported) transition graph whose vertices are two-valued interpretations and whose arcs are transitions between interpretations. This led to the stable class semantics [ 5 ] and supported class semantics [ 28 ] . If a stable (resp. supported) class is of size one, it coincides with a stable (resp. supported) model and exhibits a stable behavior. Otherwise, it exhibits an oscillating behavior. The aforementioned semantics capture various aspects of program behavior. Despite their success, they often diverge in interpretive principles, and many lack a unifying framework that integrates both model-theoretic and dynamical behaviors coherently. Recently, we have established a formal connection between Datalog ¬ programs (i.e., NLPs without function symbols—thus the Herbrand base is finite) and Boolean networks, leading to the introduction of the concept of trap space for Datalog ¬ programs, inspired by the notion of trap space in Boolean networks [ 29 , 40 ] . This concept offers a bridge between model-theoretic and dynamical aspects, but applies only to finite structures [ 41 ] . In this paper, we generalize the trap space concept to arbitrary NLPs , 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 foundational properties of the trap space semantics and systematically relate it to established model-theoretic and dynamical semantics—including the stable (supported), stable (supported) partial, regular, and L-stable model semantics—as well as to dynamical semantics such as the stable (supported) class semantics. Our results demonstrate that the trap space semantics offers a unified framework (along with a proper use of set-theoretic axioms) for proving the existence of supported classes, strict supported classes, strict stable classes, or regular models—proofs that have been unfortunately either missing or imprecise in prior literature [ 5 , 43 , 28 ] . Furthermore, by leveraging the concept of stable or supported trap set underlying the trap space semantics, we correct a flaw in the existing alternative characterization of strict stable or supported classes established in [ 28 ] . Finally, the trap space semantics emerges as a powerful tool for uncovering and formalizing deeper relationships among various existing semantics of NLPs , for instance, the stable (resp. supported) class semantics vs. the stable (resp. supported) partial model semantics, and the regular model semantics vs. the stable class semantics and the L-stable model semantics. The rest of the paper is organized as follows: in Section 2 , we review the necessary background on NLPs and set theory. Section 3 presents the formal definitions of the trap space semantics, as well as its fundamental properties. Section 4 shows the relationships between the trap space semantics and other semantics. In Section 5 , we present the existence results. Section 6 offers concluding remarks and future research directions. 2 Preliminaries 2.1 Normal Logic Programs We assume that the reader is familiar with the logic programming theory and stable model semantics. Unless specifically stated, NLP means normal logic