On Loop Formulas with Variables

• URL: http://arxiv.org/abs/2307.10226v1
• Date: Sat, 15 Jul 2023 06:20:43 GMT
• Title: On Loop Formulas with Variables
• Authors: Joohyung Lee, Yunsong Meng
• Abstract summary: Recently Ferraris, Lee and Lifschitz proposed a new definition of stable models that does not refer to grounding. We show its relation to the idea of loop formulas with variables by Chen, Lin, Wang and Zhang. We extend the syntax of logic programs to allow explicit quantifiers, and define its semantics as a subclass of the new language of stable models.
• Score: 2.1955512452222696
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently Ferraris, Lee and Lifschitz proposed a new definition of stable models that does not refer to grounding, which applies to the syntax of arbitrary first-order sentences. We show its relation to the idea of loop formulas with variables by Chen, Lin, Wang and Zhang, and generalize their loop formulas to disjunctive programs and to arbitrary first-order sentences. We also extend the syntax of logic programs to allow explicit quantifiers, and define its semantics as a subclass of the new language of stable models by Ferraris et al. Such programs inherit from the general language the ability to handle nonmonotonic reasoning under the stable model semantics even in the absence of the unique name and the domain closure assumptions, while yielding more succinct loop formulas than the general language due to the restricted syntax. We also show certain syntactic conditions under which query answering for an extended program can be reduced to entailment checking in first-order logic, providing a way to apply first-order theorem provers to reasoning about non-Herbrand stable models.

Related papers

• 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)
• Past-present temporal programs over finite traces [1.4835015204811504]
  We study the so-called past-present syntactic subclass, which consists of a set of logic programming rules whose body references to the past and head to the present. We extend the definitions of completion and loop formulas to the case of past-present formulas, which allows capturing the temporal stable models of a set of past-present temporal programs.
  arXiv  Detail & Related papers  (2023-07-24T08:50:12Z)
• Semantic Role Labeling Meets Definition Modeling: Using Natural Language to Describe Predicate-Argument Structures [104.32063681736349]
  We present an approach to describe predicate-argument structures using natural language definitions instead of discrete labels. Our experiments and analyses on PropBank-style and FrameNet-style, dependency-based and span-based SRL also demonstrate that a flexible model with an interpretable output does not necessarily come at the expense of performance.
  arXiv  Detail & Related papers  (2022-12-02T11:19:16Z)
• Hierarchical Phrase-based Sequence-to-Sequence Learning [94.10257313923478]
  We describe a neural transducer that maintains the flexibility of standard sequence-to-sequence (seq2seq) models while incorporating hierarchical phrases as a source of inductive bias during training and as explicit constraints during inference. Our approach trains two models: a discriminative derivation based on a bracketing grammar whose tree hierarchically aligns source and target phrases, and a neural seq2seq model that learns to translate the aligned phrases one-by-one.
  arXiv  Detail & Related papers  (2022-11-15T05:22:40Z)
• Benchmarking Language Models for Code Syntax Understanding [79.11525961219591]
  Pre-trained language models have demonstrated impressive performance in both natural language processing and program understanding. In this work, we perform the first thorough benchmarking of the state-of-the-art pre-trained models for identifying the syntactic structures of programs. Our findings point out key limitations of existing pre-training methods for programming languages, and suggest the importance of modeling code syntactic structures.
  arXiv  Detail & Related papers  (2022-10-26T04:47:18Z)
• Learning to Reason With Relational Abstractions [65.89553417442049]
  We study how to build stronger reasoning capability in language models using the idea of relational abstractions. We find that models that are supplied with such sequences as prompts can solve tasks with a significantly higher accuracy.
  arXiv  Detail & Related papers  (2022-10-06T00:27:50Z)
• Rationale-Augmented Ensembles in Language Models [53.45015291520658]
  We reconsider rationale-augmented prompting for few-shot in-context learning. We identify rationale sampling in the output space as the key component to robustly improve performance. We demonstrate that rationale-augmented ensembles achieve more accurate and interpretable results than existing prompting approaches.
  arXiv  Detail & Related papers  (2022-07-02T06:20:57Z)
• Logical Satisfiability of Counterfactuals for Faithful Explanations in NLI [60.142926537264714]
  We introduce the methodology of Faithfulness-through-Counterfactuals. It generates a counterfactual hypothesis based on the logical predicates expressed in the explanation. It then evaluates if the model's prediction on the counterfactual is consistent with that expressed logic.
  arXiv  Detail & Related papers  (2022-05-25T03:40:59Z)
• Foundations of Symbolic Languages for Model Interpretability [2.3361634876233817]
  We study the computational complexity of FOIL queries over two classes of ML models often deemed to be easily interpretable. We present a prototype implementation of FOIL wrapped in a high-level declarative language.
  arXiv  Detail & Related papers  (2021-10-05T21:56:52Z)
• A Logical Characterization of the Preferred Models of Logic Programs with Ordered Disjunction [1.7403133838762446]
  We provide a novel, model-theoretic semantics for Logic Programs with Ordered Disjunction (LPODs) We demonstrate that the proposed approach overcomes the shortcomings of the traditional semantics of LPODs. New approach can be used to define the semantics of a natural class of logic programs that can have both ordered and classical disjunctions in the heads of clauses.
  arXiv  Detail & Related papers  (2021-08-07T05:36:12Z)
• Temporal Answer Set Programming [3.263632801414296]
  We present an overview on Temporal Logic Programming under the perspective of its application for Knowledge Representation and declarative problem solving. We focus on recent results of the non-monotonic formalism called Temporal Equilibrium Logic (TEL) that is defined for the full syntax. In a second part, we focus on practical aspects, defining a syntactic fragment called temporal logic programs closer to ASP, and explain how this has been exploited in the construction of the solver TELINGO.
  arXiv  Detail & Related papers  (2020-09-14T16:13:36Z)

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.