Presents a method for the modular specification and verification of data abstractions in which multiple abstract objects share a common realization level data structure. Such shared realizations are an important implementation technique for data abstractions, because they provide for efficient use of memory; i.e., they allow the amount of memory allocated to the realization of an abstract object to be dynamic, so that only the amount of memory needed for its realization is allocated to it at any one time. To be explicit, an example of this kind of data abstraction is given. Although a number of programming languages provide good support for shared realizations, there has been limited research on its specification and verification. An important property of The authors' method is that it allows data abstractions to be dealt with modularly; i.e., each data abstraction can be specified and verified individually. Its abstract specification is made available for use by other program modules, but all of its implementation details are hidden, which simplifies the verification of code that uses the abstraction. The authors have developed semantics for data abstractions and their method of specification, and have used it to prove that their verification method is logically sound and relatively complete in the sense of Cook (1978). The use of shared realizations impacts specification and verification in several related ways. The manipulation of one abstract object may inadvertently produce a side effect on other abstract objects. Without shared realizations, such unwanted side effects can be prevented by scoping rules, but this is not possible with shared realizations. Instead, the absence of such side effects must be explicitly proven by the verification method. This requires the specification language to provide for quantification over the currently active (allocated) instances of an abstract type that is not necessary for the specification of less advanced implementations of data abstractions.>

This paper describes a Fault Explanation System (FES) that aids in the diagnosis of failures in discrete event systems such as certain manufacturing processes. These systems are characterized by the use of programmable logic controllers (PLC) to control the systems. In addition PLC's also perform event logging. The event log (fault log) records exceptions which may be alarms, warnings or status reports. A major difficulty is that most of the alarms do not indicate real faults in the system; for example, a fault may cause an exception which indicates what the fault is, but this exception may also give rise to a number of other exceptions which are just side-effects. FES interprets and explains faults in the log based on a model provided by the ladder logic diagrams of the PLC. These explanations separate real exceptions from the kind of side-effects described above. Finally FES ranks explanations according to their plausibility.

This research assumes that a problem-solving method has an applicabdtty condmon which specifies the properties of "good" problem-dependent parameters for the method Such a condition Is used as the basis of a computer program that mechamcally generates good parameters for the method to use in solving the problem Such problem-dependent parameters for a method constitute a problem-solving strategy.To show the feastbdity of this approach, it is used on two different methods' the GPS method for solving problems and the Nim-hke method for playing games That as, for each is constructed a program that generates good problem-dependent parameters for the input problem (or game) speclficaUon.These programs and their empirical results on a number of different problems and games are described The programs appear to be reasonably efficient and powerful In pamcular, each discovered some nonobvlous strategies Categories and Subject Descriptors 1.2 6 [

Symbolic execution provides a mechanism for formally proving programs correct. A notation is introduced which allows a concise presentation of rules of inference based on symbolic execution. Using this notation, rules of inference are developed to handle a number of language features, including loops and procedures with multiple exits. An attribute grammar is used to formally describe symbolic expression evaluation, and the treatment of function calls with side effects is shown to be straightforward. Because symbolic execution is related to program interpretation, it is an easy-to-comprehend, yet powerful technique. The rules of inference are useful in expressing the semantics of a language and form the basis of a mechanical verification condition generator.

The programming language MODULA is extended to permit the formal specification of the structure and functional capabilities of modules. This makes true hierarchical programming possible in MODULA by allowing programmers of higher level parts of a system to ignore completely the internal structure of lower level modules and to rely entirely on the specifications of the capabilities of these modules. An example is included to illustrate this technique. We show that our specification mechanisms are sufficiently powerful to support formal verification rules for modules that have disjoint representations for abstract objects.

This paper describes a theorem prover, running on a PDP-10-Tenex system, that can prove some theorems whose statements involve a relatively large number of definitions. Such theorems require special methods because 1) their statements contain a large number of clauses and 2) their proofs are quite long although straightforward.

This paper focuses on the interface between program verification and mechanical theorem proving. It is often much easier to express what a program does in higher order logic than in first-order logic. However, in general, higher order theorem proving is difficult to mechanize. Hence we have isolated some special classes of higher order formulas and will show how they can be processed efficiently by a computer. Examples are given that illustrate how naturally these formulas arise in program verification.

A formal model of a problem is developed and its relationship to the General Problem Solver (GPS) is discussed. Before GPS can work on a problem it must be given differences, a difference-ordering, and a table of connections, in addition to the specifications of a problem. Formal definitions of this additional information are given, and sufficient conditions for the success of GPS are derived. These conditions point out the utility of differences and a difference-ordering that yield a “triangular” table of connections. Several different formulations of the Tower of Hanoi are given to illustrate the formal concepts. The use of subproblems in narrowing search is discussed.