Many NP-complete problems can be encoded in the answer set semantics of logic programs in a very concise way, where the encoding reflects the typical "guess and check" nature of NP problems: the property is ...
详细信息
ISBN:
(纸本)354020721X
Many NP-complete problems can be encoded in the answer set semantics of logic programs in a very concise way, where the encoding reflects the typical "guess and check" nature of NP problems: the property is encoded in a way such that polynomial size certificates for it correspond to stable models of a program. However, the problem-solving capacity of full disjunctive logic programs (DLPs) is beyond NP at the second level of the polynomial hierarchy. While problems there also have a "guess and check" structure, an encoding in a DLP is often non-obvious, in particular if the "check" itself is co-NP-complete;usually, such problems are solved by interleaving separate "guess" and "check" programs, where the check is expressed by inconsistency of the check program. We present general transformations of head-cycle free (extended) logic programs into stratified disjunctive logic programs which enable one to integrate such "guess" and "check" programs automatically into a single disjunctive logic program. Our results complement recent results on meta-interpretation in ASP, and extend methods and techniques for a declarative "guess and check" problem solving paradigm through ASP.
We develop the system software for high-performance clusters and build such clusters using our original methodology. Design study is performed on basis of the analytical models of the cluster (a modification of the we...
详细信息
ISBN:
(纸本)076952138X
We develop the system software for high-performance clusters and build such clusters using our original methodology. Design study is performed on basis of the analytical models of the cluster (a modification of the well-known LogGP model) and test benchmark being used. In present paper different communication environments being used in high performance clusters are compared the notion of cluster's efficiency is defined as the ratio between peak and actual performances of the cluster. the results of comparative analysis of the efficiency of clusters using Myrinet, Fast Ethernet and Gigabit Ethernet, as well as the results of comparative analysis of the efficiency of clusters forming Top,100 and Myrinet-clusters built in the Institute are discussed. Presently we have built several clusters including 64 dual Xeon 3.06 GHz Myrinet-cluster for National Academy of Sciences of the Republic of Armenia. Oscar package is used as the control system, some original software being added.
Disjunctive Logic programming (DLP) under the answer set semantics is an advanced formalism for knowledge representation and reasoning. It is generally considered more expressive than normal (disjunction-free) Logic P...
详细信息
ISBN:
(纸本)354020721X
Disjunctive Logic programming (DLP) under the answer set semantics is an advanced formalism for knowledge representation and reasoning. It is generally considered more expressive than normal (disjunction-free) Logic programming, whose expressiveness is limited to properties decidable in NP. However, this higher expressiveness comes at a computational cost, and while there are several efficient systems for the normal case, we are only aware of few solid implementations for full DLP. In this paper we investigate novel techniques to couple two main modules (a model generator and a model checker) commonly found in DLP systems more tightly. Instead of using the checker only as a boolean oracle, in our approach, upon a failed check it also returns a so-called unfounded set. Intuitively, this set explains why a model candidate is not an answer set, and the generator employs this knowledge to backtrack until that set is no longer unfounded, which is vastly more efficient than employing full-fledged model checks to control backtracking. Furthermore, we invoke the checker not only for actual model candidates, but also on partial models during model generation to possibly prune the search space. We implemented these approaches in DLV, a state-of-the-art implementation of DLP according to recent comparisons, and carried out experiments;tests on hard benchmark instances show a significant speedup of a factor of two and above.
An enhanced 0-1 mixed-integer linear programming formulation based on the cell-transmission model is proposed for the traffic signal optimization problem. this formulation has several features that are currently unava...
详细信息
An enhanced 0-1 mixed-integer linear programming formulation based on the cell-transmission model is proposed for the traffic signal optimization problem. this formulation has several features that are currently unavailable in other existing models developed with a similar approach, including the components for handling the number of stops, fixed or dynamic cycle length and splits, and lost time. the problem of unintended vehicle holding, which is common in analytical models, is explicitly treated. the formulation can be utilized in developing strategies for adaptive traffic-control systems. It can also be used as a benchmark for examining the convergence behavior of heuristic algorithms based on the genetic algorithm, fuzzy logic, neural networks, or other approaches that are commonly used in this field. the discussion of extending the proposed model to capture traffic signal preemption in the presence of emergency vehicles is given. In terms of computational efficiency, the proposed formulation has the least number of binary integers as compared with other existing formulations that were developed withthe same approach.
Research on cognitive theories about programming learning suggests that experienced programmers solve problems by looking for previous solutions that are related to the new problem and that can be adapted to the curre...
详细信息
Over recent years, various semantics have been proposed for dealing with updates in the setting of logic programs. the availability of different semantics naturally raises the question of which are most adequate to mo...
详细信息
the talk provides an overview and demonstration of an Extended Static Checker for the Java programming language, a program checker that finds errors statically but has a much more accurate semantic model than existing...
详细信息
We investigate a generalization of weight-constraint programs with stable semantics, as implemented in the ASP solver smodels. Our programs admit atoms of the form 〈X, F〉 where X is a finite set of propositional atoms...
详细信息
We show how to generate well-founded and stable term orderings based on polynomial interpretations over the real numbers. Monotonicity (another usual requirement in termination proofs) can, then, be gradually introduc...
详细信息
ISBN:
(纸本)3540212981
We show how to generate well-founded and stable term orderings based on polynomial interpretations over the real numbers. Monotonicity (another usual requirement in termination proofs) can, then, be gradually introduced in the interpretations to deal with different applications. For instance, the dependency pairs method for proving termination of rewriting, and some restrictions of the rewrite relation which are not monotonic in all arguments of the function symbols, can benefit from this approach. the latter is the case for context-sensitive rewriting (CSR), a simple restriction of rewriting which has been proved useful for describing the semantics of several programming languages (e.g., Maude) and analyzing the properties of the corresponding programs. We show how to automatically generate polynomial interpretations over the real numbers for proving termination of CSR.
the proceedings contain 17 papers. the topics discussed include: addressing the trust asymmetry problem in grid computing with encrypted computation;general parallel computations on desktop grid and P2P systems;effici...
the proceedings contain 17 papers. the topics discussed include: addressing the trust asymmetry problem in grid computing with encrypted computation;general parallel computations on desktop grid and P2P systems;efficient data driven runtime code generation;IMPuLSE: integrated monitoring and profiling for large-scale environments;memory access analysis and optimization approaches on splay trees;comparing Ethernet and Myrinet for MPI communication;an orchestration language for parallel objects;design tradeoffs in modern software transactional memory systems;the hierarchically tiled arrays programming approach;combined compile-time and runtime-driven, pro-active data movement in software DSM systems;overcoming barriers to restructuring in a modular visualisation environment;compiler-generated staggered check-pointing;dynamic topology adaptation of virtual networks of virtual machines;looking at the server side of peer-to-peer systems;and replicating memory behavior for performance prediction.
暂无评论