Graphical Conditions for the Existence, Unicity and Number of Regular Models

• URL: http://arxiv.org/abs/2502.09220v1
• Date: Thu, 13 Feb 2025 11:50:20 GMT
• Title: Graphical Conditions for the Existence, Unicity and Number of Regular Models
• Abstract summary: 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.
• Score: 0.9374652839580183
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The regular models of a normal logic program are a particular type of partial (i.e. 3-valued) models which correspond to stable partial models with minimal undefinedness. In this paper, we explore graphical conditions on the dependency graph of a finite ground normal logic program to analyze the existence, unicity and number of regular models for the program. We show three main results: 1) a necessary condition for the existence of non-trivial (i.e. non-2-valued) regular models, 2) a sufficient condition for the unicity of regular models, and 3) two upper bounds for the number of regular models based on positive feedback vertex sets. The first two conditions generalize the finite cases of the two existing results obtained by You and Yuan (1994) for normal logic programs with well-founded stratification. The third result is also new to the best of our knowledge. Key to our proofs is a connection that we establish between finite ground normal logic programs and Boolean network theory.

Related papers

• LLMEval-Logic: A Solver-Verified Chinese Benchmark for Logical Reasoning of LLMs with Adversarial Hardening [69.1037790901185]
  We present LLMEval-Logic, a Chinese logical reasoning benchmark built from realistic situational scenarios.<n>Its pipeline forward-authors and expert-audits natural-language items together with their reference formalizations, verifies annotated answers with Z3, constructs expert rubrics for natural-to-formal grading, and hardens selected items through a closed-loop adversarial workflow.
  arXiv  Detail & Related papers  (2026-05-19T09:40:29Z)
• On the Out-of-Distribution Generalization of Reasoning in Multimodal LLMs for Simple Visual Planning Tasks [56.98385132295952]
  We evaluate how well chain-of-thought approaches generalize on a simple planning task.<n>We find that reasoning traces which combine multiple text formats yield the best (and non-trivial) OOD generalization.<n> purely text-based models consistently outperform those utilizing image-based inputs.
  arXiv  Detail & Related papers  (2026-02-17T09:51:40Z)
• Mathematical Proof as a Litmus Test: Revealing Failure Modes of Advanced Large Reasoning Models [11.250861762443801]
  We introduce the RFMDataset (Reveal Failure Modes), a collection of 200 diverse mathematical proof problems.<n>We thoroughly evaluate advanced models' performance on it.<n>Our analysis uncovers 10 fine-grained error types, which shows fundamental limitations in current large reasoning models.
  arXiv  Detail & Related papers  (2025-06-20T16:14:18Z)
• On the Boolean Network Theory of Datalog$^\neg$ [0.9374652839580183]
  We establish a formal link between Datalog$neg$ and Boolean network theory. We show that in the absence of odd cycles in a Datalog$neg$ program, the regular models coincide with the stable models. We also show the uniqueness of stable partial models, which entails the uniqueness of regular models.
  arXiv  Detail & Related papers  (2025-04-21T20:02:59Z)
• Generative Models with ELBOs Converging to Entropy Sums [12.962371546573229]
  Evidence lower bound (ELBO) is one of the most central objectives for unsupervised learning.<n>We prove convergence to entropy sums for several generative models and model classes.
  arXiv  Detail & Related papers  (2024-12-25T15:47:23Z)
• 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)
• 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)
• SeqLink: A Robust Neural-ODE Architecture for Modelling Partially Observed Time Series [11.261457967759688]
  We introduce SeqLink, an innovative neural architecture designed to enhance the robustness of sequence representation. We demonstrate that SeqLink improves the modelling of intermittent time series, consistently outperforming state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-12-07T10:25:59Z)
• MetaLogic: Logical Reasoning Explanations with Fine-Grained Structure [129.8481568648651]
  We propose a benchmark to investigate models' logical reasoning capabilities in complex real-life scenarios. Based on the multi-hop chain of reasoning, the explanation form includes three main components. We evaluate the current best models' performance on this new explanation form.
  arXiv  Detail & Related papers  (2022-10-22T16:01:13Z)
• ExpressivE: A Spatio-Functional Embedding For Knowledge Graph Completion [78.8942067357231]
  ExpressivE embeds pairs of entities as points and relations as hyper-parallelograms in the virtual triple space. We show that ExpressivE is competitive with state-of-the-art KGEs and even significantly outperforms them on W18RR.
  arXiv  Detail & Related papers  (2022-06-08T23:34:39Z)
• On Model Selection Consistency of Lasso for High-Dimensional Ising Models on Tree-like Graphs [13.14903445595385]
  We consider the problem of high-dimensional Ising model selection using neighborhood-based least absolute shrinkage and selection operator (Lasso) It is rigorously proved that consistent model selection can be achieved with sample sizes $n=Omega(d3logp)$ for any tree-like graph in the paramagnetic phase. Given the popularity and efficiency of Lasso, our rigorous analysis provides a theoretical backing for its practical use in Ising model selection.
  arXiv  Detail & Related papers  (2021-10-16T07:23:02Z)
• Probabilistic Modeling for Human Mesh Recovery [73.11532990173441]
  This paper focuses on the problem of 3D human reconstruction from 2D evidence. We recast the problem as learning a mapping from the input to a distribution of plausible 3D poses.
  arXiv  Detail & Related papers  (2021-08-26T17:55:11Z)
• 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)
• Goal-directed Generation of Discrete Structures with Conditional Generative Models [85.51463588099556]
  We introduce a novel approach to directly optimize a reinforcement learning objective, maximizing an expected reward. We test our methodology on two tasks: generating molecules with user-defined properties and identifying short python expressions which evaluate to a given target value.
  arXiv  Detail & Related papers  (2020-10-05T20:03:13Z)
• Minimize Exposure Bias of Seq2Seq Models in Joint Entity and Relation Extraction [57.22929457171352]
  Joint entity and relation extraction aims to extract relation triplets from plain text directly. We propose a novel Sequence-to-Unordered-Multi-Tree (Seq2UMTree) model to minimize the effects of exposure bias.
  arXiv  Detail & Related papers  (2020-09-16T06:53:34Z)
• 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)

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.