On the Boolean Network Theory of Datalog$^\neg$

• URL: http://arxiv.org/abs/2504.15417v2
• Date: Mon, 19 May 2025 22:00:47 GMT
• Title: On the Boolean Network Theory of Datalog$^\neg$
• Abstract summary: 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.
• Score: 0.9374652839580183
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• World models of environment, agent and joint agent-environment systems [76.81951414842736]
  We argue that there is a prior distinction: which channel they model.<n>We consider three cases: the environment channel $O_: mid A_:$, the agent channel $A_: mid O_:$, and the realised joint process $(A, O)_:$, equivalently viewed as a channel with no inputs.
  arXiv  Detail & Related papers  (2026-07-23T13:35:03Z)
• Weighted Rules under the Stable Model Semantics [4.756254991351937]
  We introduce the concept of weighted rules under the stable model semantics following the log-linear models of Markov Logic.<n>This provides versatile methods to overcome the deterministic nature of the stable model semantics.
  arXiv  Detail & Related papers  (2026-05-10T13:05:44Z)
• On the Trap Space Semantics of Normal Logic Programs [2.274915755738124]
  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.
  arXiv  Detail & Related papers  (2026-01-07T12:06:26Z)
• Discrete Bayesian Sample Inference for Graph Generation [48.418206985863726]
  We introduce GraphBSI, a novel one-shot graph generative model based on Bayesian Sample Inference (BSI)<n>We state BSI as a differential equation (SDE) and derive a noise-controlled family of SDEs that preserves the marginal distributions via an approximation of the score function.<n>In our empirical evaluation, we demonstrate state-of-the-art performance on molecular and synthetic graph generation, outperforming existing one-shot graph generative models.
  arXiv  Detail & Related papers  (2025-11-04T21:25:51Z)
• Causal Discovery for Linear Non-Gaussian Models with Disjoint Cycles [3.425341633647624]
  We develop an algorithm for learning causal structures with disjoint cycles.<n>We show that simple quadratic and cubic relations among low-order moments of a non-Gaussian distribution allow one to locate source cycles.
  arXiv  Detail & Related papers  (2025-07-14T19:45:23Z)
• Causal Models for Growing Networks [4.055489363682199]
  We first enumerate the 96 causal directed acyclic graph (DAG) models over pairs of nodes.<n>We then partition them into 21 classes with ancestral sets that are closed under node marginalization.
  arXiv  Detail & Related papers  (2025-04-01T17:52:24Z)
• Graphical Conditions for the Existence, Unicity and Number of Regular Models [0.9374652839580183]
  We analyze the existence, unicity and number of regular models for a finite ground normal logic program.<n>Key to our proofs is a connection that we establish between finite ground normal logic programs and Boolean network theory.
  arXiv  Detail & Related papers  (2025-02-13T11:50:20Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework.<n>We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points.<n>Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• 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)
• The Foundations of Tokenization: Statistical and Computational Concerns [51.370165245628975]
  Tokenization is a critical step in the NLP pipeline.<n>Despite its recognized importance as a standard representation method in NLP, the theoretical underpinnings of tokenization are not yet fully understood.<n>The present paper contributes to addressing this theoretical gap by proposing a unified formal framework for representing and analyzing tokenizer models.
  arXiv  Detail & Related papers  (2024-07-16T11:12:28Z)
• Fuzzy Datalog$^\exists$ over Arbitrary t-Norms [5.464669506214195]
  One of the main challenges in the area of Neuro-Symbolic AI is to perform logical reasoning in the presence of both neural and symbolic data. This requires combining heterogeneous data sources such as knowledge graphs, neural model predictions, structured databases, crowd-sourced data, and many more. We generalise the standard rule-based language Datalog with existential rules to the setting, by allowing for arbitrary t-norms in the place of classical conjunctions in rule bodies. The resulting formalism allows us to perform reasoning about associated data with degrees of uncertainty while preserving computational complexity results and the applicability of reasoning techniques established for
  arXiv  Detail & Related papers  (2024-03-05T12:51:40Z)
• Positive concave deep equilibrium models [7.148312060227714]
  Deep equilibrium (DEQ) models are a memory efficient alternative to standard neural networks. We introduce a novel class of DEQ models called positive concave deep equilibrium (pcDEQ) models. Our approach, which is based on nonlinear Perron-Frobenius theory, enforces nonnegative weights and activation functions that are concave on the positive orthant.
  arXiv  Detail & Related papers  (2024-02-06T14:24:29Z)
• Causal models in string diagrams [0.0]
  The framework of causal models provides a principled approach to causal reasoning, applied today across many scientific domains. We present this framework in the language of string diagrams, interpreted formally using category theory. We argue and demonstrate that causal reasoning according to the causal model framework is most naturally and intuitively done as diagrammatic reasoning.
  arXiv  Detail & Related papers  (2023-04-15T21:54:48Z)
• Super-model ecosystem: A domain-adaptation perspective [101.76769818069072]
  This paper attempts to establish the theoretical foundation for the emerging super-model paradigm via domain adaptation. Super-model paradigms help reduce computational and data cost and carbon emission, which is critical to AI industry.
  arXiv  Detail & Related papers  (2022-08-30T09:09:43Z)
• Discovering Invariant Rationales for Graph Neural Networks [104.61908788639052]
  Intrinsic interpretability of graph neural networks (GNNs) is to find a small subset of the input graph's features. We propose a new strategy of discovering invariant rationale (DIR) to construct intrinsically interpretable GNNs.
  arXiv  Detail & Related papers  (2022-01-30T16:43:40Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• On the Generative Utility of Cyclic Conditionals [103.1624347008042]
  We study whether and how can we model a joint distribution $p(x,z)$ using two conditional models $p(x|z)$ that form a cycle. We propose the CyGen framework for cyclic-conditional generative modeling, including methods to enforce compatibility and use the determined distribution to fit and generate data.
  arXiv  Detail & Related papers  (2021-06-30T10:23:45Z)
• Stabilizing Equilibrium Models by Jacobian Regularization [151.78151873928027]
  Deep equilibrium networks (DEQs) are a new class of models that eschews traditional depth in favor of finding the fixed point of a single nonlinear layer. We propose a regularization scheme for DEQ models that explicitly regularizes the Jacobian of the fixed-point update equations to stabilize the learning of equilibrium models. We show that this regularization adds only minimal computational cost, significantly stabilizes the fixed-point convergence in both forward and backward passes, and scales well to high-dimensional, realistic domains.
  arXiv  Detail & Related papers  (2021-06-28T00:14:11Z)
• Improving Label Quality by Jointly Modeling Items and Annotators [68.8204255655161]
  We propose a fully Bayesian framework for learning ground truth labels from noisy annotators. Our framework ensures scalability by factoring a generative, Bayesian soft clustering model over label distributions into the classic David and Skene joint annotator-data model.
  arXiv  Detail & Related papers  (2021-06-20T02:15:20Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  Probabilistic sentential decision diagrams are logic circuits where the inputs of disjunctive gates are annotated by probability values. We develop the credal sentential decision diagrams, a generalisation of their probabilistic counterpart that allows for replacing the local probabilities with credal sets of mass functions. For a first empirical validation, we consider a simple application based on noisy seven-segment display images.
  arXiv  Detail & Related papers  (2020-08-19T16:04:34Z)
• Monotone operator equilibrium networks [97.86610752856987]
  We develop a new class of implicit-depth model based on the theory of monotone operators, the Monotone Operator Equilibrium Network (monDEQ) We show the close connection between finding the equilibrium point of an implicit network and solving a form of monotone operator splitting problem. We then develop a parameterization of the network which ensures that all operators remain monotone, which guarantees the existence of a unique equilibrium point.
  arXiv  Detail & Related papers  (2020-06-15T17:57:31Z)
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models [5.983753938303726]
  We study the hierarchy of communities in real-world networks under a generic block model. We prove the strong consistency of this method under a wide range of model parameters. Unlike most of existing work, our theory covers multiscale networks where the connection probabilities may differ by orders of magnitude.
  arXiv  Detail & Related papers  (2020-04-30T01:08:59Z)

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.