We show how to combine the two most powerful approaches for automated termination analysis of logicprograms (LPs): the direct approach which operates directly on LPs and the transformational approach which transforms...
详细信息
ISBN:
(纸本)9783642125911
We show how to combine the two most powerful approaches for automated termination analysis of logicprograms (LPs): the direct approach which operates directly on LPs and the transformational approach which transforms LPs to term rewrite systems (TRSs) and tries to prove termination of the resulting TRSs. To this end, we adapt the well-known dependency pair framework from TRSs to LPs. Withthe resulting method;one can combine arbitrary termination techniques for LPs in a completely modular way and one call use both direct and transformational techniques for different parts of the same LP.
Type information has many applications;it can e.g. be used in optimized compilation, termination analysis and error detection. However, logicprograms are typically untyped. A well-typed program has the property that ...
详细信息
ISBN:
(纸本)9783642005145
Type information has many applications;it can e.g. be used in optimized compilation, termination analysis and error detection. However, logicprograms are typically untyped. A well-typed program has the property that it behaves identically on well-typed goals with or without type checking. Hence the automatic inference of a well-typing is worthwhile. Existing inferences are either cheap and inaccurate, or accurate and expensive. By giving up the requirement that all calls to a predicate have types that are instances of a unique polymorphic type but instead allowing multiple polymorphic typings for the same predicate, we obtain a novel strongly-connected-component-based analysis that provides a good compromise between accuracy and computational cost.
We present a type theory characterizing the mobility and locality of program terms in a distributed computation. the type theory of our calculus is derived from logical notions of necessity (square A) and possibility ...
详细信息
ISBN:
(纸本)3540266550
We present a type theory characterizing the mobility and locality of program terms in a distributed computation. the type theory of our calculus is derived from logical notions of necessity (square A) and possibility (lozenge A) of the modal logic S4 via a Curry-Howard style isomorphism. logical worlds are interpreted as sites for computation, accessibility corresponds to dependency between processes at those sites. Necessity (square A) describes terms of type A which have a structural kind of mobility or location-independence. Possibility (lozenge A) describes terms of type A located somewhere, perhaps at a remote site. the modalities square and lozenge are defined in a clean, orthogonal manner, leading to a simple account of mobility and higher-order functions. For illustration, we assume an execution environment with each location distinguished by a mutable store. Here modal types ensure that store addresses never escape from the location where they are defined, eliminating a source of runtime errors. We speculate as to other advantages or trade-offs of this disciplined style of distributed programming.
We describe a parameterized framework with which users can take advantage of unification over analysis variables to implement efficient or precise analyses, or even both. To be illustrative we instantiate the framewor...
详细信息
ISBN:
(纸本)9783540787686
We describe a parameterized framework with which users can take advantage of unification over analysis variables to implement efficient or precise analyses, or even both. To be illustrative we instantiate the framework with reaching definition analysis and conduct a systematic evaluation of performance and precision of the analysis. We compare our result withthat of a state-of-the-art solver, the Succinct Solver and show our solver is at least 10-times faster than the Succinct Solver. On some benchmarks linearity is reached by the use of unification. Although the result of unification is often imprecise, a heuristic study is conducted to detect where the loss of precision may happen. We apply the heuristics on benchmarks and achieve not only efficient but also precise analysis.
the increasing availability of smart objects demands for flexible mechanisms to orchestrate different types of these objects to smart environments. As smart objects are typically not aware of each other, an orchestrat...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
the increasing availability of smart objects demands for flexible mechanisms to orchestrate different types of these objects to smart environments. As smart objects are typically not aware of each other, an orchestrating platform has to manage common resources, to harmonize the individual behavior of the acting objects, and to combine their activities to an intelligent team work. this paper presents a corresponding framework to implement such an orchestrating platform. It provides a concurrent programming language representing states in Description logics and state transitions as logical updates enabling deductive support to infer non-explicitly represented knowledge. It uses temporal logic to suspend execution of a process for a particular evolution of the global state that is specified by a LTL formula. Since a process can fork into subprocesses this provides a mechanism for runtime verification by splitting a process into a subprocess executing some critical program and another parallel subprocess monitoring the first one by waiting for the desired evolution of states specified in its LTL formula.
Bounded Model Checking is one the most successful techniques for finding bugs in program. However, model checkers are resource hungry and are often unable to verify programs with loops iterating over large arrays. We ...
详细信息
ISBN:
(纸本)9783319631394;9783319631387
Bounded Model Checking is one the most successful techniques for finding bugs in program. However, model checkers are resource hungry and are often unable to verify programs with loops iterating over large arrays. We present a transformationthat enables bounded model checkers to verify a certain class of array properties. Our technique transforms an array-manipulating (Ansi-C) program to an array-free and loop-free (Ansi-C) programthereby reducing the resource requirements of a model checker significantly. Model checking of the transformed program using an off-the-shelf bounded model checker simulates the loop iterations efficiently. thus, our transformed program is a sound abstraction of the original program and is also precise in a large number of cases-we formally characterize the class of programs for which it is guaranteed to be precise. We demonstrate the applicability and usefulness of our technique on both industry code as well as academic benchmarks.
Algorithmic debugging is a semi-automatic debugging technique that is present in practically all mature programming languages. In this paper we claim that the state of the practice in algorithmic debugging is a step f...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
Algorithmic debugging is a semi-automatic debugging technique that is present in practically all mature programming languages. In this paper we claim that the state of the practice in algorithmic debugging is a step forward compared to the state of the theory. In particular, we argue that novel techniques for algorithmic debugging cannot be supported by the standard internal data structures used in this technique, and a generalization of the standard definitions and algorithms is needed. We identify two specific problems of the standard formulation and implementations of algorithmic debugging, and we propose a reformulation to solve both problems. the reformulation has been done in a paradigm-independent manner to make it useful and reusable in different programming languages.
We provide an approach to formally analyze the computational behavior of coroutines in logicprograms and to compile these computations into new programs, not requiring any support for coroutines. the problem was alre...
详细信息
ISBN:
(纸本)9783319178226;9783319178219
We provide an approach to formally analyze the computational behavior of coroutines in logicprograms and to compile these computations into new programs, not requiring any support for coroutines. the problem was already studied near to 30 years ago, in an analysis and transformation technique called Compiling Control. However, this technique had a strong ad hoc flavor: the completeness of the analysis was not well understood and its symbolic evaluation was also very ad hoc. We show how Abstract Conjunctive Partial Deduction, introduced by Leuschel in 2004, provides an appropriate setting to redefine Compiling Control. Leuschel's framework is more general than the original formulation, it is provably correct, and it can easily be applied for simple examples. We also show that the Abstract Conjunctive Partial Deduction framework needs some further extension to be able to deal with more complex examples.
the well-founded semantics of normal logicprograms has two main utilities, one being an efficiently computable semantics with a unique intended model, and the other serving as polynomial time constraint propagation f...
详细信息
ISBN:
(纸本)9783319178226;9783319178219
the well-founded semantics of normal logicprograms has two main utilities, one being an efficiently computable semantics with a unique intended model, and the other serving as polynomial time constraint propagation for the computation of answer sets of the same program. When logicprograms are generalized to support constraints of various kinds, the semantics is no longer tractable, which makes the second utility doubtful. this paper considers the possibility of tractable but incomplete methods, which in general may miss information in the computed result, but never generates wrong conclusions. For this goal, we first formulate a well-founded semantics for logicprograms with generalized atoms, which generalizes logicprograms with arbitrary aggregates/constraints/dl-atoms. As a case study, we show that the method of removing non-monotone dl-atoms for the well-founded semantics by Eiter et al. actually falls into this category. We also present a case study for logicprograms with standard aggregates.
Most algorithms for the synthesis of reactive systems focus on the construction of finite-state machines rather than actual programs. this often leads to badly structured, unreadable code. In this paper, we present a ...
详细信息
ISBN:
(纸本)9783030010904;9783030010898
Most algorithms for the synthesis of reactive systems focus on the construction of finite-state machines rather than actual programs. this often leads to badly structured, unreadable code. In this paper, we present a bounded synthesis approach that automatically constructs, from a given specification in linear-time temporal logic (LTL), a program in Madhusudan's simple imperative language for reactive programs. We develop and compare two principal approaches for the reduction of the synthesis problem to a Boolean constraint satisfaction problem. the first reduction is based on a generalization of bounded synthesis to two-way alternating automata, the second reduction is based on a direct encoding of the program syntax in the constraint system. We report on preliminary experience with a prototype implementation, which indicates that the direct encoding outperforms the automata approach.
暂无评论