On the Boolean Network Theory of Datalog ¬
VAN-GIANG TRINH, BELAID BENHAMOU, SYLVAIN SOLIMAN, FRANÇOIS FAGES · 2025
Read On the Boolean Network Theory of Datalog ¬ by VAN-GIANG TRINH, BELAID BENHAMOU, SYLVAIN SOLIMAN, FRANÇOIS FAGES (2025) 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-2504-15417.txt.
Introduction
Van-Giang Trinh and co-authors link two fields in a 2025 paper: a database logic called Datalog with negation, and the theory of Boolean networks, first built to model gene control. The logic is used in areas from deductive databases to argument frameworks and answer set programming. Its meaning rests on several kinds of models, among them supported, stable, regular, and well-founded models.
The authors prove firm ties between the logic programs and the networks. When a program has no odd cycles, its regular models match its stable models, which also proves stable models exist. When it has no even cycles, the stable partial models and regular models are each unique. The link also yields new upper bounds on how many models of each kind a program can have.
Catalog record
| CREATOR | VAN-GIANG TRINH, BELAID BENHAMOU, SYLVAIN SOLIMAN, FRANÇOIS FAGES |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 132 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-15417
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Boolean Network Theory of Datalog ¬ VAN-GIANG TRINH, BELAID BENHAMOU, SYLVAIN SOLIMAN, FRANÇOIS FAGES Abstract Datalog ¬ is a central formalism used in a variety of domains ranging from deductive databases and abstract argumentation frameworks to answer set programming. Its model theory is the finite counterpart of the logical semantics developed for normal logic programs, mainly based on the notions of Clark’s completion and two-valued or three-valued canonical models including supported, stable, regular and well-founded models. In this paper we establish a formal link between Datalog ¬ and Boolean network theory first introduced for gene regulatory networks. We show that in the absence of odd cycles in a Datalog ¬ program, the regular models coincide with the stable models, which entails the existence of stable models, and in the absence of even cycles, we prove the uniqueness of stable partial models and regular models. This connection also gives new upper bounds on the numbers of stable partial, regular, and stable models of a Datalog ¬ program using the cardinality of a feedback vertex set in its atom dependency graph. Interestingly, our connection to Boolean network theory also points us to the notion of trap spaces. In particular we show the equivalence between subset-minimal stable trap spaces and regular models. keywords deductive database, Datalog, model-theoretic semantics, dynamics, Boolean network, trap space, attractor, model counting, feedback vertex set Inria Saclay, EP Lifeware, Palaiseau, France LIRICA team, LIS, Aix-Marseille University, Marseille, France Inria Saclay, EP Lifeware, Palaiseau, France Inria Saclay, EP Lifeware, Palaiseau, France 1 Introduction Datalog ¬ is a central formalism of non-monotonic logic that plays a vital role in a variety of computational domains, including deductive databases, answer set programming, and abstract argumentation frameworks ( Ceri et al., 1990 ; Eiter et al., 1997 ; Seitzer and Schlipf, 1997 ; Niemelä, 1999 ; Wu et al., 2009 ; Alviano et al., 2012 ; Janhunen and Niemelä, 2016 ; Caminada and Schulz, 2017 ) . As a syntactic restriction of normal logic programs to function-free rules and finite Herbrand universes, Datalog ¬ benefits from favorable computational properties while retaining expressive non-monotonic logical semantics ( Ceri et al., 1990 ; Sato, 1990 ; Guessarian and Peixoto, 1994 ; Niemelä, 1999 ; Basta et al., 2002 ) . The model theory of Datalog ¬ is closely tied to the well-established logical semantics developed for normal logic programs ( You and Yuan, 1995 ) . These include two-valued and three-valued semantics such as supported models , stable models , regular models , and the well-founded models , which are typically defined in terms of Clark’s completion and its associated fixpoint or model-theoretic characterizations ( Clark, 1977 ; Lloyd, 1984 ; Przymusinski, 1990 ; Przymusinski, 1994 ; You and Yuan, 1994 ; Saccà and Zaniolo, 1997 ; Eiter et al., 1997 ) . In addition, some semantics such as the stable, or supported class semantics have been proposed to represent the dynamical behavior of a normal logic program ( Baral and Subrahmanian, 1992 ; Inoue and Sakama, 2012 ) . Each of these semantics provides different insights into the meaning of a logic program, and understanding their relationships is crucial for both theoretical and practical applications. In this paper 1 1 1 This paper is a significantly extended and revised version of the paper presented at ICLP 2024 ( Trinh et al., 2024b ) which derived first results from Boolean network theory to propositional logic programs. Here we adopt the first-order setting of Datalog ¬ programs and present some results for normal logic programs. , we investigate the semantics of Datalog ¬ programs through a new and perhaps unexpected lens: the theory of Boolean networks , a formalism originally introduced by Stuart Kauffman and René Thomas to model gene regulatory networks ( Kauffman, 1969 ; Thomas, 1973 ) . Boolean networks have since evolved into a rich mathematical framework used to study the dynamical behavior of discrete systems, leading to a wide range of applications from science to engineering, especially in systems biology ( Schwab et al., 2020 ; Trinh et al., 2023 ) . Notably, Datalog ¬ programs have been widely applied to modeling and analysis of Boolean networks ( Inoue, 2011 ; Klarner et al., 2015 ; Trinh et al., 2023 ; Khaled et al., 2023 ; Trinh et al., 2024a ) . The preliminary link between Datalog ¬ programs and Boolean networks can be traced back to the theoretical work by Inoue, (2011) . It defined a Boolean network encoding for Datalog ¬ programs, which relies on the notion of Clark’s completion ( Clark, 1977 ) , and pointed out that the two-valued models of the Clark’s completion of a Datalog ¬ program one-to-one correspond to the fixed points of the encoded Boolean network. The subsequent work ( Inoue and Sakama, 2012 ) pointed out that the strict supported classes of a Datalog ¬ program one-to-one correspond to the synchronous attractors of the encoded Boolean network. However, this line of work did not explore the structural relationships in detail, nor did it examine connections with other higher-level semantics. Moreover, the discussion remained largely conceptual and did not extend to concrete implications for the analysis of Datalog ¬ programs. In this work, we establish a formal connection between Datalog ¬ and Boolean network theory by 1) mapping the dependency structure of atoms in a Datalog ¬ program ( Apt et al., 1988 ) to the influence graph of a Boolean network ( Richard, 2019 ) , and 2) relating the supported or stable partial model semantics ( Przymusinski, 1994 ; Saccà and Zaniolo, 1997 ) and the regular model semantics ( You and Yuan, 1994 ; Saccà and Zaniolo, 1997 ) to the notion of trap spaces in Boolean networks ( Klarner et al., 2015 ; Trinh et al., 2023 ) . This connection allows us to transfer a variety of structural results from Boolean network theory ( Remy et al., 2003 ; Richard and Ruet, 2013 ; Richard, 2019 ; Schwab et al., 2020 ; Richard and Tonello, 2023 ) to the analysis of Datalog ¬ programs. Relating graphical representations of a normal logic program and its semantics is an interesting research direction in theory that also has many useful applications in practice ( Sato, 1990 ; Fages, 1994 ; Cholewinski and Truszczynski, 1999 ; Linke, 2001 ; Lin and Zhao, 2004 ; Costantini, 2006 ; Fichte, 2011 ; Fandinno and Hecher, 2021 ) . Historically, the first studies in this direction focused on the existence of a unique stable model in classes of programs with special graphical properties on (positive) atom dependency graphs, including positive programs ( Gelfond and Lifschitz, 1988 ) , acyclic programs ( Apt and Bezem, 1991 ) , and locally stratified programs ( Gelfond and Lifschitz, 1988 ) . The work by Fages, (1991) gave a simple characterization of stable models as well-supported models, and then showed that for tight programs (i.e. without non-well-founded positive justifications), the stable models of the program coincide with the two-valued models of its Clark’s completion ( Fages, 1994 ) . Being finer-represented but more computationally expensive than atom dependency graphs, several other graphical representations (e.g., cycle and extended dependency graphs,