Search

Requirements definition encompasses all aspects of system development prior to actual system design. We see the lack of an adequate approach to requirements definition as the source of major difficulties in current systems work. This paper examines the needs for requirements definition, and proposes meeting the objectives with thee interrelated subjects: context analysis, functional specification, and design constraints. Requirements definition replaces the widely used, but never well-defined, term "requirements analysis." The purpose of this paper is to present, in a comprehensive manner, concepts that apply throughout requirements definition (and, by implication, to all of system development). The paper discusses the functional architecture of systems, the characteristics of good requirements documentation, the personnel involved in the process of analysis, and management guidelines that are effective even in complex environments. The paper then outlines a systematic methodology that incorporates, in both notation and technique, the concepts previously introduced. Reference is made to actual requirements definition experience and to practicable automated support tools that may be used with the methodology. [ABSTRACT FROM AUTHOR]

Structured analysis (SA) combines blueprint-like graphic language with the nouns and verbs of any other language to provide a hierarchic, top-down, gradual exposition of detail in the form of an SA model. The things and happenings of a subject are expressed in a data decomposition and an activity decomposition, both of which employ the same graphic building block, the SA box, to represent a part of a whole. SA arrows, representing input, output, control, and mechanism, express the relation of each part to the whole. The paper describes the rationalization behind some 40 features of the SA language, and shows how they enable rigorous communication which results from disciplined, recursive application of the SA maxim: "Everything worth saying about anything worth saying something about must be expressed in six or fewer pieces." [ABSTRACT FROM AUTHOR]

This paper describes a methodology for the generation of software requirements for large, real-time unmanned weapons systems. It describes what needs to be done, how to evaluate the intermediate products, and how to use automated aids to improve the quality of the product. An example is provided to illustrate the methodology steps and their products and the benefits. The results of some experimental applications are summarized. [ABSTRACT FROM AUTHOR]

This paper contains a discussion of the Software Development System (SDS), a methodology addressing the problems involved in the development .of software for ballistic missile defense systems. These are large real-time, automated systems with a requirement for high reliability. The SDS is a broad approach attacking problems arising in requirements generation, software design, coding, and testing. The approach is highly requirements oriented and has resulted in the formulation of structuring concepts, a requirements statement language, process design language, and support software to be used throughout the development cycle. This methodology represents a significant advance in software technology for the development of software for a class of systems such as BMD. The support software has been implemented and is undergoing evaluation. [ABSTRACT FROM AUTHOR]

In a distributed computing system a modular program must have its modules assigned among the processors so as to avoid excessive interprocessor communication while taking advantage of specific efficiencies of some processors in executing some program modules. In this paper we show that this program module assignment problem can be solved efficiently by making use of the well-known Ford-Fulkerson algorithm for finding maximum flows in commodity networks as modified by Edmonds and Karp, Dinic, and Karzanov. A solution to the two-processor problem is given, and extensions to three and n-processors are considered with partial results given without a complete efficient solution. [ABSTRACT FROM AUTHOR]

This paper presents the formalism of Production Systems and investigates its application to define the syntax and translation of programming languages. Several properties appear well-suited to this task: 1) the formalism can be used to specify exactly the syntax of a computer language, including context-sensitive requirements; 2) the specification of the context-sensitive requirements on syntax can be isolated from the context-free requirements; 3) the same formalism can be used to specify more general structural properties, including the translation of one language into another. The notation has been developed with readability as a prime design issue. The following examples are given: 1) a specification of the syntax of a small but difficult subset of PL/I; 2) a specification of the rules for translating lambda-calculus expressions into normal form. [ABSTRACT FROM AUTHOR]

A general iterative control structure with multiple exits and multiple returns to the beginning of the loop is described. The conditions causing these exits or returns must be declared and defined in a prologue to the loop in a manner which is similar to the declaration of variables at the beginning of a block. Also, actions prior to an exit or a return may be specified in an epilogue of the loop. The semantics of the structure are described informally and then formally by means of a Hoare type verification rule. Attributes of the structure and examples of its usage are given in the latter part of the paper. [ABSTRACT FROM AUTHOR]

An important resource allocation mechanism in virtual storage operating systems is the maintainance of the multiprogramming level in main storage, especially when some form of working-set storage management strategy is employed. Swapping of programs in and out of main memory occurs when sufficient storage becomes available and when total storage demand exceeds capacity. In this paper, we propose a class of swapping algorithms that couples storage management parameters with swapping decisions. An analytic model is developed and numerical results are presented to compare the performance of these algorithms. [ABSTRACT FROM AUTHOR]

This paper summarizes the initial experience with the programming language Concurrent Pascal in the design of three model operating systems. A Concurrent Pascal program consists of modules called processes, monitors, and classes. The compiler checks that the data structures of each module arc accessed only by the operations defined in the module. The author emphasizes that the creative aspect of program construction is the initial selection of modules and the connection of them into hierarchical structures. By comparison the detailed implementation of each module is straightforward. The most important result is that it is possible to build a concurrent program of one thousand lines out of one-page modules that can be comprehended at a glance. [ABSTRACT FROM AUTHOR]

In this paper a general-purpose interactive pattern recognition system is built using limited resources. The system utilizes Ribak's [5] relationship matrix (R-matrix) as a data structure and a PDP-9 minicomputer as hardware. The software developed for the interactive system along with the implemented idea of "vague" relations gives the human operator flexibility and aid in interactive file creation. Files created to describe complex patterns can be formed by merging simpler subfiles of different portions of that pattern. In addition to merging riles (union operation), common elements between files can be detected using an intersection operation. User-defined routines are readily inter faced to the interactive system, thus increasing the system flexibility and giving the human operator a tailor-made effect. [ABSTRACT FROM AUTHOR]

Extended Snobol picture pattern processor (ESP³) is a programming language and pattern recognition system which was designed for generating, recognizing, and manipulating two-dimensional line drawings. An ESP³ picture pattern describes a class of line drawings just as a Snobol pattern describes a class of strings. During pattern matching, a subject picture is searched for the occurrence of a sub- picture which matches a given picture pattern. The search of the subject picture is ordered left-to-right and top-to-bottom, and the search program uses scanner guidance information found in the picture pattern to limit the area of the subject picture to be searched. An experimental implementation of ESP³ has been developed to test the feasibility of the system. This paper describes the ESP³ picture patterns, the pattern matching operation, and the experimental implementation of ESP³. [ABSTRACT FROM AUTHOR]

Usage of the Touch-Tone telephone as a computer input device has increased dramatically during the past five years. The recent decrease in cost and increase in intelligibility of synthetic voice systems has made it possible to couple voice response systems with Touch-Tone telephones to create a low-cost, highly flexible computer terminal. However, usage is primarily restricted to applications that can be accomplished with a limited character set, do not need an extensive user protocol, consist of relatively short interactive sessions, and do not require immediate hard copy feedback. This paper discusses the first of these limitations: the unambiguous representation of 26 letters, 10 digits, and several special characters by the 12 keys of a Touch-Tone keyboard. Existing input schemes often require multiple keying to represent a single alphanumeric character or table look-up of numeric codes to represent a message. An alternative scheme would permit as-is encoding of alphabetic information. Using a specific application, as-is encoding is examined in detail, and the theory for recognition of encoded English phrases is generalized by two algorithms. [ABSTRACT FROM AUTHOR]

Most current approaches to mechanical program verification transform a program and its specifications into first-order formulas and try to prove these formulas valid. Since the first-order predicate calculus is not decidable, such approaches are inherently limited. This paper proposes an alternative approach to program verification: correctness proofs are constructively established by proof justifications written in an algorithmic notation. These proof justifications are written as part of the program, along with the executable code and correctness specifications. A notation is presented in which code, specifications, and justifications are interwoven. For example, if a program contains a specification ∃x P(x), the program also contains a justification that exhibits the particular value of x that makes P true. Analogously, justifications may be used to state how universally quantified formulas are to be instantiated when they are used as hypotheses. Programs so justified may be verified by proving quantifier-free formulas. Additional classes of justifications serve related ends. Formally, justifications reduce correctness to a decidable theory. Informally, justifications establish the connection between the executable code and correctness specifications, documenting the reasoning on which the correctness is based. [ABSTRACT FROM AUTHOR]

In Concurrent Pascal, the syntactic and semantic definition of the language prevents the inadvertent definition of a program that might violate the integrity of a shared data object. However, the language also does not allow the dynamic allocation of reusable resources among processes, and this restriction seems unnecessarily stringent. This paper proposes the addition to Concurrent Pascal of a new type of program component, to be called a resource manager. By this means, dynamic resource allocation can be accomplished both safely and efficiently. The notion that a process holds access Fights to a resource is generalized to the notion that it holds capability rights, but the capability to actually make use of a resource is granted dynamically. The anonymity of dynamically allocatable resources is also guaranteed. [ABSTRACT FROM AUTHOR]

This paper describes a series of psychological experiments used to test a new data base query language. The intent is to make psychological testing of a language part of the design and development process. By testing a language while it is still under development, features that require changing can be identified and the changes made. The experiments, which used college students as subjects, investigated: 1) overall "learnabiity" of the language, 2) "learnabiity" of individual features of the language, and 3) the types and frequencies of errors made. Recommended changes to the particular language and the basis for those recommendations are described. In addition, errors made by experimental subjects during the testing are then analyzed from the point of view of possible causes. Based on this analysis, a preliminary model of query writing and two possible indices of query complexity are suggested. [ABSTRACT FROM AUTHOR]

This paper describes four major aspects of software management: development statistics, development process, development objectives, and software maintenance. The control of both large and small software projects is included in the analysis. [ABSTRACT FROM AUTHOR]

Programs can be analyzed to determine bounds on the ranges of values assumed by variables at various points in the program. This range information can then be used to eliminate redundant tests, verify correct operation, choose data representations, select code to be generated, and provide diagnostic information. Sophisticated analyses involving the proofs of complex assertions are sometimes required to derive accurate range information for the purpose of proving programs correct. The performance of such algorithms may be unacceptable for the routine analysis required during the compilation process. This paper presents a discussion of mechanical range analysis employing techniques practical for use in a compiler. This analysis can also serve as a useful adjunct to the more sophisticated techniques required for program proving. [ABSTRACT FROM AUTHOR]

This paper considers the selection of capacities in two classes of open queueing network models of computer communication systems: 1) local-balanced queueing networks with multiple classes of customers and 2) the Reiser-Kobayashi diffusion approximation model. The problem of selecting optimal bandwidths for communication lines and switches and computing machinery is difficult due to 1) the economy of scale exhibited by components (i.e., the bandwidth per dollar increases with the total cost of the component) and 2) the discrete nature of computer/communication components (for instance it is possible to lease communication lines with 2400-Bd or 4800-Bd bandwidths but not one with a 2401.3-Bd bandwidth). This paper develops an algorithm to select servers taking both of these characteristics of server costs into account. The contribution of this paper is to discuss 1) the optimization of more general network models with 2) the consideration of more realistic tariffs and 3) more constraints on network behavior than were previously analyzed. [ABSTRACT FROM AUTHOR]

This paper concerns the representation and processing of data resulting from the measurement of programs written in high-level programming languages. The value of various "perspectives" of measurement results, especially in languages having many levels of activity, is illustrated. A representation of measurement data based on ideas from relational data bases is presented, in which perspectives can be represented as hierarchically-organized permuted projections of measurement data. Applications described include measurement of Snobol4 and Fortran programs. [ABSTRACT FROM AUTHOR]

This paper deals with obtaining a data base for test and evaluation of large software systems, when at most, only a few typical pattern instances are available, Data structure variation is proposed and demonstrated for some simple images. Relationships to fundamental concepts in computer science methodology are discussed. [ABSTRACT FROM AUTHOR]

Considerable effort has been expanded in attempts to combine the power found in algorithmic languages with the power found in program libraries. However, most of these attempts to construct problem-solving systems for a particular class of users have failed to achieve their objective of providing the user with the potential benefits inherent in such systems. This paper attempts to define and place problem-solving systems in a general context, and thereby shows when the potential for failure or success is high. [ABSTRACT FROM AUTHOR]

Access time is a variable quantity in serial access memory systems such as magnetic tape units. It is difficult to quote a value for it since a random search could cover most different tape lengths. This paper analyzes several search methods. The sequential search and the catenated search are used by the designers of magnetic tape memories [4]. The other methods are proposed by the author. The paper presents relations defining the average access time and permitting a comparison between the efficiency of the methods. At the same time, the paper presents data structures which reduce the average access time. [ABSTRACT FROM AUTHOR]

The Software Hut (a small software house) is a course project designed for a graduate-level course in computer program engineering. This paper describes the Software Hut project and discusses the authors' experience using it in graduate courses at the University of Toronto. Suggestions for improvements in the project are given. [ABSTRACT FROM AUTHOR]

This paper presents the use of the virtual machine concept as a software engineering tool. The focus is on techniques that allow the rapid integration and assimilation of existing data, models, analytical facilities, report-generation facilities, and data base management systems. Since many of these models, programs, and facilities run under different operating systems, they often are incompatible with each other. By combining multiple virtual machines in a particular configuration, and allowing for communication among them, it has been possible to overcome these difficulties. The result is a set of software engineering tools that seem particularly useful in decision support systems. We present the application of these tools along with the software techniques used to implement them, and quantify some of their costs and benefits. [ABSTRACT FROM AUTHOR]

This paper discusses dynamic properties of data structures under insertions and deletions. It is shown that, in certain circumstances, the result of n random insertions and m random deletions will be equivalent to n-m random insertions, under various interpretations of the world "random" and under various constraints on the order of insertions and deletions. [ABSTRACT FROM AUTHOR]

This paper describes a method for increasing the batch-processing efficiency of medium and large scale scientific compute, systems with a small main memory. A program-replacement algorithm, RESEP, is defined whose goal is to always keep the CPU busy. RESEP temporarily transfers selected programs from main memory to the secondary storage. Reallocation of such programs is also performed by this algorithm. We will compare throughput using the RESEP strategy with that using the well-known FCFS strategy by means of simple queueing networks. This comparison shows the increase in throughput achieved by RESEP over FCFS as a function of the workload parameters. We will show that a two-disk channel system running under FCFS is less efficient than a one-channel system running under RESEP. [ABSTRACT FROM AUTHOR]

In recent years, applications of graph theory to computer software have given fruitful results and attracted more and more attention. A program graph is a graph structural model of a program exhibiting the flow relation or connection among the elements (statements) in the program. One particular aspect of graph analysis which is extremely useful for software is that of partitioning, since it both reduces the complexity of the system and highlights the actual system composition. The purpose of this paper is to review and discuss given approaches to partitioning program graphs. These techniques are best identified by the names of the units into which the program is grouped: segments, DD-paths, intervals, classes, and level-i paths. The objective here is to review these techniques on a fundamental level without exhausting all the uses and users of each approach. [ABSTRACT FROM AUTHOR]

This paper presents the concept of a model of database skeleton which is used to represent user's knowledge on the meaning of the data. The logical database synthesis problem is then formulated as a problem of converting a partially specified database skeleton to a completely specified one, which corresponds to one of several data models. Approaches to optimal logical database synthesis for the relational database are then considered. [ABSTRACT FROM AUTHOR]

This paper treats the problem of fuzzy query translation using the concept of database skeleton. An imprecise, or fuzzy, query is represented by a query graph, which can be analyzed for translatability with respect to a given database skeleton. The fuzzy query translation problem is formulated as a problem of converting a partially specified query graph into a completely specified query graph. This graph is then translated into a sequence of data manipulation commands, such as commands in relational algebra. Approaches to optimal fuzzy query translation are also described. [ABSTRACT FROM AUTHOR]

The conventional axiomatic definitions are given for multiple assignment to simple variables and for assignment to a single subscripted variable, along with examples to illustrate their use. The original contributions of this paper are the extension of the definition to include multiple assignment to several subscripted variables, and the development of a nontrivial, practical algorithm in which multiple assignment to several subscripted variables is indeed useful. Arguments are given to support the conjecture that the use of subscripted variables, like the use of pointers, can lead to exponential explosion of the length of a proof (and thus of the time needed to understand a program) unless the programmer is careful. [ABSTRACT FROM AUTHOR]

This paper is concerned with the need for computer-based tools which help human designers formulate formal process-oriented specifications. It first determines some attributes of a suitable process-oriented specification language, then examines the reasons why specifications would still be difficult to write in such a language in the absence of formulation tools. The key to overcoming these difficulties seems to be the careful introduction of informality based on partial, rather than complete, descriptions and the use of a computer-based tool that uses context extensively to complete these descriptions during the process of constructing a well-formed specification. Some results obtained by a running prototype of such a computer-based tool on a few informal example specifications are presented and, finally, some of the techniques used by this prototype system are discussed. [ABSTRACT FROM AUTHOR]

This paper examines the most widely used reliability models. The models discussed fall into two categories, the data domain and the lime domain. Besides tracing the historical development of the various models their advantages and disadvantages are analyzed. This includes models based on discrete as well as continuous probability distributions. How well a given model performs its purpose in a specific economic environment will determine the usefulness of the model. Each of the models is examined with actual data as to the applicability of the error finding process. [ABSTRACT FROM AUTHOR]

This paper gives timing comparisons for three sorting algorithms written for the CDC STAR computer. One algorithm is Hoare's Quicksort, which is the fastest or nearly the fastest sorting algorithm for most computers. A second algorithm is a vector version of Quick-sort that takes advantage of the STAR's vector operations. The third algorithm is an adaptation of Batcher's sorting algorithm, which makes especially good use of vector operations but has a complexity of N (log N)² as compared to a complexity of N log N for the Quicksort algorithms. In spite of its worse complexity, Batcher's sorting algorithm is competitive with the serial version of Quicksort for vectors up to the largest that can be treated by STAR. Vector Quicksort outperforms the other two algorithms and is generally preferred. These results indicate that unusual instruction sets can introduce biases in program execution time that counter results predicted by worst-case asymptotic complexity analysis. [ABSTRACT FROM AUTHOR]

SDD-1, A System for Distributed Databases, is a distributed database system being developed by Computer Corporation of America (CCA), Cambridge, MA. SDD-1 permits data to be stored redundantly at several database sites in order to enhance the reliability and responsiveness of the system and to facilitate upward scaling of system capacity. This paper describes the method used by SDD-1 for updating data that are stored redundantly. Redundant updating can be costly because it may potentially involve extensive intercomputer communication overhead in order to lock all copies of data being updated. The method described here avoids this overhead by identifying cases in which it is not necessary to perform this global database locking. The identification of transactions that do not require global locking is based on a predefinition of transaction classes performed by the database administrator using an analysis technique described herein. The classes defined are used at run time to decide what level of synchronization is needed for a given transaction. It is important to note that this predefinition activity in no way limits the transactions that the system can accept; it merely permits more efficient execution of those types of transactions that were anticipated. [ABSTRACT FROM AUTHOR]

This paper proposes a measure of program control complexity from an information theory viewpoint. A set of empirical data showing programmer productivity as a function of program control complexity is also presented. The data reveals a step-function-like contour to programmer productivity with increasing program control complexity. [ABSTRACT FROM AUTHOR]

This paper explores the problems of implementing arbitrary forms of process communication on a multiprocessor network. It develops a Concurrent Pascal program that enables distributed processes to communicate on virtual channels. The channels cannot deadlock and will deliver all messages within a finite time. The operation, structure, text, and performance of this program are described. It was written, tested, and described in two weeks and it worked immediately. [ABSTRACT FROM AUTHOR]

Techniques derived from mathematical logic promise to provide an alternative to the conventional methodology for constructing, debugging, and optimizing computer programs. Ultimately, these techniques are intended to lead to the automation of many of the facets of the programming process. This paper provides a unified tutorial exposition of the logical techniques, illustrating each with examples. The strengths and limitations of each technique as a practical programming aid are assessed and attempts to implement these methods in experimental systems are discussed. [ABSTRACT FROM AUTHOR]

Basic error recovery problems between interacting processes are first discussed and the desirability of having separate recovery mechanisms for cooperation and competition is demonstrated. The paper then concentrates on recovery mechanisms for processes competing for the use of the shared resources of a computer system. Appropriate programming language features are developed based on the class and inner features of SIMULA, and on the structuring concepts of recovery blocks and monitors. [ABSTRACT FROM AUTHOR]

In a two-processor distributed computer network, prior research showed that a maximum flow algorithm can be used to find optimal program-module-to-processor assignments to maximize the performance of distributed programs. This paper examines the sequence of optimal assignments found as the load on one processor is held fixed and the load on the other is varied. For every program module M there exists a critical load factor fM such that when the load on the processor with variable load is below fM, M is assigned to that processor by an optimal assignment, and is otherwise assigned to the other processor. This characteristic opens the possibility of doing optimal dynamic assignments in real-time. [ABSTRACT FROM AUTHOR]

This editorial discusses selected papers submitted during the Third International Conference on Software Engineering held in Atlanta, Georgia in May 1978. The international congress, attended by members of the academe and the computer industry, aimed to define the emerging importance of computer software engineering. The first paper refers to how the computer industry provides solutions to everyday challenges with the use of computers. Here, customers express their views on the purpose of computers, leading computer software developers to consider user requirements. The second paper focuses on the activity of design. It discusses a modeling scheme where large programs can be built out of incomplete parts. Design activities are followed by testing, the focus of the third manuscript. A comprehensive study of the two basic approaches to program testing is discussed. The last paper considers programs in operation, the last phase of the computer software development.

User-perceived quality of interactive systems is defined in terms of statistically nonoverlapping categories, so-called dimensions or factors. Categories are identified by factor analysis and represent a dimensional concept of the quality of interactive systems as perceived by its users. Each category describes essential user requirements. This paper reports on a method and some initial results in the analysis of user-perceived quality of interactive systems. It is based on research work described in more detail elsewhere [7]. The methodology of approach is suitable for software requirements definition and human-factors engineering. [ABSTRACT FROM AUTHOR]

This editorial discusses selected articles about software management that appear in the July 1978 issue of "IEEE Transactions on Software Engineering". The manuscript was inspired by a series of seminars on software management organized by the American Institute of Aeronautics and Astronautics which addressed software management from the viewpoint of the U.S. Defense Department. The first paper manifests the theme of the seminar, that is the Department of Defense is launching a major effort to bring the management of software development under better control. Starting with this global view of the problem, the succeeding papers examine software management from the more restrictive viewpoints of the system developer within the framework of a major procurement agency, the program manager responsible for a system containing an embedded computer resource, and finally the system implementer who gambles his system expertise in an attempt to successfully develop a system on schedule and profit.

This paper describes project management methods used for controlling the life cycle of large-scale software systems deployed in multiple installations over a wide geographic area. A set of management milestones is offered along with requirements and techniques for establishing and maintaining control of the project. In particular, a quantitative measure of software quality is proposed based upon functional value, availability, and maintenance costs. Conclusions drawn are based on the study of several cases and are generally applicable to both commercial and military systems. [ABSTRACT FROM AUTHOR]

This paper describes weapon system software life cycle management from a contractor perspective. Four procurement strategies—each requiring two or more contracts—are examined and their impact on the contractor and the software process are described. [ABSTRACT FROM AUTHOR]

Application software development has been an area of organizational effort that has not been amenable to the normal managerial and cost controls. Instances of actual costs of several times the initial budgeted cost, and a time to initial operational capability sometimes twice as long as planned are mote often the case than not. A macromethodology to support management needs has now been developed that will produce accurate estimates of manpower, costs, and times to reach critical milestones of software projects. There are four parameters in the basic system and these are in terms managers are comfortable working with—effort, development time, elapsed time, and a state-of-technology parameter. The system provides managers sufficient information to assess the financial risk and investment value of a new software development project before it is undertaken and provides techniques to update estimates from the actual data stream once the project is underway. Using the technique developed in the paper, adequate analysis for decisions can be made in an hour or two using only a few quick reference tables and a scientific pocket calculator. [ABSTRACT FROM AUTHOR]

This paper presents a constructive approach to the problem of specifying, implementing, and verifying operations that will give concurrent processes exclusive access to a resource. The method eliminates the need for auxiliary variables and establishes the correctness of a whole class of solutions to the same problem. The solutions are derived directly from the specifications using a language construct called guarded regions. Several new solutions to well-known exclusion problems are presented. [ABSTRACT FROM AUTHOR]

A method for formal description of programming principles is presented in this paper. Programming principles, such as sequential search can be defined and proven even in the absence of an application. We represent a principle as a program scheme which has partially interpreted functions in it. The functions must obey certain input constraints. Use of these ideas in program proving is illustrated with examples. [ABSTRACT FROM AUTHOR]

Due to subsequent insertion and deletion, the performance of a file will decline as time goes by. In order to maintain a fast response time at the expense of storage space, a technique commonly known as "within distributed free space" has been developed and used in many access methods. In this paper, a procedure to determine and preallocate the size of "within distributed free space" is presented. The optimal block size for a data storage area, which minimizes the CPU operations and I/O interruptions, is also described. [ABSTRACT FROM AUTHOR]

We computer scientists face at least two problems in promoting the use of computerized data-base systems: 1) some important data might be missing; 2) there might be errors in the data. Both of these problems can be quite serious. If they cannot be solved, it will be quite hard to convince potential users that computerized information systems are useful. In this paper, we shall show that while it is generally impossible to overcome these difficulties entirely, we have succeeded in developing some techniques to overcome these difficulties partially. Using a part of the data, our algorithm detected an error in the book Weyer's Warships of the World 1969. Each of the approximately 2000 warships listed in the book has 18 variables associated with it. It would be difficult for a person to find errors in the book. It is important to point out here that our method does not require any a priori knowledge about the data. For instance, we detected the error in the book Weyer's Warships of the World 1969 without knowing anything about warships. [ABSTRACT FROM AUTHOR]

The critical region construct can be usefully extended by adding region entry conditions and replacing the mutual exclusion restriction by a more general restriction. This paper discusses an extended construct of this nature, and presents an implementation approach based on Dijkstra's secretary process concept, with the code for the secretary process generated automatically during program compilation. This type of implementation can produce efficient solu- lions to many complex synchronization problems. It is also applicable in a wide range of hardware/software environments, including many existing systems. The use of the construct is demonstrated by a number of programming examples. [ABSTRACT FROM AUTHOR]