We show that the concepts of strong and uniform equivalence of logic programs can be generalized to an abstract algebraic setting of operators on complete lattices. Our results imply characterizations of strong and un...
详细信息
Propositional satisfiability (SAT) solvers provide a promising computational platform for logic programs under the stable model semantics. However. computing stable models of a logic program using a SAT solver presume...
详细信息
ISBN:
(纸本)9783642042379
Propositional satisfiability (SAT) solvers provide a promising computational platform for logic programs under the stable model semantics. However. computing stable models of a logic program using a SAT solver presumes translating the program into a set of clauses which is the input form accepted by most SAT solvers. this leads to fairly complex super-linear translations. there are, however, interesting extensions to plain clausal propositional representations Such as difference logic. A number of solvers have been developed for difference logic, in particular in the context of the satisfiability modulo theories (SMT) framework. and the goal of the paper is to study whether Such engines could be harnessed to the computation of stable models for logic programs in an effective way. To this end, we provide succinct translations front logic programs to theories of difference logic and evaluate the potential of SMT solvers in the computation of stable models using, these translations and a selection of benchmarks.
the logic FO(ID) uses ideas from the field of logicprogramming to extend first order logic with non-monotone inductive definitions. the goal of this paper is to extend Gentzen's sequeut calculus to obtain a deduc...
详细信息
ISBN:
(纸本)9783642042379
the logic FO(ID) uses ideas from the field of logicprogramming to extend first order logic with non-monotone inductive definitions. the goal of this paper is to extend Gentzen's sequeut calculus to obtain a deductive inference method for FO(ID). the main difficulty in building Such a proof system is the representation and inference of unfounded sets. It turns out that we can represent unfounded sets by least fixpoint expressions borrowed from stratified least fixpoint logic (SLFP), which is a logic with a least fixpoint operator and characterizes the expressibility of stratified logic programs. therefore, in this paper, we integrate least fixpoint expressions into FO(ID) and define the logic FO(ID,SLFP). We investigate a sequeut calculus for FO(ID,SLFP), which extends the sequent calculus for SLFP with inference rules for the inductive definitions of FO(ID). We show that this proof system is sound with respect to a slightly restricted fragment of FO(ID) and complete for a more restricted fragment of FO(ID).
We present a new general purpose query and abduction language for reasoning about action domains that allows the processing of simultaneous actions, definition of conditions and reasoning about fluents and actions. AQ...
详细信息
We consider the problem of whether a given preferred answer set program can be reduced to a propositional formula. Research on this topic is of boththeoretical and practical interests: on one hand, it will shed new i...
详细信息
ISBN:
(纸本)9783642042379
We consider the problem of whether a given preferred answer set program can be reduced to a propositional formula. Research on this topic is of boththeoretical and practical interests: on one hand, it will shed new insights to understand the expressive power of preferred answer set programs on the other hand, it may also lead to efficient implementations for computing preferred answer sets of logic programs. In this paper, we focus on Brewka and Eiter's preferred answer set programs. We propose a translation from preferred answer set programs to propositional logic and show that there is one-to-one correspondence between the preferred answer sets of the program to the models of the resulting propositional theory. We then link this result to Brewka and Eiter's weakly preferred answer set semantics.
Epistemic logic programs constitute an extension of the stable models semantics to deal with new constructs called subjective literals. Informally speaking, a subjective literal allows checking whether some regular li...
详细信息
ISBN:
(纸本)9783030205287;9783030205270
Epistemic logic programs constitute an extension of the stable models semantics to deal with new constructs called subjective literals. Informally speaking, a subjective literal allows checking whether some regular literal is true in all or some stable models. As it can be imagined, the associated semantics has proved to be non-trivial, as the truth of subjective literals may interfere withthe set of stable models it is supposed to query. As a consequence, no clear agreement has been reached and different semantic proposals have been made in the literature. Unfortunately, comparison among these proposals has been limited to a study of their effect on individual examples, rather than identifying general properties to be checked. In this paper, we propose an extension of the well-known splitting property for logic programs to the epistemic case. We formally define when an arbitrary semantics satisfies the epistemic splitting property and examine some of the consequences that can be derived from that, including its relation to conformant planning and to epistemic constraints. Interestingly, we prove (through counterexamples) that most of the existing proposals fail to fulfill the epistemic splitting property, except the original semantics proposed by Gelfond in 1991.
Configurable on chip multiprocessor systems combine advantages of task-level parallelism and the flexibility Of field-programmable devices to customize architectures for parallel programs, thereby alleviating technolo...
详细信息
ISBN:
(纸本)9783642042379
Configurable on chip multiprocessor systems combine advantages of task-level parallelism and the flexibility Of field-programmable devices to customize architectures for parallel programs, thereby alleviating technological limitations due to memory bandwidth and power Consumption. Given the huge size of the design Space Of Such Systems, it is important to automatically optimize design parameters in order to facilitate wide and disciplined explorations. Being a combinatorial problem. system design can be modeled and solved as Such, but the amount of parameters renders the problem difficult to Solve for large instances. However. its the synthesis problem usually exhibits structure, Answer Set programming (ASP), for which solvers utilizing techniques from the propositional satisfiability domain are available, can be effectively employed. this paper presents a design flow based on ASP that uses the solver clasp as back-end engine. Synthesis experiments demonstrate the effectiveness of the approach.
To ensure a close relation between the answer sets of a program and those of its ground version, some answer set solvers deal with variables by requiring a safety condition on program rules. If we go beyond the syntax...
详细信息
ISBN:
(纸本)9783642042379
To ensure a close relation between the answer sets of a program and those of its ground version, some answer set solvers deal with variables by requiring a safety condition on program rules. If we go beyond the syntax of disjunctive programs, for instance by allowing rules with nested expressions, or perhaps even arbitrary first-order formulas, new definitions of safety are required. In this paper we consider a new concept of safety for formulas in quantified equilibrium logic where answer sets can be defined for arbitrary first-order formulas. the new concept captures and generalises two recently proposed safety definitions: that of Lee, Lifschitz and Palla (2008) as well as that of Bria, Faber and Leone (2008). We Study the main metalogical properties of safe formulas.
Modular nonmonotoniclogic programs (MLPs) under the answer-set semantics have been recently introduced as an ASP formalism in which modules can receive context-dependent input from other modules, while allowing (mutu...
详细信息
ISBN:
(纸本)9783642042379
Modular nonmonotoniclogic programs (MLPs) under the answer-set semantics have been recently introduced as an ASP formalism in which modules can receive context-dependent input from other modules, while allowing (mutually) recursive module calls. this call be used for more Succinct and natural problem representation at the price of an exponential increase of evaluation time. In this paper, we aim at all efficient top-down evaluation of MLPs, considering only calls to relevant module instances. To this end, we generalize the well-known Splitting theorem to the MLP setting and present notions of call stratification, for which we determine sufficient conditions. Call-stratified MLPs allow to split module instantiations into two parts, one for computing input of module calls, and one for evaluating the calls themselves with subsequent computations. Based on these results, we develop a top-down evaluation procedure that expands only relevant module instantiations. Finally. we discuss syntactic conditions for its exploitation.
In answer-set programming (ASP), many notions of program equivalence have been introduced and formally analysed. A particular line of research in this direction aims at studying conditions under which certain syntacti...
详细信息
ISBN:
(纸本)9783642042379
In answer-set programming (ASP), many notions of program equivalence have been introduced and formally analysed. A particular line of research in this direction aims at studying conditions under which certain syntactic constructs can be eliminated from programs preserving some given equivalence relation. In this paper, we continue this endeavour introducing novel conditions under which disjunction and negation can be eliminated from answer-set programs under relativised strong equivalence with projection. this notion is a generalisation of the usual strong-equivalence relation, as introduced by Lifschitz. Pearce, and Valverde, by allowing parametrisable context and Output alphabets, which is an important feature in view of practical programming techniques like the use of local variables and modules. We provide model-theoretic conditions that hold for a disjunctive logic program P precisely when there is a program Q, equivalent to P under our considered notion, Such that Q is either positive, normal, or Horn, respectively. Moreover, we outline how such a Q, called a casting of P, can be obtained, and consider complexity issues.
暂无评论