A proof system for concurrent ADA programs

A subset of ADA is introduced, ADA-CF, to study the basic synchronization and communication primitive of ADA, the rendezvous. Basing ourselves on the techniques introduced by Apt, Francez and de Roever for their CSP proof system, we develop a Hoare-style proof system for proving partial correctness properties which is sound and relatively complete. The proof system is then extended to deal with safety, deadlock, termination and failure. No prior exposure of the reader to parallel program proving techniques is presupposed. Two non-trivial example proofs are given of ADA-CF programs; the first one concerns a buffered producer-consumer algorithm, the second one a parallel sorting algorithm due to Brinch Hansen. Features of ADA expressing dynamic process creation and realtime constraints are not covered by our proof methods. Consequently, we do not claim that the methods described can be extended to full ADA without serious additional further research.     

A system for analysing Ada programs at run-time

This paper describes a prototype system for analysing core dump files from crashed Ada programs. In addition the general question of Ada runtime debugging is discussed. It is suggested that the Ada scope rules are not appropriate to control visibility in this situation. An alternative scheme has been implemented in the prototype. Some first impressions of live use of the Ada language are included among the conclusions.     

A proof method for cyclic programs

Summary We consider the specification and verification of cyclic (sequential and concurrent) programs. The input-output based concept of correctness traditionally applied to functional programs is replaced by another, based on the concept of eventual behaviour. Various types of eventual behaviour are introduced. In the case of concurrency, the introduction of interface-predicates reduces the proof complexity and achieves greater readability. All specifications use explicitly the auxiliary variables of a location counter and elapsing time t.The research of N.F. was partially supported by The Fund for Aiding Research, Histadrut, The Federation of Hebrew workers in Israel     

A methodology for designing proof rules for fair parallel programs

We propose a methodology for designing sound and complete proof systems for proving progress properties of parallel programs under various fairness assumptions. Our methodology begins with a branching time temporal logic formula (CTL^*) formula that expresses progress under a fairness assumption. The next step obtains an equivalent fixpoint characterization of this CTL^* formula in the-calculus. The final step uses the fixpoint characterizations to extract proof systems for proving progress under the fairness constraint. The methodology guarantees that the proof rules so obtained are sound and relatively complete in the sense of Cook.     

A self-updating model for analysing system reconfigurability

Systems are built by connecting different components (e.g., sensors, actuators, process components) that are, in turn, organized to achieve system objectives. But, when a system component fails, the system's objectives can no longer be achieved. For many years, numerous studies have proposed efficient fault detection and isolation (FDI) and fault-tolerant control (FTC) algorithms. This paper considers faults that lead to the complete failure of actuators. In this specific case, the system's physical structure changes, and the system model thus becomes incorrect. The potential that the system has to continue to achieve its objectives has to be re-evaluated from a qualitative point of view, before recalculating or modifying the control algorithms. To this end, this paper proposes a self-updating system model to reflect the current system potential, a formulation of system objectives using temporal logic, and a verification method based on model checking to verify whether the objectives can still be achieved by the faulty system. The systems considered are discrete-continuous systems.     

Polyvariant mixed computation for analyzer programs

Summary A polyvariant mixed computation algorithm for low-level non-structured programs is presented. A subclass of so called analyser programs has been chosen for which all partial computation that becomes possible during mixed computation is defined over a finite domain of nonsuspended variables. This not only provides termination of mixed computation but allows also to embody in the residual program a control structure encoded in the data.     

A proof system for distributed processes

Summary A partial correctness proof system for Brinch Hansen's Distributed Processes (DP) is presented. Two important aspects of the system are: Proofs of individual processes of a DP program are completely isolated from each other; in particular, no assumptions are allowed in the proof of one process about the behavior of the other processes. Secondly a process is characterized by its externally visible behavior, i.e. the sequence of interactions between this process and the other processes of the program. An example demonstrates the use of the system.This paper is an extended version of a paper presented at the Workshop on Logics of Programs, Brooklyn, New York, June 17–19, 1985 and was supported in part by the National Science Foundation under grant ECS-8404725     

A proof system for distributed processes

Summary A partial correctness proof system for Brinch Hansen’s Distributed Processes (DP) is presented. Two important aspects of the system are: Proofs of individual processes of a DP program are completely isolated from each other; in particular, no assumptions are allowed in the proof of one process about the behavior of the other processes. Secondly a process is characterized by its externally visible behavior, i.e. the sequence of interactions between this process and the other processes of the program. An example demonstrates the use of the system. This paper is an extended version of a paper presented at the Workshop on Logics of Programs, Brooklyn, New York, June 17–19, 1985 and was supported in part by the National Science Foundation under grant ECS-8404725.     

An axiomatic proof technique for parallel programs I

Summary A language for parallel programming, with a primitive construct for synchronization and mutual exclusion, is presented. Hoare's deductive system for proving partial correctness of sequential programs is extended to include the parallelism described by the language. The proof method lends insight into how one should understand and present parallel programs. Examples are given using several of the standard problems in the literature. Methods for proving termination and the absence of deadlock are also given.This research was partially supported by National Science Foundation grant GJ-42512.     

A computerised system for analysing working postures in agriculture

This paper aims to show a computerised program for analysing work postures in agriculture. The system contains two types of routines for studies of observation, Working Posture Analysing Sytem (WOPALAS) and a simple Video film technique for Registration and Analysis of working postures and movements (VIRA). Furthermore the system consists of programs for moment calculations and routines for registration of problems in the locomotive organs. The computerised system provides several advantages compared with traditional manual systems. For the operator, it is a less demanding work and the analyses are more accurate. The system rapidly provides the results of an analysis.     

A space and time efficient algorithm for SimRank computation

SimRank has become an important similarity measure to rank web documents based on a graph model on hyperlinks. The existing approaches for conducting SimRank computation adopt an iteration paradigm. The most efficient deterministic technique yields O(n³)O\left(n^3\right) worst-case time per iteration with the space requirement O(n²)O\left(n^2\right), where n is the number of nodes (web documents). In this paper, we propose novel optimization techniques such that each iteration takes O (min{ n ·m , n^r })O \left(\min \left\{ n \cdot m , n^r \right\}\right) time and O ( n + m )O \left( n + m \right) space, where m is the number of edges in a web-graph model and r ≤ log₂ 7. In addition, we extend the similarity transition matrix to prevent random surfers getting stuck, and devise a pruning technique to eliminate impractical similarities for each iteration. Moreover, we also develop a reordering technique combined with an over-relaxation method, not only speeding up the convergence rate of the existing techniques, but achieving I/O efficiency as well. We conduct extensive experiments on both synthetic and real data sets to demonstrate the efficiency and effectiveness of our iteration techniques.     

A simplex algorithm for on-line computation of time optimal controls

The minimum-time regulator problem is solved computationally for general linear-discrete systems by a modification of the simplex algorithm of linear programming (LP). The algorithm presented is faster than the LP solutions devised previously, taking but a single application to solve for the optimal control. An extension of the LP bounded-variable technique further reduces computer time and storage requirements. Application to a sixth-order process with two control inputs shows that the algorithm is sufficiently economical of running time and storage to be implemented on-line with a small process-control computer.     

A language-independent proof system for full program equivalence

Two programs are fully equivalent if, for the same input, either they both diverge or they both terminate with the same result. Full equivalence is an adequate notion of equivalence for programs written in deterministic languages. It is useful in many contexts, such as capturing the correctness of program transformations within the same language, or capturing the correctness of compilers between two different languages. In this paper we introduce a language-independent proof system for full equivalence, which is parametric in the operational semantics of two languages and in a state-similarity relation. The proof system is sound: a proof tree establishes the full equivalence of the programs given to it as input. We illustrate it on two programs in two different languages (an imperative one and a functional one), that both compute the Collatz sequence. The Collatz sequence is an interesting case study since it is not known whether the sequence terminates or not; nevertheless, our proof system shows that the two programs are fully equivalent (even if we cannot establish termination or divergence of either one).     

A type system for logic programs

A theory for a type system for logic programs is developed which addressesthe question of well-typing, type inference, and compile-time and run-time type checking. A type is a recursively enumerable set of ground atoms, which is tuple-distributive. The association of a type to a program is intended to mean that only ground atoms that are elements of the type may be derived from the program. A declarative definition of well-typed programs is formulated, based on an intuitive approach related to the fixpoint semantics of logic programs. Whether a program is well typed is undecidable in general. We define a restricted class of types, called regular types, for which type checking is decidable. Regular unary logic programs are proposed as a specification language for regular types. An algorithm for type-checking a logic program with respect to a regular type definition is described, and its complexity is analyzed. Finally, the practicality of the type system is discussed, and some examples are shown. The type system has been implemented in FCP for FCP and is incorporated in the Logix system.     

A proof system for communicating processes with value-passing

A proof system for a version of CCS with value-passing is proposed in which the reasoning about data is factored out from that about the structure of processes. The system is shown to be sound and complete for finite terms with respect to a denotational semantics based on Acceptance Trees.     

A unifying framework for analysing common cyclical features in cointegrated time series

A unifying framework in which the coexistence of differing forms of common cyclical features can be tested and imposed upon a cointegrated VAR model is provided. This is achieved by introducing a new notion of common cyclical features, described as the weak form of polynomial serial correlation, which encompasses most of the existing formulations. Statistical inference is based upon reduced-rank regression, and alternative forms of common cyclical features are detected through tests for over-identifying restrictions on the parameters of the new model. Some iterative estimation procedures are then proposed for simultaneously modelling various forms of common features. The concepts and methods of the paper are illustrated via an empirical investigation of the US business cycle indicators.     

A system subdivision approach for large radiosity computation

O (n) for n subsystems. Moreover, the data necessary for each subsystem computation is completely localized, which allows the database to be stored on disk. The algorithm can easily be implemented with a slight modification of the hierarchical radiosity algorithm. Experiments demonstrate the efficiency of the algorithm.     

A model and temporal proof system for networks of processes

An approach is presented for modeling networks of processes that communicate exclusively through message passing. A process (or a network) is defined by its set of possible behaviors, where each behavior is an abstraction of an infinite execution sequence of the process. The resulting model is simple and modular and facilitates information hiding. It can describe both synchronous and asynchronous networks. It supports recursively-defined networks and can characterize liveness properties such as progress of inputs and outputs, termination, and deadlock.A sound and complete temporal proof system based on the model is presented. It is compositional — a specification of a network is formed naturally from specifications of its components.Van Nguyen received a B.S. degree from Monash University in 1982, an M.S. degree from Cornell University in 1983 and a Ph.D. degree from Cornell University in 1985. He has accepted a research position at the IBM Thomas J. Watson Research Center. His research interests include logics and semantics of programs, programming languages, program synthesis and distributed computing.David Gries received a Ph.D. (actually, a Dr. rer. nat.) from the Munich Institute of Technology (Germany) in 1966. He was an assistant professor at Stanford from 1966 to 1969 and has been on the faculty of Computer Science at Cornell since 1969, where he is presently chairman of the department. He is known for his research in compilers (he is a co-author of the Alcor-Illinois 7090 Algol compiler, finished in 1964), for his research in programming methodology, and for his texts Compiler Construction for Digital Computers (1971) and Science of Programming (1981). He was a Guggenheim Fellow in 1984–85.Susan Owicki received the B.S. degree in mathematics from Michigan State University in 1968. She then attended Cornell University as an NSF Fellow, receiving the M.S. and Ph.D. degrees in computer science in 1970 and 1975, respectively. From 1975 to 1976 she was an Assistant Professor in the Department of Computer Science at Cornell University. Since then she has been a member of the Department of Electrical Engineering at Stanford University, where she is currently an Associate Professor.Dr. Owicki's research in the area of concurrent programming has included work in program verification, programming languages and methodology, and design of algorithms for concurrent systems. She has been particularly interested in problems in computer networks and distributed systems.This work was supported by the NSF under grants MCS-81-03605, DCR-83-202-74, and DCR-83-123-19; by NASA under contract NAGW419; and by the third author's Guggenheim FellowshipThis paper is based on part of the first author's Ph.D. thesis     

An expert system for setting time steps in dynamic finite element programs

An expert system, ETUDES—Expert Time integration control Using Deep and Surface Knowledge System, which addresses the determination of the timestep for time integration of linear structural dynamic equations is described. This time-step may also be applicable for a moderately nonlinear simulation of the same structure. The program also determines whether an explicit or implicit method is most efficient for the particular simulation. A production rule programming system written in OPS5 is used for the implementation of this prototype expert system. Issues relating to the expert system architecture for this application, such as knowledge representation and structure, as well as domain knowledge are discussed. The prototype is evaluated by measuring it's performance in various benchmark model problems.