# On the Boolean Network Theory of Datalog^neg

arXiv: https://arxiv.org/abs/2504.15417 · HTML: https://mlsanity.com/paper/2504.15417/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 69 references that are in the map.
- First posted on arXiv 21 Apr 2025.

## Builds on (most cited first, 9 of 9)

- [Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard](https://mlsanity.com/paper/2007.04620/) (2020)
- [On the Equivalence Between Abstract Dialectical Frameworks and Logic Programs](https://mlsanity.com/paper/1907.09548/) (2019)
- [mpbn: a simple tool for efficient edition and analysis of elementary properties of Boolean networks](https://mlsanity.com/paper/2403.06255/) (2024)
- [Abstract Dialectical Frameworks are Boolean Networks (full version)](https://mlsanity.com/paper/2407.02055/) (2024)
- [Bridging abstract dialectical argumentation and Boolean gene regulation](https://mlsanity.com/paper/2407.06106/) (2024)
- [Positive Dependency Graphs Revisited](https://mlsanity.com/paper/2207.08579/) (2022)
- [Static Analysis of Logic Programs via Boolean Networks](https://mlsanity.com/paper/2407.09015/) (2024)
- [Graphical Conditions for the Existence, Unicity and Number of Regular Models](https://mlsanity.com/paper/2502.09220/) (2025)
- [On the number of asynchronous attractors in AND-NOT Boolean networks](https://mlsanity.com/paper/2503.19147/) (2025)

## Built on by (most cited first, 1 of 1)

- [On the Trap Space Semantics of Normal Logic Programs](https://mlsanity.com/paper/2601.03842/) (2026)

## Abstract (arXiv)

Datalog^neg 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^neg and Boolean network theory first introduced for gene regulatory networks. We show that in the absence of odd cycles in a Datalog^neg 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^neg 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.