Search

Two trends are highlighted here, in the area of automated theorem proving: the integration of reasoning methods for propositional and first-order logic, with a best-of-both-worlds motivation; and built-in reasoning support modulo background theories. [ABSTRACT FROM AUTHOR]

Maxwell's stress equation for magnetostatics identifies a tensile stress in the direction of the magnetic field and a pressure normal to this direction. For an isolated, differential current element, Maxwell's stress equation is recast using a variant of Stokes' Theorem. The recast stress equation eliminates the tensile stress in the direction of the magnetic field and establishes a stress that is normal to the magnetic field, directed inward toward the differential current element. For two separated current elements, Maxwell's stress equation is also recast, identifying a constant line stress directionally aligned between the two current elements. The magnitude of the line stress is equivalent to the two current element Neumann force. The analysis and manipulation of Maxwell's stress equation provides some insight into magnetostatic stresses and establishes additional tools for the electrical engineer when analyzing magnetostatic system stresses. [ABSTRACT FROM PUBLISHER]

Strong typicality, which is more powerful for theorem proving than weak typicality, can be applied to finite alphabets only, while weak typicality can be applied to countable alphabets. In this paper, the relation between typicality and information divergence measures is discussed. The new definition of information divergence measure in this paper leads to the definition of a unified typicality for finite or countably infinite alphabets which is stronger than both weak typicality and strong typicality. Unified typicality retains the asymptotic equipartition property and the structural properties of strong typicality, and it can potentially be used to generalize those theorems which are previously established by strong typicality to countable alphabets. The applications in rate-distortion theory and multisource network coding problems are discussed. [ABSTRACT FROM PUBLISHER]

The growing complexity of systems and their implementation into silicon encourages designers to look for ways to model designs at higher levels of abstraction and then incrementally build portions of these designs--automatically or manually--from these high-level specifications. Unfortunately, this translation process itself can be buggy, which can create a mismatch between what a designer intends and what is actually implemented in the circuit. Therefore, checking if the implementation is a refinement or equivalent to its initial specification is of tremendous value. In this paper, we present an approach to automatically validate the implementation against its initial high-level specification using insights from translation validation, automated theorem proving, and relational approaches to reasoning about programs. In our experiments, we first focus on concurrent systems modeled as communicating sequential processes and show that their refinements can be validated using our approach. Next, we have applied our validation approach to a realistic scenario--a parallelizing high-level synthesis framework called Spark. We present the details of our algorithm and experimental results. [ABSTRACT FROM AUTHOR]

Real number calculations on elementary functions are remarkably difficult to handle in mechanical proofs. In this paper, we show how these calculations can be performed within a theorem prover or proof assistant in a convenient and highly automated as well as interactive way. First, we formally establish upper and lower bounds for elementary functions. Then, based on these bounds, we develop a rational interval arithmetic where real number calculations take place in an algebraic setting. In order to reduce the dependency effect of interval arithmetic, we integrate two techniques: interval splitting and Taylor series expansions. This pragmatic approach has been developed, and formally verified, in a theorem prover. The formal development also includes a set of customizable strategies to automate proofs involving explicit calculations over real numbers. Our ultimate goal is to provide guaranteed proofs of numerical properties with minimal human theorem-prover interaction. [ABSTRACT FROM AUTHOR]

The article discusses the hybrid computer system verification process that combines theorem proving with model checking through predicate abstraction. The author contends that there is a gap in the complexity verification tools can handle and practical verification problems that can be lessened via theorem proving with model checking through predicate abstraction.

The article offers an overview of hybrid techniques for functional verification of computer hardware. The article discusses the taxonomy of hybrid methods, ATPG and formal techniques, methods combining formal techniques, trajectory evaluation and theorem proving, combining theorem provers and decision procedures, and composition of model-checking runs.

As the use of nonclassical logics becomes increasingly important in computer science, artificial intelligence and logic programming, the development of efficient automated theorem proving based on nonclassical logic is currently an active area of research. This paper aims at the resolution principle for the Pavelka type fuzzy logic. Pavelka showed (in 1979) that the only natural way of formalizing fuzzy logic for truth-values in the unit interval [0, 1] is by using the Lukasiewicz's implication operator a → b = min{1, 1 - a + b} or some isomorphic forms of it. Hence, we first focus on the resolution principle for the Lukasiewicz logic L[sub N] with [0, 1] as the truth-valued set. Some limitations of classical resolution and resolution procedures for fuzzy logic with Kleene implication are analyzed. Then some preliminary ideals about combining resolution procedure with the implication connectives in L[sub N] are given. Moreover, a resolution-like principle in L[sub N] is proposed and the soundness theorem of this resolution procedure is also proved. Second, we use this resolution-like principle to Horn clauses with truth-values in an enriched residuated lattice and consider the L-type fuzzy Prolog. [ABSTRACT FROM AUTHOR]

Discusses automatic verification of self-stabilizing algorithms. Mechanical theorem proving; Process of exploring a finite state space to determine whether or not a given property holds; Symbolic model checking; Verification of self-stabilization using Symbolic Model Verifier.

Achieving interactive consistency among processors in the presence of faults is an important problem in fault tolerant computing, first cleanly formulated by Lamport, Pease, and Shostak and solved in selected cases with their Oral Messages (OM) algorithm. Several machine-supported verifications of this algorithm have been presented, including a particularly elegant formulation and proof by John Rushby using EHDM and PVS. Rushby proposes interactive consistency as a benchmark problem for specification and verification systems. We present a formalization of the OM algorithm in the ACL2 logic and compare our formalization and proof to his. We draw some conclusions concerning the range of desirable features for verification systems. In particular, while higher-order functions, strong typing, lambda abstraction, and full quantification have some value they come with a cost; moreover, many uses of such features can be easily translated into simpler logical constructs, which facilitate more automated proof discovery. We offer a cautionary note about comparing systems with respect to a small set of problems in a limited domain. [ABSTRACT FROM AUTHOR]

ACL2 is a reimplemented extended version of Boyer and Moore's Nqthm and Kaufmann's Pc-Nqthm, intended for large scale verification projects. This paper deals primarily with how we scaled up Nqthm's logic to an "industrial strength" programming language-namely, a large applicative subset of Common Lisp-while preserving the use of total functions within the logic. This makes it possible to run formal models efficiently while keeping the logic simple. We enumerate many other important features of ACL2 and we briefly summarize two industrial applications: a model of the Motorola CAP digital signal processing chip and the proof of the correctness of the kernel of the floating point division algorithm on the AMD5K86 microprocessor by Advanced Micro Devices, Inc. [ABSTRACT FROM AUTHOR]

How should iterators be abstracted and encapsulated in modern imperative languages? We consider the combined impact of several factors on this question: the need for a common interface model for user defined iterator abstractions, the importance of formal methods in specifying such a model, and problems involved in modular correctness proofs of iterator implementations and clients. A series of iterator designs illustrates the advantages of the swapping paradigm over the traditional copying paradigm. Specifically, swapping based designs admit more efficient implementations while offering relatively straight- forward formal specifications and the potential for modular reasoning about program behavior. The final proposed design schema is a common interface model for an iterator for any generic collection. [ABSTRACT FROM AUTHOR]

This paper describes a uniform approach to the automation of verification tasks associated with while statements, representation functions for abstract data types, generic program units, and abstract base classes. Program units are annotated with equations containing symbols defined by algebraic axioms. An operation's axioms are developed by using strategies that guarantee crucial properties such as convergence and sufficient completeness. Sets of axioms are developed by stepwise extensions that preserve these properties. Verifications are performed with the aid of a program that incorporates term rewriting, structural induction, and heuristics based on ideas used in the Boyer-Moore prover. The program provides valuable mechanical assistance: managing inductive arguments and providing hints for necessary lemmas, without which formal proofs would be impossible. The successes and limitations of our approaches are illustrated with examples from each domain. [ABSTRACT FROM AUTHOR]

In this paper we describe an implementation of a rule-based theorem prover for verifying iterative programs over integers. The soundness and the completeness issues of the constituent rules have been treated at length in [1]; their effectiveness in treating quantified formulas, especially in the context of programs involving array variables, has been discussed in [2]. Here we emphasize the overall proof construction strategy of the prover. The prover has been able to construct the correctness proofs of all iterative programs taken from the literature [3], [4]. Two performance measures of the prover have been proposed and its proof construction for an array-sorting program has been evaluated using these measures. [ABSTRACT FROM AUTHOR]

Kit is a small multitasking operating system kernel written in the machine language of a uniprocessor von Neumann computer. The kernel is proved to implement on this shared computer a fixed number of conceptually distributed communicating processes. In addition to implementing processes, the kernel provides the following verified services: process scheduling, error handling, message passing, and an interface to asynchronous devices. As a by-product of the correctness proof, security related results such as the protection of the kernel from tasks and the inability of tasks to enter supervisor mode are proved. The problem is stated in the Boyer-Moore logic, and the proof is mechanically checked with the Boyer-Moore theorem prover. [ABSTRACT FROM AUTHOR]

Because of the undecidability problem of program verification it becomes necessary for an automated verifier to seek human assistance for proving theorems which fall beyond its capability. So that the user is able to interact smoothly with the machine, it is desired that the theorems be maintained and processed by the prover in a form as close as possible to the popular algebraic notation. Motivated by the need of such an automated verifier, which works in an environment congenial to easier human participation and at the same time employs the methodologies of resolution provers of first-order logic, some inference rules have been proposed in 1331 for integer arithmetic and their completeness issues have been discussed. The present paper examines how these rules can be applied to quantified formulas vis-a-vis verification of programs involving arrays. An interesting situation, referred to here as bound-extension, has been found to occur frequently in proving the quantified verification conditions (VC's) of the paths in a program. A new rule, called the hound-extension rule (rbe, has been devised to consolidate and depict the various issues involved in a bound-extension process. Subsequently, it has been proved that the rule-set proposed in [33] is adequate for handling a more general phenomenon, called bound-modification, which covers bound-extension in all its entirety. Also, while proving the result, a unified approach has emerged for implementation of various cases of bound-modification in a prover. This approach accomplishes the proof (of bound-modification) at a much lesser cost than would be possible by the explicit rule rbe. [ABSTRACT FROM AUTHOR]

This paper describes the data type definition facilities of the AFFIRM system for program specification and verification. Following an overview of the system, we review the rewrite rule concepts that form the theoretical basis for its data type facilities. The main emphasis is on methods of ensuring convergence (finite and unique termination) of sets of rewrite rules and on the relation of this property to the equational and inductive proof theories of data types. [ABSTRACT FROM AUTHOR]

Reviews the history of the use of computers to automate mathematical proofs. Development of ideas of proof in mathematics and logic prior to the advent of the digital computer; Discussion of the early automated theorem provers of the 1950s; Development in 1963 of the best known of the techniques of automated theorem proof; History of the automatic theorem after the development of resolution. INSET: Resolution..

The article presents samples of the most promising areas Chinese artificial intelligence (AI) researchers have been studying for the past 50 years and predicts related future activities in AI technology. Mathematics professor Wen-Tsun Wu developed a method that initiates the use of algebraic geometrical methods to retrieve analytical solutions to complex mathematical problems. His work has been considered as the factor that re-invigorated the field of Automated Geometrical Theorem Proving. It has been used to enhance a theoretical framework that scientists and engineers use to solve various problems. It has been predicted that this method will be used to extend mathematical mechanization and robot research. Other significant researches were also discussed in detail.

This note shows that the basic theoretical tool used for smoothing data in the above paper is almost indistinguishable from the method presented in an earlier paper. [ABSTRACT FROM AUTHOR]