there are many different notions of "rule" in the literature. A key feature and main intuition of any such notion is that rules can be "applied" to derive conclusions from certain premises. More fo...
详细信息
ISBN:
(纸本)9783642405648
there are many different notions of "rule" in the literature. A key feature and main intuition of any such notion is that rules can be "applied" to derive conclusions from certain premises. More formally, a rule is viewed as a function that, when invoked on a set of known facts, can produce new facts. In this paper, we show that this extreme simplification is still sufficient to obtain a number of useful results in concrete cases. We define abstract rules as a certain kind of functions, provide them with a semantics in terms of (abstract) stable models, and explain how concrete normal logicprogramming rules can be viewed as abstract rules in a variety of ways. We further analyse dependencies between abstract rules to recognise classes of logic programs for which stable models are guaranteed to be unique.
We introduce a general approach to cryptographic protocol verification based oil answer set programming. In our approach, cryptographic protocols are represented as extended logic programs where the answer Sets corres...
详细信息
ISBN:
(纸本)9783642042379
We introduce a general approach to cryptographic protocol verification based oil answer set programming. In our approach, cryptographic protocols are represented as extended logic programs where the answer Sets correspond to traces of protocol runs. Using queries, we can find attacks on a protocol by finding the answer sets for the corresponding logic program. Our encoding is modular, with different modules representing the message passing environment, the protocol Structure and the intruder model. We can easily tailor each module to suit a specific application, while keeping the rest of the encoding constant. As such. our approach is more flexible and elaboration tolerant than related formalizations. the present system is intended as a first step towards the development of a compiler from protocol specifications to executable programs: such a compiler would make verification a completely automated process. this work is also part of a larger project in which we are exploring the advantages of explicit, declarative representations of protocol verification problems.
We present a procedure for deciding (database) query containment under constraints. the technique is to extend the logic DLR with an ABox, and to transform query subsumption problems into DLR ABox satisfiability probl...
详细信息
ISBN:
(纸本)3540412859
We present a procedure for deciding (database) query containment under constraints. the technique is to extend the logic DLR with an ABox, and to transform query subsumption problems into DLR ABox satisfiability problems. Such problems can then be decided, via a reification transformation, using a highly optimised reasoner for the SHIQ description logic. We use a simple example to support our hypothesis that this procedure will work well with realistic problems.
We introduce choice logic programs as negation-free datalog programs that allow rules to have exclusive-only (possibly empty) disjunctions in the head. Such programs naturally model decision problems where, depending ...
详细信息
ISBN:
(纸本)3540667490
We introduce choice logic programs as negation-free datalog programs that allow rules to have exclusive-only (possibly empty) disjunctions in the head. Such programs naturally model decision problems where, depending on a context, agents must make a decision, i.e. an exclusive choice out of several alternatives. It is shown that such a choice mechanism is in a sense equivalent with negation as supported in semi-negative ("normal") datalog programs. We also discuss an application where strategic games can be naturally formulated as choice programs: it turns out that the stable models of such programs capture exactly the set of Nash equilibria. We then consider the effect of choice on "negative information" that may be implicitly derived from a program. Based on an intuitive notion of unfounded set for choice programs. ive show that several results from (seminegative) disjunctive programs can be strengthened;characterizing the position of choice programs as an intermediate between simple positive programs and programs that allow for the explicit use of negation in the body of a rule.
Global Abduction (GA) is a recently proposed logical formalism for agent oriented programming which allows an agent to collect information about the world and update this in a nonmonotonic: way when changes in the wor...
详细信息
ISBN:
(纸本)9783540696186
Global Abduction (GA) is a recently proposed logical formalism for agent oriented programming which allows an agent to collect information about the world and update this in a nonmonotonic: way when changes in the world are observed. A distinct feature of Global Abduction is that in case the agent needs to give up one plan, it may start a new one, or continue a suspended plan, while its beliefs learned about the world in the failed attempts persist. this paper describes an implementation of GA in the high-level language of Constraint Handling Rules (CHR). It appears to be a first attempt to a full implementation of GA, which also confirms CHR as a powerful meta-programming language for advanced reasoning. the construction gives rise a discussion of important issues of the semantics and pragmatics of Global Abduction, leading to proposals for a specific procedural semantics and architecture that seem well suited for real-time applications.
Recently, Boolean Satisfiability (SAT) solving has been proposed to tackle the increasing complexity in high-level system design. Working well for system specifications with a limited amount of routing options, they t...
详细信息
ISBN:
(纸本)9783642405648
Recently, Boolean Satisfiability (SAT) solving has been proposed to tackle the increasing complexity in high-level system design. Working well for system specifications with a limited amount of routing options, they tend to fail for densely connected computing platforms. this paper proposes an automated system design approach employing Answer Set programming (ASP). ASP provides a stringent semantics, allowing for an efficient representation of routing options. An automotive case-study illustrates that the proposed ASP-based system design approach is competitive for sparsely connected computing platforms, while it outperforms SAT-based approaches for dense Networks-on-Chip by an order of magnitude.
this paper proposes a new knowledge representation language, called QDLP, which extends DLP to deal with uncertain values. A certainty degree interval (a subinterval of [0, 1]) is assigned to each (quantitative) rule....
详细信息
ISBN:
(纸本)3540667490
this paper proposes a new knowledge representation language, called QDLP, which extends DLP to deal with uncertain values. A certainty degree interval (a subinterval of [0, 1]) is assigned to each (quantitative) rule. Triangular norms (T-norms) are employed to define calculi for propagating uncertainty information from the premises to the conclusion of a quantitative rule. Negation is considered and the concept of stable model is extended to QDLP. Different T-norms induce different semantics for one given quantitative program. In this sense, QDLP is parameterized and each choice of a T-norm induces a different QDLP language. Each T-norm is eligible for events with determinate relationships (e.g., independence, exclusiveness) between them. Since there are infinitely many T-norms, it turns out that there is a family of infinitely many QDLP languages. this family is carefully studied and the set of QDLP languages which generalize traditional DLP is precisely singled out. Finally the complexity of the main decisional problems arising in the context of QDLP (i.e., Model Checking, Stable Model Checking, Consistency, and Brave reasoning) is analyzed. It is shown that the complexity of the relevant fragments of QDLP coincides exactly withthe complexity of DLP. that is, reasoning with uncertain values is more general and not harder than reasoning with boolean values.
Answer Set programming is a new paradigm based on logicprogramming. the main component of answer set programming is a system that finds the answer sets of logic programs. During the computation of an answer set, syst...
详细信息
Aggregates in answer set programming (ASP) have recently been studied quite intensively. the main focus of previous work has been on defining suitable semantics for programs with arbitrary, potentially recursive aggre...
详细信息
ISBN:
(纸本)3540285385
Aggregates in answer set programming (ASP) have recently been studied quite intensively. the main focus of previous work has been on defining suitable semantics for programs with arbitrary, potentially recursive aggregates. By now, these efforts appear to have converged. On another line of research, the relation between unfounded sets and (aggregate-free) answer sets has lately been rediscovered. It turned out that most of the currently available answer set solvers rely on this or closely related results (e.g., loop formulas). In this paper, we unite these lines and give a new definition of unfounded sets for disjunctive logic programs with arbitrary, possibly recursive aggregates. While being syntactically somewhat different, we can show that this definition properly generalizes all main notions of unfounded sets that have previously been defined for fragments of the language. We demonstrate that, as for restricted languages, answer sets can be crisply characterized by unfounded sets: they are precisely the unfounded-free models. this result can be seen as a confirmation of the robustness of the definition of answer sets for arbitrary aggregates. We also provide a comprehensive complexity analysis for unfounded sets, and study its impact on answer set computation.
Forgetting is an operation that allows the removal, from a knowledge base, of middle variables no longer deemed relevant, while preserving all relationships (direct and indirect) between the remaining variables. When ...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
Forgetting is an operation that allows the removal, from a knowledge base, of middle variables no longer deemed relevant, while preserving all relationships (direct and indirect) between the remaining variables. When investigated in the context of Answer-Set programming, many different approaches to forgetting have been proposed, following different intuitions, and obeying different sets of properties. this talk will present a bird's-eye view of the complex landscape composed of the properties and operators of forgetting defined over the years in the context of Answer-Set programming, zooming in on recent findings triggered by the formulation of the so-called strong persistence, a property based on the strong equivalence between an answer-set program and the result of forgetting modulo the forgotten atoms, which seems to best encode the requirements of the forgetting operation.
暂无评论