A Logical Characterization of the Preferred Models of Logic Programs
with Ordered Disjunction
- URL: http://arxiv.org/abs/2108.03369v1
- Date: Sat, 7 Aug 2021 05:36:12 GMT
- Title: A Logical Characterization of the Preferred Models of Logic Programs
with Ordered Disjunction
- Authors: Angelos Charalambidis, Panos Rondogiannis, Antonis Troumpoukis
- Abstract summary: 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.
- Score: 1.7403133838762446
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Logic Programs with Ordered Disjunction (LPODs) extend classical logic
programs with the capability of expressing alternatives with decreasing degrees
of preference in the heads of program rules. Despite the fact that the
operational meaning of ordered disjunction is clear, there exists an important
open issue regarding its semantics. In particular, there does not exist a
purely model-theoretic approach for determining the most preferred models of an
LPOD. At present, the selection of the most preferred models is performed using
a technique that is not based exclusively on the models of the program and in
certain cases produces counterintuitive results. We provide a novel,
model-theoretic semantics for LPODs, which uses an additional truth value in
order to identify the most preferred models of a program. We demonstrate that
the proposed approach overcomes the shortcomings of the traditional semantics
of LPODs. Moreover, the 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. This allows programs that can express not
only strict levels of preferences but also alternatives that are equally
preferred. This work is under consideration for acceptance in TPLP.
Related papers
- Faster Cascades via Speculative Decoding [66.16909847419198]
We propose new speculative cascading techniques that implement their deferral rule through speculative execution.
We show that the proposed approach yields better cost-quality trade-offs than cascading and speculative decoding baselines.
arXiv Detail & Related papers (2024-05-29T16:55:08Z) - Coherent Entity Disambiguation via Modeling Topic and Categorical
Dependency [87.16283281290053]
Previous entity disambiguation (ED) methods adopt a discriminative paradigm, where prediction is made based on matching scores between mention context and candidate entities.
We propose CoherentED, an ED system equipped with novel designs aimed at enhancing the coherence of entity predictions.
We achieve new state-of-the-art results on popular ED benchmarks, with an average improvement of 1.3 F1 points.
arXiv Detail & Related papers (2023-11-06T16:40:13Z) - On Loop Formulas with Variables [2.1955512452222696]
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.
arXiv Detail & Related papers (2023-07-15T06:20:43Z) - $\omega$PAP Spaces: Reasoning Denotationally About Higher-Order,
Recursive Probabilistic and Differentiable Programs [64.25762042361839]
$omega$PAP spaces are spaces for reasoning denotationally about expressive differentiable and probabilistic programming languages.
Our semantics is general enough to assign meanings to most practical probabilistic and differentiable programs.
We establish the almost-everywhere differentiability of probabilistic programs' trace density functions.
arXiv Detail & Related papers (2023-02-21T12:50:05Z) - Strong Equivalence of Logic Programs with Ordered Disjunction: a Logical
Perspective [1.160208922584163]
Logic Programs with Ordered Disjunction (LPODs) extend classical logic programs with the capability of expressing preferential disjunctions.
In this paper we obtain a purely logical characterization of strong equivalence of LPODs as logical equivalence in a four-valued logic.
We provide a new proof of the coNP-completeness of strong equivalence for LPODs, which has an interest in its own right since it relies on the special structure of such programs.
arXiv Detail & Related papers (2022-05-10T13:33:32Z) - Structured Reordering for Modeling Latent Alignments in Sequence
Transduction [86.94309120789396]
We present an efficient dynamic programming algorithm performing exact marginal inference of separable permutations.
The resulting seq2seq model exhibits better systematic generalization than standard models on synthetic problems and NLP tasks.
arXiv Detail & Related papers (2021-06-06T21:53:54Z) - 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) - Lexicographic Logic: a Many-valued Logic for Preference Representation [1.5484595752241122]
We propose lexicographic logic, an extension of classical propositional logic that can express a variety of preferences.
We argue that the new logic is an effective formalism for ranking query results according to the satisfaction level of user preferences.
arXiv Detail & Related papers (2020-12-20T14:42:04Z) - Conditional independence by typing [30.194205448457385]
A central goal of probabilistic programming languages (PPLs) is to separate modelling from inference.
Conditional independence (CI) relationships among parameters are a crucial aspect of probabilistic models.
We show that for a well-typed program in our system, the distribution it implements is guaranteed to have certain CI-relationships.
arXiv Detail & Related papers (2020-10-22T17:27:22Z) - Generating Random Logic Programs Using Constraint Programming [12.47276164048813]
We present a novel approach to generating random logic programs using constraint programming.
We show how the model scales with parameter values, and use the model to compare probabilistic inference algorithms across a range of synthetic problems.
arXiv Detail & Related papers (2020-06-02T19:12:53Z) - Pre-training Is (Almost) All You Need: An Application to Commonsense
Reasoning [61.32992639292889]
Fine-tuning of pre-trained transformer models has become the standard approach for solving common NLP tasks.
We introduce a new scoring method that casts a plausibility ranking task in a full-text format.
We show that our method provides a much more stable training phase across random restarts.
arXiv Detail & Related papers (2020-04-29T10:54:40Z)
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.