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.
the hybrid logic H(@) is obtained by adding nominals and the satisfaction operator @ to the basic modal logic. the resulting logic gains expressive power without increasing the complexity of the satisfiability problem...
详细信息
ISBN:
(纸本)3540252363
the hybrid logic H(@) is obtained by adding nominals and the satisfaction operator @ to the basic modal logic. the resulting logic gains expressive power without increasing the complexity of the satisfiability problem, which remains within PSpace. A resolution calculus for H(@) was introduced in [5], but it did not provide strategies for ordered resolution and selection functions. Additionally, the problem of termination was left open. In this paper we address both issues. We first define proper notions of admissible orderings and selection functions and prove the refutational completeness of the obtained ordered resolution calculus using a standard "candidate model" construction [10]. Next, we refine some of the nominal-handling rules and show that the resulting calculus is sound, complete and can only generate a finite number of clauses, establishing termination. Finally, the theoretical results were tested empirically by implementing the new strategies into HyLoRes [6,18], an experimental prototype for the original calculus described in [5]. Both versions of the prover were compared and we discuss some preliminary results.
logical Bayesian Networks (LBNs) have recently been introduced as another language for knowledge based model construction of Bayesian networks, besides existing languages such as Probabilistic Relational Models (PRMs)...
详细信息
ISBN:
(纸本)3540281770
logical Bayesian Networks (LBNs) have recently been introduced as another language for knowledge based model construction of Bayesian networks, besides existing languages such as Probabilistic Relational Models (PRMs) and Bayesian logic Programs (BLPs). the original description of LBNs introduces them as a variant of BLPs and discusses the differences with BLPs but still leaves room for a deeper discussion of the relationship between LBNs and BLPs. Also the relationship to PRMs was not treated in much detail. In this paper, we first give a more compact and clear definition of LBNs. Next, we describe in more detail how PRMs and BLPs relate to LBNs. Like this we not only see what the advantages and disadvantages of LBNs are with respect to PRMs and BLPs, we also gain more insight into the relationships between PRMs and BLPs.
We present a program logic for verifying the heap consumption of low-level programs. the proof rules employ a uniform assertion format and have been derived from a general purpose program logic [1]. In a proof-carryin...
详细信息
ISBN:
(纸本)3540252363
We present a program logic for verifying the heap consumption of low-level programs. the proof rules employ a uniform assertion format and have been derived from a general purpose program logic [1]. In a proof-carrying code scenario, the inference of invariants is delegated to the code provider, who employs a certifying compiler that generates a certificate from program annotations and analysis. the granularity of the proof rules matches that of the linear type system presented in [6], which enables us to perform verification by replaying typing derivations in a theorem prover, given the specifications of individual methods. the resulting verification conditions are of limited complexity, and are automatically discharged. We also outline a proof system that relaxes the linearity restrictions and relates to the type system of usage aspects presented in [2].
there is a trend to study extended variants of propositional logic which have explicit means to represent cardinality constraints. that is accomplished using so-called c-atoms. We show that c-atoms can be efficiently ...
详细信息
ISBN:
(纸本)3540252363
there is a trend to study extended variants of propositional logic which have explicit means to represent cardinality constraints. that is accomplished using so-called c-atoms. We show that c-atoms can be efficiently reduced to a general form of Exact Satisfiability. the general X(i)SAT problem is to find an assignment for a CNF such that exactly i literals are true in each clause for any i >= 1. We show that this problem is solvable in time O(1.4143(n)) (where n is the number of variables) regardless of i if we allow exponential space. For polynomial space, we present an algorithm solving X(i)SAT for all i strictly better than the trivial O(2(n)) bound. For i = 2, i = 3 and i = 4 we obtain upper time bounds in O(1.5157(n)), O(1.6202(n)) and O(1.6844(n)), respectively. We also present a dedicated X(2)SAT algorithm running in polynomial space and time O(1.4511(n)).
this paper deals with mining the logical layer of the Semantic Web. Our approach adopts the hybrid system AL-log as a knowledge representation and reasoning framework and Inductive logicprogramming as a methodologica...
详细信息
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.
Resolution-based calculi are among the most widely used calculi for theorem proving in first-order logic. Numerous refinements of resolution are nowadays available, such as e.g. basic superposition, a calculus highly ...
详细信息
ISBN:
(纸本)3540252363
Resolution-based calculi are among the most widely used calculi for theorem proving in first-order logic. Numerous refinements of resolution are nowadays available, such as e.g. basic superposition, a calculus highly optimized for theorem proving with equality. However, even such an advanced calculus does not restrict inferences enough to obtain decision procedures for complex logics, such as SHIQ. In this paper, we present a new decomposition inference rule, which can be combined with any resolution-based calculus compatible withthe standard notion of redundancy. We combine decomposition with basic superposition to obtain three new decision procedures: (i) for the description logic SHIQ, (ii) for the description logic ALCHIQb, and (iii) for answering conjunctive queries over SHIQ knowledge bases. the first two procedures are worst-case optimal and, based on the vast experience in building efficient theorem provers, we expect them to be suitable for practical usage.
the proceedings contain 19 pages. the topics discussed include: declaratively querying and visualizing knowledge bases in XML;incremental learning of transfer rules for customized machine translation;an evaluation of ...
详细信息
ISBN:
(纸本)3540255605
the proceedings contain 19 pages. the topics discussed include: declaratively querying and visualizing knowledge bases in XML;incremental learning of transfer rules for customized machine translation;an evaluation of a rule based language for classification queries;mining semantic structures in movies;solving alternating boolean equation systems in answer set programming;effective modeling with constraints;a local search system for solving constraint problems of declarative graph based global constraints;realizing the alternative resources constraint;distributed constraint-based railway simulation;concurrent engineering to wisdom engineering;and a pragmatic approach to pre-testing Prolog programs.
Multidimensional dynamic logic programs are a paradigm which allows to express (partially) hierarchically ordered evolving knowledge bases through (partially) ordered multi sets of logic programs and allowing to solve...
详细信息
ISBN:
(纸本)3540285385
Multidimensional dynamic logic programs are a paradigm which allows to express (partially) hierarchically ordered evolving knowledge bases through (partially) ordered multi sets of logic programs and allowing to solve contradictions among rules in different programs by allowing rules in more important programs to reject rules in less important ones. this class of programs extends the class of dynamic logic program that provides meaning and semantics to sequences of logic programs. Recently a semantics named refined stable model semantics has fixed some counterintuitive behaviour of previously existing semantics for dynamic logic programs. However, it is not possible to directly extend the definitions and concepts of the refined semantics to the multidimensional case and hence more sophisticated principles and techniques are in order. In this paper we face the problem of defining a proper semantics for multidimensional dynamic logic programs by extending the idea of well supported model to this class of programs and by showing that this concept alone is enough for univocally characterizing a proper semantics. We then show how the newly defined semantics coincides withthe refined one when applied to sequences of programs.
暂无评论