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).
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.
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.
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.
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.
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.
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.
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.
In answer-set programming (ASP), the main focus usually is on computing answer sets which correspond to solutions to the problem represented by a logic program. Simple reasoning over answer sets is sometimes supported...
详细信息
ISBN:
(纸本)9783642042379
In answer-set programming (ASP), the main focus usually is on computing answer sets which correspond to solutions to the problem represented by a logic program. Simple reasoning over answer sets is sometimes supported by ASP systems (usually in the form of computing brave or cautious consequences), but Slightly more involved reasoning problems require external postprocessing. Generally speaking, it is often desirable to use (a subset of) brave or cautious consequences of a program P-1 as input to another program P-2 in order to provide the desired Solutions to the problem to be solved. In practice, the evaluation of the program P-1 Currently has to be decopuled from the evaluation of P-2 using an intermediate step which collects the desired consequences of P-1 and provides them as input to P-2. In this work, we present a novel method for representing such a procedure within a single program, and thus within the realm of ASP itself. Our technique relies oil rewriting P-1 into a so-called manifold program. which allows for accessing all desired consequences of P-1 within a single answer set. then, this manifold program can be evaluated jointly with P-2 avoiding any intermediate computation step. For determining the consequences within the manifold program we use weak constraints, which is strongly motivated by complexity considerations. As an application, we present all encoding for computing the ideal extension of,in abstract argumentation framework.
the support for function symbols in logicprogramming under answer set semantics allows to overcome some modeling limitations of traditional Answer Set programming (ASP) systems, Such as the inability of handling infi...
详细信息
ISBN:
(纸本)9783642042379
the support for function symbols in logicprogramming under answer set semantics allows to overcome some modeling limitations of traditional Answer Set programming (ASP) systems, Such as the inability of handling infinite domains. On the other hand, admitting function symbols in ASP makes inference undecidable in the general case. Lately. the research community is focusing on finding proper subclasses for which decidability of inference is guaranteed. the two major proposals, so far, are finitary programs and finitely-ground programs. these two proposals are somehow complementary: indeed, the former is conceived to allow decidable querying (by means of a top-down evaluation strategy), while file latter supports the computability of answer-sets (by means of a bottom-up evaluation strategy). One of the main advantages of finitely-ground programs is that they can be "directly" evaluated by Current ASP systems, which are based on a bottom-up computational model. However, there are also some interesting programs which are suitable for top-down query evaluation;but do not fall in the class of finitely-ground programs. In this paper, we focus on disjunctive finitely-recursive Positive (DFRP) programs. We present a proper adaptation of the magic-sets technique for DFRP programs, which ensures query equivalence under both brave and cautious reasoning. We show that, if the input program is DFRP, then its magic-set rewriting is guaranteed to be finitely ground. thus, reasoning oil DFRP programs turns Out to be decidable, and we provide an effective method for its computation on the ASP system DLV.
暂无评论