2025/04/21 by Van-Giang Trinh, Belaïd Benhamou, Trinh, Van-Giang +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Decision Sciences · #Artificial Intelligence (cs.AI) #DNA and Biological Computing #FOS: Computer and information sciences #Gene Regulatory Network Analysis #Logic in Computer Science (cs.LO) #Scientific Computing and Data Management
paper · pdf · doi:10.48550/arxiv.2504.15417
openalex publication_date 2025/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.