Proofs by induction are often incompatible with functions in tail-recursive form as the accumulator changes in the course of unfolding the definitions. Context-moving and context-splitting (Giesl, 2000) for functional...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
Proofs by induction are often incompatible with functions in tail-recursive form as the accumulator changes in the course of unfolding the definitions. Context-moving and context-splitting (Giesl, 2000) for functional programs transform tail-recursive programs into non tail-recursive ones which are more suitable for proofs by induction and thus for verification. In this paper, we formulate context-moving and context-splitting transformations in the framework of term rewriting systems, and prove their correctness with respect to both eager evaluation semantics and initial algebra semantics under some conditions on the programs to be transformed. the conditions for the correctness with respect to initial algebra semantics can be checked by automated methods for inductive theorem proving developed in the field of term rewriting systems.
the Next Generation Air Traffic System (NGATS) is aiming to provide substantial computer support for the air traffic controller. Algorithms for the accurate prediction of aircraft movements are of central importance f...
详细信息
ISBN:
(纸本)9783642205507
the Next Generation Air Traffic System (NGATS) is aiming to provide substantial computer support for the air traffic controller. Algorithms for the accurate prediction of aircraft movements are of central importance for such software systems but trajectory prediction has to work reliably in the presence of unknown parameters and uncertainties. We are using the AutoBayes programsynthesis system to generate customized data analysis algorithms that process large sets of aircraft radar track data in order to estimate parameters and uncertainties. In this paper, we present, how the tasks of finding structure in track data, estimation of important parameters in climb trajectories, and detection of continuous descent approaches (CDA) can be supported by code generated from compact AUTOBAYES specifications. We present an overview of the AutoBayes architecture and describe, how its schema-based approach generates customized analysis algorithms, documented C/C++ code, and detailed mathematical derivations. Results of experiments with actual air traffic control data are discussed.
We present two new algorithms which perform automatic parallelization via source-to-source transformations. the objective is to exploit goal-level, unrestricted independent and-parallelism. the proposed algorithms use...
详细信息
ISBN:
(纸本)9783540787686
We present two new algorithms which perform automatic parallelization via source-to-source transformations. the objective is to exploit goal-level, unrestricted independent and-parallelism. the proposed algorithms use as targets new parallel execution primitives which are simpler and more flexible than the well-known &/2 parallel operator. this makes it possible to generate better parallel expressions by exposing more potential parallelism among the literals of a clause than is possible with &/2. the difference between the two algorithms stems from whether the order of the solutions obtained is preserved or not. We also report on a preliminary evaluation of an implementation of our approach. We compare the performance obtained to that of previous annotation algorithms and show that relevant improvements can be obtained.
Intuitionistic logicprogramming provides the notion of embedded implication in rule bodies, which can be used to reason about a current database modified by the antecedent. this can be applied to a system that transl...
详细信息
ISBN:
(纸本)9783319631394;9783319631387
Intuitionistic logicprogramming provides the notion of embedded implication in rule bodies, which can be used to reason about a current database modified by the antecedent. this can be applied to a system that translates SQL to Datalog to solve SQL WIth queries, for which relations are locally defined and can therefore be understood as locally added to the current database. In addition, assumptions in SQL queries as either adding or removing data can be modelled in this way as well, which is an interesting feature for decision-support scenarios. this work suggests a way to apply intuitionistic logicprogramming to SQL, and provides a pointer to a working system implementing this idea.
We propose an analysis for detecting procedures and goals that are deterministic (i.e. that produce at most one solution), or predicates whose clause tests are mutually exclusive (which implies that at most one of the...
详细信息
ISBN:
(纸本)3540266550
We propose an analysis for detecting procedures and goals that are deterministic (i.e. that produce at most one solution), or predicates whose clause tests are mutually exclusive (which implies that at most one of their clauses will succeed) even if they are not deterministic (because they call other predicates that can produce more than one solution). Applications of such determinacy information include detecting programming errors, performing certain high-level programtransformations for improving search efficiency, optimizing low level code generation and parallel execution, and estimating tighter upper bounds on the computational costs of goals and data sizes, which can be used for program debugging, resource consumption and granularity control, etc. We have implemented the analysis and integrated it in the CiaoPP system, which also infers automatically the mode and type information that our analysis takes as input. Experiments performed on this implementation show that the analysis is fairly accurate and efficient.
In a world where trusting software systems is increasingly important, formal methods and formal proof can help provide trustable foundations. Proof checking can help to reduce the size of the trusted base since we do ...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
In a world where trusting software systems is increasingly important, formal methods and formal proof can help provide trustable foundations. Proof checking can help to reduce the size of the trusted base since we do not need to trust an entire theorem prover if we can check the proofs they produce by a trusted (and smaller) checker. Many approaches to building proof checkers require embedding within them a full programming language. In most many modern proof checkers and theorem provers, that programming language is a functional programming language, often a variant of ML. In fact, parts of ML (e.g., strong typing, abstract datatypes, and higher-order programming) were designed to make ML into a trustworthy "meta-language" for checking proofs. While there is considerable overlap in the foundations of logicprogramming and proof checking (both benefit from unification, backtracking search, efficient term structures, etc.), the discipline of logicprogramming has, in fact, played a minor role in the history of proof checking. I will argue that logicprogramming can have a major role in the future of this important topic.
Competitive abstract machines for Prolog are usually large, intricate, and incorporate sophisticated optimizations. this makes them difficult to code, optimize, and, especially, maintain and extend. this is partly due...
详细信息
ISBN:
(纸本)9783540714095
Competitive abstract machines for Prolog are usually large, intricate, and incorporate sophisticated optimizations. this makes them difficult to code, optimize, and, especially, maintain and extend. this is partly due to the fact that efficiency considerations make it necessary to use low-level languages in their implementation. Writing the abstract machine (and ancillary code) in a higher-level language can help harness this inherent complexity. In this paper we show how the semantics of basic components of an efficient virtual machine for Prolog can be described using (a variant of) Prolog which retains much of its semantics. these descriptions are then compiled to C and assembled to build a complete bytecode emulator. thanks to the high level of the language used and its closeness to Prolog the abstract machine descriptions can be manipulated using standard Prolog compilation and optimization techniques with relative ease. We also show how, by applying programtransformations selectively, we obtain abstract machine implementations whose performance can match and even exceed that of highly-tuned, hand-crafted emulators.
this article proposes a method for proving the correctness of graph algorithms by manipulating their spanning trees enriched with additional references. We illustrate this concept with a proof of the correctness of a ...
详细信息
ISBN:
(纸本)9783642205507
this article proposes a method for proving the correctness of graph algorithms by manipulating their spanning trees enriched with additional references. We illustrate this concept with a proof of the correctness of a (pseudo-)imperative version of the Schorr-Waite algorithm by refinement of a functional one working on trees. It is composed of two orthogonal steps of refinement - functional to imperative and tree to graph - finally merged to obtain the result. Our imperative specifications use monadic constructs and syntax sugar, making them close to common imperative languages. this work has been realized within the Isabelle/HOL proof assistant.
this book constitutes the thoroughly refereed post-proceedings of the 20thinternationalsymposium on logic-basedprogramsynthesis and transformation, LOPSTR 2010, held in Hagenberg, Austria in July 2010. the 13 revi...
详细信息
ISBN:
(数字)9783642205514
ISBN:
(纸本)9783642205507
this book constitutes the thoroughly refereed post-proceedings of the 20thinternationalsymposium on logic-basedprogramsynthesis and transformation, LOPSTR 2010, held in Hagenberg, Austria in July 2010. the 13 revised full papers presented together with two invited papers were carefully reviewed and selected from 26 submissions. Among the topics covered are specification, synthesis, verification, analysis, optimization, specialization, security, certification, application and tools, program/model manipulation, and transformation techniques for any programming language paradigm.
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.
暂无评论