Several learning systems based on Inverse Entailment (IE) have been proposed, some that compute single clause hypotheses, exemplified by Progol, and others that, produce multiple clauses in response to a single seed e...
详细信息
ISBN:
(纸本)9783642042379
Several learning systems based on Inverse Entailment (IE) have been proposed, some that compute single clause hypotheses, exemplified by Progol, and others that, produce multiple clauses in response to a single seed example. A common denominator of these systems, is a restricted hypothesis search space, within which each clause must individually explain some example E, or some member of an abductive explanation for E. this paper proposes a new IE approach, called Induction on Failure (IoF), that generalises existing Horn clause learning systems by allowing the computation of hypotheses within a larger search space, namely that of Connected theories. A proof procedure for IoF is proposed that generalises existing IE systems and also resolves Yamamoto's example. A prototype implementation is also described. Finally, a semantics is presented called Connected theory Generalisation, which is proved to extend Kernel Set Subsumption and to include hypotheses constructed within this new IoF approach.
作者：
de Groote, PINRIA
LORIA UMR 7503 F-54506 Vandoeuvre Les Nancy France
We reduce the provability of fragments of multiplicative linear logic to matching problems consisting in finding a one-one-correspondence between two sets of first-order terms together with a unifier that equates the ...
详细信息
ISBN:
(纸本)3540412859
We reduce the provability of fragments of multiplicative linear logic to matching problems consisting in finding a one-one-correspondence between two sets of first-order terms together with a unifier that equates the corresponding terms. According to the kind of structure to which these first-order terms belong our matching problem corresponds to provability in the implicative fragment of multiplicative linear logic, in the Lambek calculus, or in the non-associative Lambek calculus.
In recent years, Answer Set programming (ASP), logicprogramming under the stable model or answer set semantics, has seen several extensions by generalizing the notion of an atom in these programs: be it aggregate ato...
详细信息
ISBN:
(纸本)9783642405648
In recent years, Answer Set programming (ASP), logicprogramming under the stable model or answer set semantics, has seen several extensions by generalizing the notion of an atom in these programs: be it aggregate atoms, HEX atoms, generalized quantifiers, or abstract constraints, the idea is to have more complicated satisfaction patterns in the lattice of Herbrand interpretations than traditional, simple atoms. In this paper we refer to any of these constructs as generalized atoms. It is known that programs with generalized atoms that have monotonic or antimonotonic satisfaction patterns do not increase complexity with respect to programs with simple atoms (if satisfaction of the generalized atoms can be decided in polynomial time) under most semantics. It is also known that generalized atoms that are nonmonotonic (being neither monotonic nor antimonotonic) can, but need not, increase the complexity by one level in the polynomial hierarchy if non-disjunctive programs under the FLP semantics are considered. In this paper we provide the precise boundary of this complexity gap: programs with convex generalized atom never increase complexity, while allowing a single non-convex generalized atom (under reasonable conditions) always does. We also discuss several implications of this result in practice.
Brewka and Eiter's nonmonotonic multi-context system is an elegant knowledge representation framework to model heterogeneous and nonmonotonic multiple contexts. Belief change is a central problem in knowledge repr...
详细信息
ISBN:
(纸本)9783642405648
Brewka and Eiter's nonmonotonic multi-context system is an elegant knowledge representation framework to model heterogeneous and nonmonotonic multiple contexts. Belief change is a central problem in knowledge representation and reasoning. In this paper we follow the classical AGM approach to investigate belief change in multi-context systems. Specifically, we formulate semantically the AGM postulates of belief expansion, revision and contraction for multi-context systems. We show that the change operations can be characterized in terms of minimal change by ordering equilibria of multi-context systems. Two distance based revision operators are obtained and related to the classical Satoh and Dalal revision operators (via loop formulas).
In answer set programming systems like Smodels and some SAT solvers, constraint propagation is carried out by a mechanism called lookahead. the question arises as what is the pruning power of lookahead, and how such p...
详细信息
ISBN:
(纸本)3540285385
In answer set programming systems like Smodels and some SAT solvers, constraint propagation is carried out by a mechanism called lookahead. the question arises as what is the pruning power of lookahead, and how such pruning power fares in comparison withthe consistency techniques in solving CSPs. In this paper, we study the pruning power of lookahead by relating it to local consistencies under two different encodings from CSPs to answer set programs. this leads to an understanding of how the search space is pruned in an answer set solver with lookahead for solving CSPs. On the other hand, lookahead as a general constraint propagation mechanism provides a uniform algorithm for enforcing a variety of local consistencies. We also study the impact on the search efficiency under these encodings.
In this paper we define a semantic foundation for an abstract interpretation approach to universal termination and we develop a new abstract domain useful for termination analysis. Based on this approximation we defin...
详细信息
ISBN:
(纸本)3540412859
In this paper we define a semantic foundation for an abstract interpretation approach to universal termination and we develop a new abstract domain useful for termination analysis. Based on this approximation we define a method which is able to detect classes of goals which universally terminate (with a fair selection rule). We also define a method which is able to characterize classes of programs and goals for which depth-first search is fair.
We present a new logicprogramming approach to contextual reasoning, based on the Weak Completion Semantics (WCS), the latter of which has been successfully applied in the past to adequately model various human reason...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
We present a new logicprogramming approach to contextual reasoning, based on the Weak Completion Semantics (WCS), the latter of which has been successfully applied in the past to adequately model various human reasoning tasks. One of the properties of WCS is the open world assumption with respect to undefined atoms. this is a characteristic that is different to other common logicprogramming semantics, a property that seems suitable when modeling human reasoning. Notwithstanding, we have noticed that the famous Tweety default reasoning example, originally introduced by Reiter, cannot be modeled straightforwardly under WCS. Hence, to address the issue and taking Pereira and Pinto's inspection points as inspiration, we develop a notion of contextual reasoning for which we introduce contextual logic programs. We reconsider the formal properties of WCS with respect to these and verify whether they still hold. Finally, we set forth contextual abduction and show that not only the original Tweety example can be nicely modeled within the new approach, but more sophisticated examples as well, where context plays an important role.
this book constitutes the refereed proceedings of the 15thinternationalconference on logicprogramming and nonmonotonicreasoning, LPNMR 2019, held in Philadelphia, PA, USA, in June 2019.
ISBN:
(数字)9783030205287
ISBN:
(纸本)9783030205270
this book constitutes the refereed proceedings of the 15thinternationalconference on logicprogramming and nonmonotonicreasoning, LPNMR 2019, held in Philadelphia, PA, USA, in June 2019.
We describe the first automatic approach for merging coreference annotations obtained from multiple annotators into a single gold standard. Merging is subject to hard constraints (consistency) and optimization criteri...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
We describe the first automatic approach for merging coreference annotations obtained from multiple annotators into a single gold standard. Merging is subject to hard constraints (consistency) and optimization criteria (minimal divergence from annotators) and involves an equivalence relation over a large number of elements. We describe two representations of the problem in Answer Set programming and four objective functions suitable for the task. We provide two structurally different real-world benchmark datasets based on the METU-Sabanci Turkish Treebank, and we report our experiences in using the Gringo, Clasp, and Wasp tools for computing optimal adjudication results on these datasets.
Internet routing is the process of selecting paths across the Internet to connect the communicating hosts, it is unique in that path selection is jointly determined by a network of independently operated networks, kno...
详细信息
ISBN:
(纸本)9783030205287;9783030205270
Internet routing is the process of selecting paths across the Internet to connect the communicating hosts, it is unique in that path selection is jointly determined by a network of independently operated networks, known as domains or Autonomous Systems (ASes), that interconnect to form the Internet. In fact, the present routing infrastructure takes such an extreme position that it favors local autonomy-an AS can use arbitrary path preference to override the default shortest path policy, at the expense of potential global oscillation-a collection of AS preferences (policies) can fail to converge on a stable path, a paththat is also the most preferred possible for every AS along the path. In this paper, we examine the route oscillation problem with non-monotonic reasoning. We observe that, in the absence of any AS specific policies, Internet routing degenerates into the monotonic computation of shortest path-a preferred (shorter) (super)path always extends another preferred (sub)path;But fully autonomous AS policies are non-monotonic a path favored by one AS can be an extension of a less preferred path of a neighbor, to which an "upgrade" to a better path can cause this AS to downgrade to a less preferred path previously discarded. Based on this insight, we present an Answer Set programming (ASP) formulation that allows for automatic oscillation detection. Our evaluation using the clingo ASP solver is promising: on realistic Internet topology and representative policies, clingo can detect anomalies within 35 s.
暂无评论