Search

Observational determinism is a property that ensures the confidentiality in concurrent programs. It conveys that public variables are independent of private variables during the execution of programs, and the scheduling policy of threads. Different definitions for observational determinism have been proposed. On the other hand, observational determinism is not a standard property and it should be checked over two or more executions of a program. The self-composition approach allows comparing two different copies of a program using a single formula. In this paper, we propose a new specification for the observational determinism security property in linear temporal logic. We also present a general method to create the appropriate program model using the self-composition approach. Both the program model and the observational determinism property are encoded in embedded C codes in PROMELA using the SPIN model checker. The paper also discusses a method for the instrumentation of PROMELA code in order to encode the program model for specifying the observational determinism security property. [ABSTRACT FROM AUTHOR]

Design patterns are typically defined imprecisely using natural language descriptions with graphical annotations. It is also common to describe patterns using a concrete design example with implementation details. Several approaches have been proposed to describe design patterns abstractly based on role concepts. However, the notion of role differs in each approach. The behavioral aspects of patterns are not addressed in the role-based approaches. This paper presents a rigorous approach to describe design patterns based on role concepts. Adopting metamodeling and formalism, our work defines an innovative framework where generic pattern concepts based on roles are precisely defined as a formal role metamodel using Object-Z. Individual patterns are specified using these generic role concepts in terms of pattern role models. Temporal behaviors of patterns are also specified using Object-Z and integrated in the pattern role models. Patterns described this way are abstract, separating pattern realization information from the pattern description. They are also precise providing a rigorous foundation for reasoning about pattern properties. This paper also formalizes the properties that must be captured in a class model when a design pattern is deployed. These properties are defined generically in terms of role bindings from a pattern role model to a class model. They provide a precise basis for checking the validity of pattern utilisation in designs. Our work is supported by tools. We have developed an initial role metamodel using an existing modeling framework, Eclipse Modeling Framework (EMF) and have transformed the metamodel to Object-Z using model transformation techniques. Complex constraints are added to the transformed Object-Z model. More importantly, we implement the role metamodel. Using this implementation, pattern authors can develop an initial pattern role model in the same modeling framework and convert the initial model to Object-Z using our transformation rules. The transformed Object-Z model is then enhanced with behavioral features of the pattern. This tool support significantly improves the practicability of applying formalism to design patterns. [ABSTRACT FROM AUTHOR]

This paper presents a systematic approach to matching categories of query language interfaces with the requirements of certain user types. The method is based on a trend model of query language development on the dimensions of functional capabilities and usability. From the trend model the following are derived: a classification scheme for query languages, a criterion hierarchy for query language evaluation, a comprehensive classification scheme of query language users and their requirements, and preliminary recommendations for allocating language classes to user types. The method integrates the results of existing human factors studies and provides a structured framework for future research in this area. Current and expected developments are exemplified by the description of "new generation" database query languages. In a practical query language selection problem, the results of this paper can be used for preselecting suitable query language types; the final selection decision will also depend on organization-specific factors, such as the available database management system, hardware and software strategies, and financial system costs. [ABSTRACT FROM AUTHOR]

Much has been learned in the last decade about concurrent programming. This paper identifies the major concepts of concurrent programming and describes some of the more important language notations for writing concurrent programs. The roles of processes, communication, and synchronization are discussed. Language notations for expressing concurrent execution and for specifying process interaction are surveyed. Synchronization primitives based on shared variables and on message passing are described. Finally, three general classes of concurrent programming languages are identified and compared. Much has been learned in the last decade about concurrent programming. This paper identifies the major concepts of concurrent programming and describes some of the more important language notations for writing concurrent programs. The roles of processes, communication, and synchronization are discussed. Language notations for expressing concurrent execution and for specifying process interaction are surveyed. Synchronization primitives based on shared variables and on message passing are described. Finally, three general classes of concurrent programming languages are identified and compared. [ABSTRACT FROM AUTHOR]

Much research has recently been devoted to "multikey" searching problems. In this paper the particular multikey problem of range searching is investigated and a number of data structures that have been proposed as solutions to this problem are surveyed. The purposes of this paper are to bring together a collection of widely scattered results, to acquaint the reader with the structures currently available for solving the particular problem of range searching, and to display a set of general methods for attacking multikey searching problems. [ABSTRACT FROM AUTHOR]

This paper is an introduction to the main features of ALGOL 68, emphasizing the novel features not found in many other programming languages. The topics, data types (modes), type conversion (coercion), generalized expressions (units), procedures, operators, the standard prelude, and input/output, form the basis of the paper. The approach is informal, relying heavily on many short examples. The paper applies to the Revised Report, published in 1975, rather than to the original report, published in 1969. [ABSTRACT FROM AUTHOR]

This is a tutorial paper on the coordination of parallel activities. It commences with an overview of multiprogrammed operating systems that uncovers an architecture consisting of cooperating, but competing processes working in parallel. This is followed by a formal treatment of processes, and an analysis of the fundamental coordination needs of concomitant processes. The analysis leads to a set of two coordination primitives originally defined by Dijkstra. In the rest of the paper, an evolutionary series of examples of increasing coordination complexity is formulated and solved. As the various examples are discussed, cumulative extensions to the original set of coordination primitives are justified and formally defined. [ABSTRACT FROM AUTHOR]

Time and time again software projects, though undertaken by people of considerable intellectual ability, fail. This will doubtless be a continuing phenomenon, because software production is indeed a difficult task requiring wide-ranging skills. Certainly, no single paper can suddenly solve all the problems of software writing and eliminate the failures. The scope of this paper is limited to four stages in the execution of software projects, namely the planning, coding, testing, and final usage. These four crucial areas contain pitfalls that have been responsible for a large proportion of software failures, and it is hoped this paper will help avoid some of them. [ABSTRACT FROM AUTHOR]

The concept of "process" has come to play a central role in many efforts to master the complexity of large computer systems. The purpose of this paper is to discuss useful methods of structuring complex processes, and to relate these to the problems of improving the quality of large computer systems. Two distinct ways of structuring systems are presented, namely, process combination, and process abstraction; these are then used to discuss such topics as concurrency, synchronization, multiprogramming, interpreters, and programmable processors. This discussion is based on a set of precise definitions for such concepts as "process," "processor," "computation," "combination," and "abstraction." The paper relates these definitions to both current research and practical applications, with particular concern for the problems of the performance, reliability, and modifiability of computer systems. [ABSTRACT FROM AUTHOR]

This paper defines a new variant of program slicing, called specialization slicing, and presents an algorithm for the specialization-slicing problem that creates an optimal output slice. An algorithm for specialization slicing is polyvariant: for a given procedure p, the algorithm may create multiple specialized copies of p. In creating specialized procedures, the algorithm must decide for which patterns of formal parameters a given procedure should be specialized and which program elements should be included in each specialized procedure. We formalize the specialization-slicing problem as a partitioning problem on the elements of the possibly infinite unrolled program. To manipulate possibly infinite sets of program elements, the algorithm makes use of automata-theoretic techniques originally developed in the model-checking community. The algorithm returns a finite answer that is optimal (with respect to a criterion defined in the article). In particular, (i) each element replicated by the specialization-slicing algorithm provides information about specialized patterns of program behavior that are intrinsic to the program, and (ii) the answer is of minimal size (i.e., among all possible answers with property (i), there is no smaller one). The specialization-slicing algorithm provides a newway to create executable slices. Moreover, by combining specialization slicing with forward slicing, we obtain a method for removing unwanted features from a program. While it was previously known how to solve the feature-removal problem for single-procedure programs, it was not known how to solve it for programs with procedure calls. [ABSTRACT FROM AUTHOR]

In the original failure-divergence semantic model for Communicating Sequential Processes (CSP), the incomplete treatment of successful process termination, and in particular parallel termination, permitted unnatural processes to be defined. In response to these problems, a number of different solutions have been proposed by various authors since the original failure-divergence model was developed by Hoare, Brookes and Roscoe. This paper presents an alternative solution to this problem, which is both closer to the original semantic model and provides greater flexibility over the type of parallel termination semantics available in CSP. [ABSTRACT FROM AUTHOR]

SCOOP is a concurrent programming language with a new semantics for contracts that applies equally well in concurrent and sequential contexts. SCOOP eliminates race conditions and atomicity violations by construction. However, it is still vulnerable to deadlocks. In this paper we describe how far contracts can take us in verifying interesting properties of concurrent systems using modular Hoare rules and show how theorem proving methods developed for sequential Eiffel can be extended to the concurrent case. However, some safety and liveness properties depend upon the environment and cannot be proved using the Hoare rules. To deal with such system properties, we outline a SCOOP Virtual Machine (SVM) as a fair transition system. The SVM makes it feasible to use model-checking and theorem proving methods for checking global temporal logic properties of SCOOP programs. The SVM uses the Hoare rules where applicable to reduce the number of steps in a computation. [ABSTRACT FROM AUTHOR]

We describe a variety of methods to compute the functions Kja(x), Lja(x) and their derivatives for real a and positive x. These functions are numerically satisfactory independent solutions of the differential equation x²w" + xw' + (a² - x²)w =0. In the accompanying paper [Gil et al. 2004], we describe the implementation of these methods in Fortran 77 codes. [ABSTRACT FROM AUTHOR]

The need to search for complex and recurring patterns in database sequences is shared by many applications. In this paper, we investigate the design and optimization of a query language capable of expressing and supporting efficiently the search for complex sequential patterns in database systems. Thus, we first introduce SQL-TS, an extension of SQL to express these patterns, and then we study how to optimize the queries for this language. We take the optimal text search algorithm of Knuth, Morris and Pratt, and generalize it to handle complex queries on sequences. Our algorithm exploits the interdependencies between the elements of a pattern to minimize repeated passes over the same data. Experimental results on typical sequence queries, such as double bottom queries, confirm that substantial speedups are achieved by our new optimization techniques. [ABSTRACT FROM AUTHOR]

Java provides a clean object-oriented programming model and allows for inherently system-independent programs. Unfortunately, Java has a limited concurrency model, providing only threads and remote method invocation (RMI). The JR programming language extends Java to provide a rich concurrency model, based on that of SR. JR provides dynamic remote virtual machine creation, dynamic remote object creation, remote method invocation, asynchronous communication, rendezvous, and dynamic process creation. JR's concurrency model stems from the addition of operations (a generalization of procedures) and JR supports the redefinition of operations through inheritance. JR programs are written in an extended Java and then translated into standard Java programs. The JR run-time support system is also written in standard Java. This paper describes the JR programming language and its implementation. Some initial measurements of the performance of the implementation are also included. [ABSTRACT FROM AUTHOR]

Recently the relationship between abstract interpretation and program specialization has received a lot of scrutiny, and the need has been identified to extend program specialization techniques so as to make use of more refined abstract domains and operators. This article clarifies this relationship in the context of logic programming, by expressing program specialization in terms of abstract interpretation. Based on this, a novel specialization framework, along with generic correctness results for computed answers and finite failure under SLD-resolution, is developed. This framework can be used to extend existing logic program specialization methods, such as partial deduction and conjunctive partial deduction, to make use of more refined abstract domains. lEt is also shown how this opens up the way for new optimizations. Finally, as shown in the paper, the framework also enables one to prove correctness of new or existing specialization techniques in a simpler manner. The framework has already been applied in the literature to develop and prove correct specialization algorithms using regular types, which in turn have been applied to the verification of infinite state process algebras. [ABSTRACT FROM AUTHOR]

Methods for mechanically synthesizing concurrent programs from temporal logic specifications obviate the need to manually construct a program and compose a proof of its correctness. A serious drawback of extant synthesis methods, however, is that they produce concurrent programs for models of computation that are often unrealistic. In particular, these methods assume completely fault-free operation, that is, the programs they produce are fault-intolerant. In this paper, we show how to mechanically synthesize fault-tolerant concurrent programs for various fault classes. We illustrate our method by synthesizing fault-tolerant solutions to the mutual exclusion and barrier synchronization problems. [ABSTRACT FROM AUTHOR]

Attribute grammars (AGs) are a formal technique for defining semantics of programming languages. Existing complexity proofs on the circularity problem of AGs are based on automata theory such as writing pushdown acceptor and alternating Turing machines. They reduced the acceptance problems of above automata, which are exponential-time (EXPTIME) complete, to the AG circularity problem. These proofs thus show that the circularity problem is EXPTIME-hard, at least as hard as the most difficult problems in EXPTIME. However, none has shown that the problem is EXPTIME-complete. This paper presents an alternating Turing machine for the circularity problem. The alternating Turing machine requires polynomial space. Thus, the circularity problem is in EXPTIME and is then EXPTIME-complete. [ABSTRACT FROM AUTHOR]

Emerging distributed query-processing systems support flexible execution strategies in which each query can be run using a combination of data shipping and query shipping. As in any distributed environment, these systems can obtain tremendous performance and availability benefits by employing dynamic data caching. When flexible execution and dynamic caching are combined, however, a circular dependency arises: Caching occurs as a by-product of query operator placement, but query operator placement decisions are based on (cached) data location. The practical impact of this dependency is that query optimization decisions that appear valid on a per-query basis can actually cause suboptimal performance for all queries in the long run. To address this problem, we developed Cache In vestment — a novel approach for integrating query optimization and data placement that looks beyond the performance of a single query. Cache Investment sometimes intentionally generates a "suboptimal" plan for a particular query in the interest of effecting a better data placement for subsequent queries. Cache Investment can be integrated into a distributed database system without changing the internals of the query optimizer. In this paper, we propose Cache investment mechanisms and policies and analyze their performance. The analysis uses results from both an implementation on the SHORE storage manager and a detailed simulation model. Our results show that Cache investment can significantly improve the overall performance of a system and demonstrate the trade-offs among various alternative policies. [ABSTRACT FROM AUTHOR]

The query optimizer is one of the most important components of a database system. Most commercial query optimizers today are based on a dynamic-programming algorithm, as proposed in Selinger et al., [1979]. While this algorithm produces good optimization results (i.e., good plans), its high complexity can be prohibitive if complex queries need to be processed, new query execution techniques need to be integrated, or in certain programming environments (e.g., distributed database systems). In this paper, we present and thoroughly evaluate a new class of query optimization algorithms that are based on a principle that we call iterative dynamic programming, or IDP for short. IDP has several important advantages: First, IDP-algorithms produce the best plans of all known algorithms in situations in which dynamic programming is not viable because of its high complexity. Second, some IDP variants are adaptive and produce as good plans as dynamic programming if dynamic programming is viable and as-good-as possible plans as dynamic programming turns out to be not viable. Three, all IDP-algorithms can very easily be integrated into an existing optimizer which is based on dynamic programming. [ABSTRACT FROM AUTHOR]

This article presents letters relate to database management published in the September 1979 issue of the journal "Computing Surveys." The journal received several letters pointing out omissions in the research paper on relational databases published in the September 1979 issue of the journal. This article provides a table similar to that used in the research paper to summarize the status of nine reported systems. One of the letter displays table that outlines nine relational database systems which escaped the survey in the September issue. In the response letter by researcher Won Kim, he explains that one of the nine systems escaped his research. One of the letter is related to MULTICS relational Data Store (MRDS) database management system that became commercially available in 1975. The access method utilized by MRDS is indexed sequentially and augmented with secondary indices. The input language is a relationally complete relational calculus. Input expressions are converted internally.

This paper aims at discussing and classifying the various ways in which the object paradigm is used in concurrent and distributed contexts. We distinguish among the library approach, the integrative approach, and the reflective approach. The library approach applies object-oriented concepts, as they are, to structure concurrent and distributed systems through class libraries. The integrative approach consists of merging concepts such as object and activity, message passing, and transaction, etc. The reflective approach integrates class libraries intimately within an object-based programming language. We discuss and illustrate each of these and point out their complementary levels and goals. [ABSTRACT FROM AUTHOR]

Fringe analysis is a technique used to study the average behavior of search trees. In this paper we survey the main results regarding this technique, and we improve a previous asymptotic theorem. At the same time, we present new developments and applications of the theory that allow improvements in several bounds on the behavior of search trees. Our examples cover binary search trees, AVL-trees, 2-3 trees, and B-trees. [ABSTRACT FROM AUTHOR]

Due to data spreading among processors and due to the cache coherence problem, private data caches have not been as effective in reducing the average memory delay in multiprocessors as in uniprocessors. A wide variety of mechanisms have been proposed for maintaining cache coherence in large-scale shared-memory multiprocessors, making it difficult to compare their performance and implementation implications. To help the computer architect understand some of the trade-offs involved, this paper surveys current cache coherence mechanisms and identifies several issues critical to their design. These design issues include: (1) the coherence detection strategy, through which possibly incoherent memory accesses are detected either statically at compile-time, or dynamically at run-time; (2) the coherence enforcement strategy, such as updating or invalidating, used to ensure that stale cache entries are never referenced by a processor; (3) how the precision of block-sharing information can be changed to trade-off the implementation cost and performance of the coherence mechanism; and (4) how the cache block size affects the performance of the memory system. Trace-driven simulations are used to compare the performance and implementation impacts of these different issues. Additionally, hybrid strategies are presented that can enhance the performance of the multiprocessor memory system by combining several different coherence mechanisms into a single system. [ABSTRACT FROM AUTHOR]

The consensus problem is concerned with the agreement on a system status by the fault-free segment of a processor population in spite of the possible inadvertent or even malicious spread of disinformation by the faulty segment of that population. The resulting protocols are useful throughout fault-tolerant parallel and distributed systems and will impact the design of decision systems to come. This paper surveys research on the consensus problem, compares approaches, outlines applications, and suggests directions for future work. [ABSTRACT FROM AUTHOR]

Computer music is a relatively new field. While a large proportion of the public is aware of computer music in one form or another, there seems to be a need for a better understanding of its capabilities and limitations in terms of synthesis, performance, and recording hardware. This article addresses that need by surveying and discussing the architecture of existing computer music systems. System requirements vary according to what the system will be used for. Common uses for computer music systems include composition, performance, research, home entertainment, and studio recording/mixing. This paper outlines system components with this wide diversity of possible uses in mind. Current synthesis and analysis techniques, and the different way in which these techniques can be implemented in special-purpose hardware, are comprehensively reviewed. Design specifications are given for certain digital-to-analog (and analog-to- digital) converters, disk interfaces, system organization, control hardware and software, and numerical precision. Several synthesis systems are described in detail, with an emphasis on theoretical developments and innovative design. Commerical synthesizers and other architectures are also briefly mentioned. [ABSTRACT FROM AUTHOR]

Although the boundaries of artificial intelligence (AI) remain elusive, computers can now perform musical tasks that were formerly associated exclusively with naturally intelligent musicians. After a historical note, this paper sermonizes on the need for A! techniques in four areas of musical research: composition, performance, music theory, and digital sound processing. The next part surveys recent work involving AI and music. The discussion concentrates on applications in the four areas of research just mentioned. The final part examines how Al techniques of planning and learning could be used to expand the knowledge base and enrich the behavior of musically intelligent systems. [ABSTRACT FROM AUTHOR]

In this paper various techniques for optimizing queries in distributed databases are presented. Although no attempt is made to cover all proposed algorithms on this topic, quite a few ideas extracted from existing algorithms are outlined. It is hoped that large- scale experiments will be conducted to verify the usefulness of these ideas and that they will be integrated to construct a powerful algorithm for distributed query processing. [ABSTRACT FROM AUTHOR]

The implications of adding security mechanisms to high-level network protocols operating in an open-system environment are analyzed. First the threats to security that may arise in such an environment are described, and then a set of goals for communications security measures is established. This is followed by a brief description of the two basic approaches to communications security, link-oriented measures and end-to-end measures, which concludes that end-to-end measures are more appropriate in an open-system environment. Next, relevant properties of data encryption-the fundamental technique on which all communications security mechanisms are based-are discussed. The remainder of the paper describes how end-to-end measures can be used to achieve each of the security goals previously established. [ABSTRACT FROM AUTHOR]

The languages C and PASCAL are growing in popularity, particularly among programmers of small computers. In this paper we summarize and compare the two languages covering their design philosophies, their handling of data types, the programming facilities they provide, the impact of these facilities on the quality of programs, and how useful the facilities are for programming in a variety of application domains. [ABSTRACT FROM AUTHOR]

During the last ten years, many computer networks have been designed, implemented, and put into service in the United States, Canada, Europe, Japan, and elsewhere. From the experience obtained with these networks, certain key design principles have begun to emerge, principles that can be used to design new computer networks in a more structured way than has traditionally been the case. Chief among these principles is the notion of structuring a network as a hierarchy of layers, each one built upon the previous one. This paper is a tutorial about such network hierarchies, using the Reference Model of Open Systems Interconnection developed by the International Organization for Standardization as a guide. Numerous examples are given to illustrate the principles. [ABSTRACT FROM AUTHOR]

This paper examines the current state of knowledge concerning how to increase the novice's understanding of computers and computer programming. In particular, it reviews how advances in cognitive and educational psychology may be applied to problems in teaching nonprogrammers how to use computers. Two major instructional techniques are reviewed: providing a concrete model of the computer and encouraging the learners to actively put technical information into their own words. [ABSTRACT FROM AUTHOR]

Given a set of records with known access probabilities, the problems of record placement, page allocation, and dynamic record placement to minimize read/write head movement for sequential as well as batched processing are discussed. The distance traveled by the head in the systems under consideration is modeled by the rectilinear (L[SUB1]), Euclidean (L[SUB2]), and maximum (L[SUB∞]) metrics. Some open problems are mentioned at the end of the paper. [ABSTRACT FROM AUTHOR]

Most innovations in programming languages and methodology are motivated by a belief that they will improve the performance of the programmers who use them. Although such claims are usually advanced informally, there is a growing body of research which attempts to verify them by controlled observation of programmers' behavior. Surprisingly, these studies have found few clear effects of changes in either programming notation or practice. Less surprisingly, the computing community has paid relatively little attention to these results. This paper reviews the psychological research on programming and argues that its ineffectiveness is the result of both unsophisticated experimental technique and a shallow view of the nature of programming skill. [ABSTRACT FROM AUTHOR]

Database management systems have evolved to the point of general acceptance and wide application; however a major problem still facing the user is the effective utilization of these systems. Important to achieving effective database usability and responsiveness is the design of the database. This paper presents a practical stepwise database design methodology that derives a DBMS-processable database structure from a set of user information and processing requirements. Although the methodology emphasizes the logical design step, the activities of requirements analysis and physical design are also addressed. The methodology is illustrated with a detailed example. Performance trade-offs among multiple users of a single integrated database are considered, and the relationship between short-term design and design for flexibility to changing requirements is discussed. Many steps in the database design process can be assisted with proper use of computer modeling techniques and other tools, such as requirements analysis software. The example design problem and its solution steps serve to point out when and where current technology can be effectively used. [ABSTRACT FROM AUTHOR]

All cryptosystems currently in use are symmetric in the sense that they require the transmitter and receiver to share, in secret, either the same piece of information (key) or one of a pair of related keys easily computed from each other; the key is used in the encryption process to introduce uncertainty to an unauthorized receiver. Not only is an asymmetric encryption system one in which the transmitter and receiver keys are different, but in addition it is computationally infeasible to compute at least one from the other. Asymmetric systems make it possible to authenticate messages whose contents must be revealed to an opponent or allow a transmitter whose key has been compromised to communicate in privacy to a receiver whose key has been kept secret-neither of which is possible using a symmetric cryptosystem. This paper opens with a brief discussion of encryption principles and then proceeds to a comprehensive discussion of the asymmetric encryption/decryption channel and its application in secure communications. [ABSTRACT FROM AUTHOR]

Database reorganization can be defined as changing some aspect of the way in which a database is arranged logically and/or physically. An example is changing from a one-to-one to a one-to-many relationship. Reorganization is a necessary function in a database system. This paper introduces the basic concepts of reorganization, including why it is performed. Many types of reorganization are described and classified into logical/physical levels. Then pragmatic issues such as reorganization strategies, a survey of several commercial reorganization facilities, case studies, and database administration considerations are covered. Finally, several research efforts are surveyed. [ABSTRACT FROM AUTHOR]

This paper first surveys all the relational database systems which have been reported, highlighting their most noteworthy features and concepts. It then surveys and classifies proposals for implementing each of the requisite functional components of a hypothetical, comprehensive relational database system. It concludes with some general observations about user responses to relational systems. [ABSTRACT FROM AUTHOR]

B-trees have become, de facto, a standard for file organization. File indexes of users, dedicated database systems, and general-purpose access methods have all been proposed and implemented using B-trees. This paper reviews B-trees and shows why they have been so successful. It discusses the major variations of the B-tree, especially the W-tree, contrasting the relative merits and costs of each implementation. It illustrates a general purpose access method which uses a B-tree. [ABSTRACT FROM AUTHOR]

Over the last decade, the Petri net has gained increased usage and acceptance as a basic model of systems of asynchronous concurrent computation. This paper surveys the basic concepts and uses of Petri nets. The structure of Petri nets, their markings and execution, several examples of Petri net models of computer hardware and software, and research into the analysis of Petri nets are presented, as are the use of the reachability tree and the decidability and complexity of some Petri net problems. Petri net languages, models of computation related to Petri nets, and some extensions and subclasses of the Petri net model are also briefly discussed. [ABSTRACT FROM AUTHOR]

Pipelined computer architecture has received considerable attention since the 1960s when the need for faster and more cost-effective systems became critical. The merit of pipelining is that it can help to match the speeds of various subsystems without duplicating the cost of the entire system involved. As technology evolves, faster and cheaper LSI circuits become available, and the future of pipelining, either in a simple or complex form, becomes more promising. This paper reviews the many theoretical considerations and problems behind pipelining, surveying and comparing various representative pipeline machines that operate in either sequential or vector pipeline mode, the practical solutions adopted, and the tradeoffs involved. The performance of a simple pipe, the physical speed limitation, and the control structures for penalty-incurring events are analyzed separately. The problems faced by the system designers are tackled, including buffering, busing structure branching, and interrupt handling. Aspects of sequential and vector processing are studied. Fundamental advantages of vector processing are unveiled, and additional requirements (costs) are discussed to establish a criterion for the tradeoff between sequential and vector pipeline processing. Finally, two recent machines (the CRAY-1 and the Amdahl 470 V/6 systems) are presented to demonstrate how complex pipeline techniques can be used and how simple but advantageous pipeline concepts can be exploited. [ABSTRACT FROM AUTHOR]

This paper is a survey of parallel machine organizations and programming. Parallelism is defined in a broad sense, on the bit level, operation level, and algorithm level. A number of abstract and practical questions are discussed. First, fast techniques for evaluating arithmetic expressions and linear recurrences are treated. Next, whole programs are discussed, and some experimental results are presented. Finally, various aspects of machine organization are discussed, including processors, memories, and alignment networks. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to describe the concepts, definitions, and ideas of computer architecture and to suggest that architecture can be viewed as composed of three components: physical organization; control and flow of information; and representation, interpretation and transformation of information. This framework can accommodate diverse architectural concepts such as array processing, microprogramming, stack processing and tagged architecture. Architectures of some existing machines are considered and methods of associating architectural concepts with the components are established. Architecture design problems and trade-offs are discussed in terms of the proposed framework. [ABSTRACT FROM AUTHOR]

This paper is a tutorial on the methods used to control the transmission of digital information on data communication links. Simple models of data communication systems are introduced and terminology for describing their functions and operation is established. Various graphical methods of representing communication control procedures are discussed and used to describe significant features of communication control procedures in detail. [ABSTRACT FROM AUTHOR]

The bibliography appearing at the end of this article lists 37 sorting algorithms and 100 books and papers on sorting published in the last 20 years. The basic ideas presented here have been abstracted from this body of work, and the best algorithms known are given as examples. As the algorithms are explained, references to related algorithms and mathematical or experimental analyses are given. Suggestions are then made for choosing the algorithm best suited to a given situation. [ABSTRACT FROM AUTHOR]

This is a tutorial paper describing the construction of a basic simulation model for a disk-based multiprogrammed computer system. First, the job processing sequence of the system to be simulated is described and techniques for generating the simulated job mix are discussed. The structure of simulation models, events, and events scheduled are then introduced. A simulation model for the multiprogrammed system is presented and the event routines comprising the model are discussed. The use of GPSS, SIMSCRIPT, and FORTRAN in constructing a simulation model is reviewed. [ABSTRACT FROM AUTHOR]

The article focuses on the papers published in the March 1983 issue of the periodical, "acm computing surveys." The papers in this issue describe the details of a level of abstraction. The concept of levels of abstraction is integral to work in system str

This article introduces a series of articles related to three areas of computer research published in the December 1981 issue of the journal "ACM Computing Surveys." Narendra Ahuja and Bruce Schacter provide a survey of image models, focusing on the low-level techniques used in such applications as image restoration or texture analysis and synthesis. They classify image models as being either pixel based or region based. In pixel-based modeling, pixels or picture points are the structural primitives; in region-based models, sets of subpatterns for small neighborhoods larger than a single pixel, along with rules for placing subpatterns, serve as the structural primitives. One approach to high-level image modeling incorporates three-dimensional spatial data representations. The paper by a Sargur Srihari is a tutorial on such models, emphasizing techniques applicable to the representation of images as collections of volume elements or voxels. The paper by Edward Frank and Robert Sproull deals with the steps in integrated circuit design and fabrication whereby the circuit is tested and, if found to be incorrect, debugged.

This article presents information about December 1, 1980 issue of the periodical "ACM Computing Surveys." The five papers in this issue are primarily mathematical in nature. They provide theoretical treatments of the description, of programming languages, of efficient techniques for implementing and carrying out various algorithms, and of the representation of rigid solid objects. By probabilistic languages software developer C.S. Wetherell means the attachment of probabilistic information into the context free grammar describing a programming language. This is done in order to have a mathematical formulation of the statistical information available from that language. The intention of Wetherell's paper is, first, to describe the notion of probabilisitic context free grammars and, second, to discuss some of their applications in order to emphasize their value in programming language studies. Following a brief overview of context free languages, the author examines methods for adding probabilities to the grammar of a language in order to attach probabilities to strings of that language.