Sequential composition of answer set programs

• URL: http://arxiv.org/abs/2104.12156v6
• Date: Wed, 12 Jun 2024 10:51:34 GMT
• Title: Sequential composition of answer set programs
• Authors: Christian Antić,
• Abstract summary: This paper contributes to the mathematical foundations of logic programming by introducing and studying the sequential composition of answer set programs. In a broader sense, this paper is a first step towards an algebra of answer set programs and in the future we plan to lift the methods of this paper to wider classes of programs.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper contributes to the mathematical foundations of logic programming by introducing and studying the sequential composition of answer set programs. On the semantic side, we show that the immediate consequence operator of a program can be represented via composition, which allows us to compute the least model semantics of Horn programs without any explicit reference to operators. As a result, we can characterize answer sets algebraically, which further provides an algebraic characterization of strong and uniform equivalence which is appealing. This bridges the conceptual gap between the syntax and semantics of an answer set program in a mathematically satisfactory way. The so-obtained algebraization of answer set programming allows us to transfer algebraic concepts into the ASP-setting which we demonstrate by introducing the index and period of an answer set program as an algebraic measure of its cyclicality. The technical part of the paper ends with a brief section introducing the algebraically inspired novel class of aperiodic answer set programs strictly containing the acyclic ones. In a broader sense, this paper is a first step towards an algebra of answer set programs and in the future we plan to lift the methods of this paper to wider classes of programs, most importantly to higher-order and disjunctive programs and extensions thereof.

Related papers

• ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
  We characterize several different forms of compositional generalization that are desirable in program synthesis. We propose ExeDec, a novel decomposition-based strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step.
  arXiv  Detail & Related papers  (2023-07-26T01:07:52Z)
• HPE:Answering Complex Questions over Text by Hybrid Question Parsing and Execution [92.69684305578957]
  We propose a framework of question parsing and execution on textual QA. The proposed framework can be viewed as a top-down question parsing followed by a bottom-up answer backtracking. Our experiments on MuSiQue, 2WikiQA, HotpotQA, and NQ show that the proposed parsing and hybrid execution framework outperforms existing approaches in supervised, few-shot, and zero-shot settings.
  arXiv  Detail & Related papers  (2023-05-12T22:37:06Z)
• Sequential decomposition of propositional logic programs [0.0]
  This paper studies the sequential decomposition of programs by studying Green's relations between programs. In a broader sense, this paper is a further step towards an algebraic theory of logic programming.
  arXiv  Detail & Related papers  (2023-02-21T16:14:57Z)
• A Divide-Align-Conquer Strategy for Program Synthesis [8.595181704811889]
  We show that compositional segmentation can be applied in the programming by examples setting to divide the search for large programs across multiple smaller program synthesis problems. A structural alignment of the constituent parts in the input and output leads to pairwise correspondences used to guide the program search.
  arXiv  Detail & Related papers  (2023-01-08T19:10:55Z)
• UniRPG: Unified Discrete Reasoning over Table and Text as Program Generation [32.74302320558048]
  We propose UniRPG, a semantic-parsing-based approach advanced in interpretability and scalability. UniRPG performs unified discrete reasoning over heterogeneous knowledge resources, i.e., table and text, as program generation. It achieves tremendous improvements and enhances interpretability and scalability compared with state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-10-15T10:17:52Z)
• Non-determinsitic algebraic rewriting as adjunction [0.0]
  We develop a general model theoretic semantics to rewriting beyond the usual confluence and termination assumptions. This is based on preordered algebra which is a model theory that extends many sorted algebra.
  arXiv  Detail & Related papers  (2022-04-26T07:55:09Z)
• ProTo: Program-Guided Transformer for Program-Guided Tasks [59.34258016795216]
  We formulate program-guided tasks which require learning to execute a given program on the observed task specification. We propose the Program-guided Transformer (ProTo), which integrates both semantic and structural guidance of a program. ProTo executes a program in a learned latent space and enjoys stronger representation ability than previous neural-symbolic approaches.
  arXiv  Detail & Related papers  (2021-10-02T13:46:32Z)
• Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
  We propose LeAR, an end-to-end neural model to learn algebraic recombination for compositional generalization. Key insight is to model the semantic parsing task as a homomorphism between a latent syntactic algebra and a semantic algebra. Experiments on two realistic and comprehensive compositional generalization demonstrate the effectiveness of our model.
  arXiv  Detail & Related papers  (2021-07-14T07:23:46Z)
• Representing Partial Programs with Blended Abstract Semantics [62.20775388513027]
  We introduce a technique for representing partially written programs in a program synthesis engine. We learn an approximate execution model implemented as a modular neural network. We show that these hybrid neuro-symbolic representations enable execution-guided synthesizers to use more powerful language constructs.
  arXiv  Detail & Related papers  (2020-12-23T20:40:18Z)
• Latent Programmer: Discrete Latent Codes for Program Synthesis [56.37993487589351]
  In many sequence learning tasks, such as program synthesis and document summarization, a key problem is searching over a large space of possible output sequences. We propose to learn representations of the outputs that are specifically meant for search: rich enough to specify the desired output but compact enough to make search more efficient. We introduce the emphLatent Programmer, a program synthesis method that first predicts a discrete latent code from input/output examples, and then generates the program in the target language.
  arXiv  Detail & Related papers  (2020-12-01T10:11:35Z)
• Sequential composition of propositional logic programs [0.0]
  We show that acyclic programs can be decomposed into single-rule programs and provide a general decomposition result for arbitrary programs. We show that the immediate consequence operator of a program can be represented via composition which allows us to compute its least model without any explicit reference to operators.
  arXiv  Detail & Related papers  (2020-09-12T11:57:30Z)

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.