We present a logic interpreted over integer arrays, which allows difference bound comparisons between array elements situated within constant sized window. We show that the satisfiability problem for the logic is Unde...
详细信息
ISBN:
(纸本)9783540894384
We present a logic interpreted over integer arrays, which allows difference bound comparisons between array elements situated within constant sized window. We show that the satisfiability problem for the logic is Undecidable for formulae with a quantifier prefix {there exists, for all} *for all*there exists*for all*. For formulae With quantifier prefixes in the there exists*for all* fragment, decidability is established by an automata-theoretic argument. For each formula in the there exists*for all* fragment, we can build a flat counter automaton with difference bound transition rules (FCADBM) whose traces correspond to the models of the formula. the construction is modular, following the syntax of the formula. Decidability of the there exists*for all* fragment of the logic is a consequence of the fact that reachability of a control state is decidable for FCADBM.
this paper introduces Compositional Neural logicprogramming (CNLP), a framework that integrates neural networks and logicprogramming for symbolic and sub-symbolic reasoning. We adopt the idea of compositional neural...
详细信息
ISBN:
(纸本)9780999241196
this paper introduces Compositional Neural logicprogramming (CNLP), a framework that integrates neural networks and logicprogramming for symbolic and sub-symbolic reasoning. We adopt the idea of compositional neural networks to represent first-order logic predicates and rules. A voting backward-forward chaining algorithm is proposed for inference with both symbolic and sub-symbolic variables in an argument-retrieval style. the framework is highly flexible in that it can be constructed incrementally with new knowledge, and it also supports batch reasoning in certain cases. In the experiments, we demonstrate the advantages of CNLP in discriminative tasks and generative tasks.
Disjunctive logicprogramming (DLP) with stable model semantics is a powerful nonmonotonic formalism for knowledge representation and reasoning. reasoning with DLP is harder than with normal (boolean OR-free) logic pr...
详细信息
Disjunctive logicprogramming (DLP) with stable model semantics is a powerful nonmonotonic formalism for knowledge representation and reasoning. reasoning with DLP is harder than with normal (boolean OR-free) logic programs, because stable model checking-deciding whether a given model is a stable model of a propositional DLP program-is co-NP-complete, while it is polynomial for normal logic programs. this paper proposes a new transformation Gamma(M) (P), which reduces stable model checking to UNSAT-i.e., to deciding whether a given CNF formula is unsatisfiable. the stability of a model M of a program P thus can be verified by calling a Satisfiability Checker on the CNF formula Gamma(M) (P). the transformation is parsimonious (i.e., no new symbol is added), and efficiently computable, as it runs in logarithmic space (and therefore in polynomial time). Moreover, the size of the generated CNF formula never exceeds the size of the input (and is usually much smaller). We complement this transformation with modular evaluation results, which allow for efficient handling of large real-world reasoning problems. the proposed approach to stable model checking has been implemented in DLV-a state-of-the-art implementation of DLP. A number of experiments and benchmarks have been run using SATZ as Satisfiability checker. the results of the experiments are very positive and confirm the usefulness of our techniques. (C) 2003 Elsevier B.V. All rights reserved.
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.
the extend the Constraint logicprogramming (CLP) formalism in order to handle semiring-based constraint systems. this allows us to perform in the same language both constraint solving and optimization. In fact, const...
详细信息
ISBN:
(纸本)1558604804
the extend the Constraint logicprogramming (CLP) formalism in order to handle semiring-based constraint systems. this allows us to perform in the same language both constraint solving and optimization. In fact, constraint systems based on semirings are able to model both classical constraint solving and more sophisticated features like uncertainty, probability, fuzzyness, and optimization. We then provide this class of languages withthree equivalent semantics: model-theoretic, fixpoint and proof-theoretic, in the style of CLP programs.
Nonmonotonic reasoning is virtually absent from industry and has been so since its inception;the result is that the field is becoming marginalized within AI. I argue that this is because researchers in the area focus ...
详细信息
ISBN:
(纸本)1558604804
Nonmonotonic reasoning is virtually absent from industry and has been so since its inception;the result is that the field is becoming marginalized within AI. I argue that this is because researchers in the area focus exclusively on commonsense problems which are irrelevant to industry and because few efficient algorithms and/or tools have been developed. A sensible strategy is thus to focus on industry problems and to develop solutions within tractable sub-theories of nonmonotonic logic. I examine one of the few examples of nonmonotonic reasoning in industry - inheritance of business rules in the medical insurance domain - and show how the paradigm of inheritance with exceptions can be extended to a broader and more powerful kind of nonmonotonic reasoning. Finally I discuss the underlying lessons that can be generalized to other industry problems.
Defeasible reasoning is a rule-based approach for efficient reasoning with incomplete and inconsistent information. Such reasoning is, among others, useful for ontology integration, where conflicting information arise...
详细信息
ISBN:
(纸本)076952236X
Defeasible reasoning is a rule-based approach for efficient reasoning with incomplete and inconsistent information. Such reasoning is, among others, useful for ontology integration, where conflicting information arises naturally;and for the modeling of business rules and policies, where rules with exceptions are often used this paper describes these scenarios in more detail, and reports on the implementation of a system for defeasible reasoning on the Web. the system (a) is syntactically compatible with RuleML;(b) features strict and defeasible rules and priorities;(c) is based on a translation to logicprogramming with declarative semantics;and (d) is flexible and adaptable to different intuitions within defeasible reasoning.
the program composition approach can be fruitfully applied to combine general logic programs, i.e, logic programs possibly containing negative premises. We show how the introduction of a basic set of (meta-level) comp...
详细信息
ISBN:
(纸本)3540632557
the program composition approach can be fruitfully applied to combine general logic programs, i.e, logic programs possibly containing negative premises. We show how the introduction of a basic set of (meta-level) composition operations over general programs increases the knowledge representation capabilities of logicprogramming for non-monotonic reasoning. Examples of modular programming, hierarchical reasoning, constraints, and rules with exceptions will be illustrated. the semantics of programs and program compositions is defined in terms of three-valued logic [15]. the computational interpretation of program compositions is formalised by an equivalence preserving syntactic transformation of arbitrary program compositions into standard general programs.
Associative computation is characterized by the in-tertwining of search by content and data parallel com-putation. this intertwining facilitates the integration of knowledge retrieval and data parallel computation. th...
详细信息
We extend probabilistic action language pBC+ withthe notion of utility in decision theory. the semantics of the extended pBC+ can be defined as a shorthand notation for a decision-theoretic extension of the probabili...
详细信息
ISBN:
(纸本)9783030205287;9783030205270
We extend probabilistic action language pBC+ withthe notion of utility in decision theory. the semantics of the extended pBC+ can be defined as a shorthand notation for a decision-theoretic extension of the probabilistic answer set programming language LPMLN. Alternatively, the semantics of pBC+ can also be defined in terms of Markov Decision Process (MDP), which in turn allows for representing MDP in a succinct and elaboration tolerant way as well as leveraging an MDP solver to compute a pBC+ action description. the idea led to the design of the system PBCPLUS2MDP, which can find an optimal policy of a pBC+ action description using an MDP solver.
暂无评论