bluuebunny/crossref_metadata_2025 huggingface dataset:
Computing similarity in a reuse library system
Authors: Ostertag Eduardo , Hendler James , Díaz Rubén Prieto , Braun Christine
Published: July 2002

This paper presents an AI based library system for software reuse, called AIRS, that allows a developer to browse a software library in search of components that best meet some stated requirement. A
component
is described by a set of (
feature, term
) pairs. A feature represents a classification criterion, and is defined by a set of related terms. The system allows to represent
packages
(logical units that group a set of components) which are also described in terms of features. Candidate reuse components and packages are selected from the library based on the degree of similarity between their descriptions and a given target description. Similarity is quantified by a nonnegative magnitude (
distance
) proportional to the effort required to obtain the target given a candidate. Distances are computed by
comparator
functions based on the
subsumption, closeness,
and
package
relations. We present a formalization of the concepts on which the AIRS system is based. The functionality of a prototype implementation of the AIRS system is illustrated by application to two different software libraries: a set of Ada packages for data structure manipulation, and a set of C components for use in Command, Control, and Information Systems. Finally, we discuss some of the ideas we are currently exploring to automate the construction of AIRS classification libraries.
Real zero isolation for trigonometric polynomials
Authors: Schweikard Achim
Published: July 2002

An exact and practical method for determining the number, location, and multiplicity of all real zeros of the trigonometric polynomials is described. All computations can be performed without loss of accuracy. lThe method is based on zero isolation techniques for algebraic polynomials. An efficient method for the calculation of the coefficients of a corresponding algebraic polynomial is stated. The complexity of trigonometric zero isolation depending on the degree and the coefficient size of the given trigonometric polynomial is analyzed. In an experimental evaluation, the performance of the method is compared to the performance of recently developed numeric techniques for the approximate determination of all roots of trigonometric polynomials. The case of exponential or hyperbolic polynomials is treated in an appendix.
The model, language, and implementation of an object-oriented multimedia knowledge base management system
Authors: Ishikawa Hiroshi , Suzuki Fumio , Kozakura Fumihiko , Makinouchi Akifumi , Miyagishima Mika , Izumida Yoshio , Aoshima Masaaki , Yamane Yasuo
Published: July 2002

New applications such as CAD, AI, and hypermedia require direct representation and flexible use of complex objects, behavioral knowledge, and multimedia data. To this end, we have devised a knowledge base management system called Jasmine. An object-oriented approach in a programming language also seems promising for use in Jasmine. Jasmine extends the current object-oriented approach and provides the following features. Our object model is based on functional data models and well-established set theory. Attributes or functions composing objects can represent both structural and behavioral knowledge. The object model can represent incomplete and generic knowledge. The model can support the basic storage and operations of multimedia data. The facets of attributes can flexibly represent constraints and triggers. The object manipulation language can support associative access of objects. The structural and behavioral knowledge can be uniformly treated to allow the user to specify complex object operations in a compact manner. The user-defined and system-defined attributes can be uniformly specified to ease user customization of the language. The classes and instances can be uniformly accessed. Incomplete knowledge can be flexibly accessed. The system has a layered architecture. Objects are stored in nested relations provided by extensive DBMS as a sublayer. User query of objects is compiled into relational operations such as select and join, which can be efficiently processed using hashing. The behavioral knowledge is compiled into predicate and manipulation function interfaces that can directly access tuples in a buffer.—
Authors' Abstract
Optimization of array subscript range checks
Authors: Asuru Jonathan M.
Published: July 2002

Compile-time elimination of subscript range checks is performed by some optimizing compilers to reduce the overhead associated with manipulating array data structures. Elimination and propagation, the two methods of subscript range check optimization, are less effective for eliminating global redundancies especially in while-loop structures with nonconstant loop guards. This paper describes a subscript range check optimization procedure that can eliminate more range checks than current methods. Two transformations called inner-loop guard elimination and conservative expression substitution are introduced to enhance propagation of range checks in nested while-loops and to define a partial order on related range checks. Global elimination is improved by considering range checks performed before control reaches a statement and after control leaves a statement. A unique feature of this method is the simplification of the available range-check analysis system for global elimination.
Access normalization
Authors: Li Wei , Pingali Keshav
Published: July 2002

In scalable parallel machines, processors can make local memory accesses much faster than they can make remote memory accesses. Additionally, when a number of remote accesses must be made, it is usually more efficient to use block transfers of data rather than to use many small messages. To run well on such machines, software must exploit these features. We believe it is too onerous for a programmer to do this by hand, so we have been exploring the use of restructuring compiler technology for this purpose. In this article, we start with a language like HPF-Fortran with user-specified data distribution and develop a systematic loop transformation strategy called
access normalization
that restructures loop nests to exploit locality and block transfers. We demonstrate the power of our techniques using routines from the BLAS (Basic Linear Algebra Subprograms) library. An important feature of our approach is that we model loop transformation using
invertible
matrices and integer lattice theory.
Bounded relative error in estimating transient measures of highly dependable non-Markovian systems
Authors: Heidelberger Philip , Shahabuddin Perwez , Nicola Victor F.
Published: July 2002

This article deals with fast simulation techniques for estimating transient measures in highly dependable systems. The systems we consider of components with generally distributed lifetimes and repair times, with complex interaction among components. As is well known, standard simulation of highly dependable systems is very inefficient, and importance-sampling is widely used to improve efficiency. We present two new techniques, one of which is based on the uniformization approach to simulation, and the other is a natural extension of the uniformization approach which we call exponential transformation. We show that under certain assumptions, these techniques have the bounded relative error property, i.e., the relative error of the simulation estimate remains bounded as components become more and more reliable, unlike standard simulation in which it tends to infinity. This implies that only a fixed number of observations are required to achieve a given relative error, no matter how rare the failure events are.
Set-associative cache simulation using generalized binomial trees
Authors: Sugumar Rabin A. , Abraham Santosh G.
Published: July 2002

Set-associative caches are widely used in CPU memory hierarchies, I/O subsystems, and file systems to reduce average access times. This article proposes an efficient simulation technique for simulating a group of set-associative caches in a single pass through the address trace, where all caches have the same line size but varying associativities and varying number of sets. The article also introduces a generalization of the ordinary binomial tree and presents a representation of caches in this class using the Generalized Binomial Tree (gbt). The tree representation permits efficient search and update of the caches. Theoretically, the new algorithm, GBF_LS, based on the gbt structure, always takes fewer comparisons than the two earlier algorithms for the same class of caches: all-associativity and generalized forest simulation. Experimentally, the new algorithm shows performance gains in the range of 1.2 to 3.8 over the earlier algorithms on address traces of the SPEC benchmarks. A related algorithm for simulating multiple alternative direct-mapped caches with fixed cache size, but varying line size, is also presented.
ATM virtual private networks
Authors: Fotedar Shivi , Gerla Mario , Crocetti Paola , Fratta Luigi
Published: July 2002

Asynchronous transfer mode (ATM) networks are aimed at supporting a variety of services, including voice, video and data, while allowing the users to efficiently share network resources. Efficiency and flexibility in managing the resources are essential to meet the different quality requirements of these services. Network resources include trunk bandwidth, switching capacity, and buffer space in the ATM cross-connects. Sharing these resources is a complex task, since different applications have different traffic characteristic and quality of service (QOS) requirements. For example, video is characterized by continuous bit rate (CBR) or variable bit rate (VBR) traffic, while voice and data are bursty in nature. The quality requirements also depend on the type of service under considerations—some services, like video and voice, have strict end-to-end delay requirements, whereas others may be carried on a best-effort basis.
Chiron-1
Authors: Taylor Richard N. , Nies Kari A. , Bolcer Gregory Alan , MacFarlane Craig A. , Anderson Kenneth M. , Johnson Gregory F.
Published: July 2002

The Chiron-1 user interface system demonstrates key techniques that enable a strict separation of an application from its user interface. These techniques include separating the control-flow aspects of the application and user interface: they are concurrent and may contain many threads. Chiron also separates windowing and look-and-feel issues from dialogue and abstract presentation decisions via mechanisms employing a client-server architecture. To separate application code from user interface code, user interface agents called
artists
are attached to instances of application abstract data types (ADTs). Operations on ADTs within the application implicitly trigger user interface activities within the artists. Multiple artists can be attached to ADTs, providing multiple views and alternative forms of access and manipulation by either a single user or by multiple users. Each artist and the application run in separate threads of control. Artists maintain the user interface by making remote calls to an abstract depiction hierarchy in the Chiron server, insulting the user interface code from the specifics of particular windowing systems and toolkits. The Chiron server and clients execute in separate processes. The client-server architecture also supports multilingual systems: mechanisms are demonstrated that support clients written in programming languages other than that of the server while nevertheless supporting object-oriented server concepts. The system has been used in several universities and research and development projects. It is available by anonymous ftp.
Fault-tolerance in air traffic control systems
Authors: Cristian Flaviu , Dancey Bob , Dehn Jon
Published: July 2002

The distributed real-time system services developed by Lockheed Martin's Air Traffic Management group serve the infrastructure for a number of air traffic control systems. Either completed development or under development are the US Federal Aviation Administration's Display System Replacement (DSR) system, the UK Civil Aviation Authority's New Enroute Center (NERC) system, and the Republic of China's Air Traffic Control Automated System (ATCAS). These systems are intended to replace present en route systems over the next decade. High availability of air traffic control services is an essential requirement of these systems. This article discusses the general approach to fault-tolerance adopted in this infrastructure, by reviewing some of the questions which were asked during the system design, various alternative solutions considered, and the reasons for the design choices made. The aspects of this infrastructure chosen for the individual ATC systems mentioned above, along with the status of those systems, are presented in the Section 11 of the article.
Remark on “Fast floating-point processing in Common Lisp”
Authors: Reid J. K.
Published: July 2002

We explain why we feel that the comparison betwen Common Lisp and Fortran in a recent article by Fateman et al. in this journal is not entirely fair.
An evolutionary approach to constructing effective software reuse repositories
Authors: Henninger Scott
Published: July 2002

Repositories for software reuse are faced with two interrelated problems: (1) acquiring the knowledge to initially construct the repository and (2) modifying the repository to meet the evolving and dynamic needs of software development organizations. Current software repository methods rely heavily on classification, which exacerbates acquistition and evolution problems by requiring costly classification and domain analysis efforts before a repository can be used effectively, This article outlines an approach that avoids these problems by choosing a retrieval method that utilizes minimal repository structure to effectively support the process of finding software conponents. The approach is demonstrated through a pair of proof-of-concept prototypes: PEEL, a tool to semiautomatically identify reusable components, and CodeFinder, a retrieval system that compensates for the lack of explicit knowledge structures through a spreading activation retrieval process. CodeFinder also allows component representations to be modified while users are searching for information. This mechanism adapts to the changing nature of the information in the repository and incrementally improves the repository while people use it. The combination of these techniques holds potential for designing software repositories that minimize up-front costs, effectively support the search process, and evolve with an organization's changing needs.
Contention in shared memory algorithms
Authors: Dwork Cynthia , Herlihy Maurice , Waarts Orli
Published: July 2002

Most complexity measures for concurrent algorithms for asynchronous shared-memory architectures focus on process steps and memory consumption. In practice, however, performance of multiprocessor algorithms is heavily influenced bycontention, the extent to which processess access the same location at the same time. Nevertheless, even though contention is one of the principal considerations affecting the performance of real algorithms on real multiprocessors, there are no formal tools for analyzing the contention of asynchronous shared-memory algorithms.

This paper introduces the first formal complexity model for contention in shared-memory multiprocessors. We focus on the standard multiprocessor architecture in whichnasynchronous processes communicate by applyingread, write,andread-modify-writeoperations to a shared memory. To illustrate the utility of our model, we use it to derive two kinds of results: (1) lower bounds on contention for well-known basic problems such as agreement and mutual exclusion, and (2) trade-offs between the length of the critical path (maximal number of accesses to shared variables performed by a single process in executing the algorithm) and contention for these algorithms. Furthermore, we give the first formal contention analysis of a variety of counting networks, a class of concurrent data structures inplementing shared counters. Experiments indicate that certain counting networks outperform conventional single-variable counters at high levels of contention. Our analysis provides the first formal model explaining this phenomenon.
Compiler blockability of dense matrix factorizations
Authors: Carr Steve , Lehoucq R. B.
Published: July 2002

The goal of the LAPACK project is to provide efficient and portable software for dense numerical linear algebra computations. By recasting many of the fundamental dense matrix computations in terms of calls to an efficient implementation of the BLAS (Basic Linear Algebra Subprograms), the LAPACK project has, in large part, achieved its goal. Unfortunately, the efficient implementation of the BLAS results often in machine-specific code that is not portable across multiple architectures without a significant loss in performance or a significant effort to reoptimize them. This article examines wheter most of the hand optimizations performed on matrix factorization codes are unnecessary because they can (and should) be performed by the compiler. We believe that it is better for the programmer to express algorithms in a machine-independent form and allow the compiler to handle the machine-dependent details. This gives the algorithms portability across architectures and removes the error-prone, expensive and tedious process of hand optimization. Although there currently exist no production compilers that can perform all the loop transformations discussed in this article, a description of current research in compiler technology is provided that will prove beneficial to the numerical linear algebra community. We show that the Cholesky and optimized automaticlaly by a compiler to be as efficient as the same hand-optimized version found in LAPACK. We also show that the QR factorization may be optimized by the compiler to perform comparably with the hand-optimized LAPACK version on modest matrix sizes. Our approach allows us to conclude that with the advent of the compiler optimizations dicussed in this article, matrix factorizations may be efficiently implemented in a BLAS-less form
Algorithm 779: Fermi-Dirac functions of order -1/2, 1/2, 3/2, 5/2
Authors: MacLeod Allan J.
Published: July 2002

The computation of Fermi-Dirac integrals *** is discussed for the values *** = -1, 1/2, 3/2, 5/2. We derive Chebyshev polynomial expansions which allow the computation of these functions to double precision IEEE accuracy.
Collaborative conceptual schema design
Authors: Ram Sudha , Ramesh V.
Published: July 2002

Recent years have seen an increased interest in providing support for collaborative activities among groups of users participating in various information systems design tasks such as, requirements determination and process modeling. However, little attention has been paid to the collaborative conceptual database design process. In this article, we develop a model of the collaborative conceptual schema development process and describe the design and implementation of a graphical multiuser conceptual schema design tool that is based on the model. The system we describe allows a group of users to work collaboratively on the creation of database schemas in synchronous (same-time) mode (either in a face-to-face or distributed setting). Extensive modeling support is provided to assist users in creating semantically correct conceptual schemas. The system also provides users with several graphical facilities such as, a large drawing workspace with the ability to scroll or “jump” to any portion of this workspace, zooming capabilities, and the ability to move object(s) to any portion of the workspace. The unique component of the system, however, is its built-in support for collaborative schema design. The system supports a relaxed WYSIWIS environment, i.e., each user can control the graphical layout of the same set of schema objects. The system ensures that changes/additions made by any user are consistent. Any conflicts that may compromise to the integrity of the shared schema are flagged and resolved by the system. The results from a preliminary experiment suggest that the use of our system in a collaborative mode improved information sharing among users, minimized conflicts, and led to a more comprehensive schema definition.
Eliciting software process models with theE3language
Authors: Jaccheri Maria Letizia , Picco Gian Pietro , Lago Patricia
Published: July 2002

Software processes are complex entities that demand careful understand ing and improvement as they determine the quality of the resulting product. A necessary step toward the improvement of an organization's process is a clear description of the entities involved and of their mutual relationships. Process modelelicitationaims at constructing this description under the shape of a software process model. The model is constructed by gathering, from several sources, process information which is often incomplete, inconsistent, and ambiguous. A process modeling language can be used to represent the model being elicited. However, elicitation requires process models to be understandable and well structured. These requirements are often not satisfied by available process modeling languages becuase of their bias toward process enaction rather than process description. This article presents a process modeling language and a support tool which are conceived especially for process model elicitation. TheE3language is an object-oriented modeling language with a graphical notation. InE3, associations are a means to express constraints and facilitate reuse. TheE3p-draw tool supports the creation and management ofE3models and provides a view mechanism that enables inspection of models according to different perspectives.
From formal models to formally based methods
Authors: Ciapessoni Emanuele , Mirandola Piergiorgio , Coen-Porisini Alberto , Mandrioli Dino , Morzenti Angelo
Published: July 2002

We address the problem of increasing the impact of formal methods in the practice of industrial computer applications. We summarize the reasons why formal methods so far did not gain widespead use within the industrial environment despite several promising experiences. We suggest an evolutionary rather than revolutionary attitude in the introduction of formal methods in the practice of industrial applications, and we report on our long-standing experience which involves an academic institution. Politecnico di Milano, two main industrial partners, ENEL and CISE, and occasionally a few other industries. Our approach aims at augmenting an existing and fairly deeply rooted informal industrial methodology with our original formalism, the logic specification language TRIO. On the basis of the experiences we gained we argue that our incremental attitude toward the introduction of formal methods within the industry could be effective largely independently from the chosen formalism.
Remark on Algorithm 702—the updated truncated Newton minimization package
Authors: Xie Dexuan , Schlick Tamar
Published: July 2002

A truncated Newton minimization package, TNPACK, was described in ACM
Transactions on Mathematical Software 14
, 1 (Mar. 1992), pp.46–111. Modifications to enhance performance, especially for large-scale minimization of molecular potential functions, are described here. They involve three program segments of TNPACK: negative curvature test, modified Cholesky factorization, and line-search stopping rule.
Flexible control of downloaded executable content
Authors: Jaeger Trent , Prakash Atul , Liedtke Jochen , Islam Nayeem
Published: July 2002

We present a security architecture that enables system and application a ccess control requirements to be enforced on applications composed from downloaded executable content. Downloaded executable content consists of messages downloaded from remote hosts that contain executables that run, upon receipt, on the downloading principal's machine. Unless restricted, this content can perform malicious actions, including accessing its downloading principal's private data and sending messages on this principal's behalf. Current security architectures for controlling downloaded executable content (e.g., JDK 1.2) enable specification of access control requirements for content based on its provider and identity. Since these access control requirements must cover every legal use of the class, they may include rights that are not necessary for a particular application of content. Therefore, using these systems, an application composed from downloaded executable content cannot enforce its access control requirements without the addition of application-specific security mechanisms. In this paper, we define an access control model with the following properties: (1) system administrators can define system access control requirements on applications and (2) application developers can use the same model to enforce application access control requirements without the need for ad hoc security mechanisms. This access control model uses features of role-based access control models to enable (1) specification of a single role that applies to multiple application instances; (2) selection of a content's access rights based on the content's application and role in the application; (3) consistency maintained between application state and content access rights; and (4) control of role administration. We detail a system architecture that uses this access control model to implement secure collaborative applications. Lastly, we describe an implementation of this architecture, called the Lava security architecture.
Support for repetitive transactions and ad hoc queries in System R
Authors: Chamberlin D. D. , Astrahan M. M. , King W. F. , Lorie R. A. , Mehl J. W. , Price T. G. , Schkolnick M. , Griffiths Selinger P. , Slutz D. R. , Wade B. W. , Yost R. A.
Published: July 2002

System R supports a high-level relational user language called SQL which may be used by ad hoc users at terminals or as an embedded data sublanguage in PL/I or COBOL. Host-language programs with embedded SQL statements are processed by the System R precompiler which replaces the SQL statements by calls to a machine-language access module. The precompilation approach removes much of the work of parsing, name binding, and access path selection from the path of a running program, enabling highly efficient support for repetitive transactions. Ad hoc queries are processed by a similar approach of name binding and access path selection which takes place on-line when the query is specified. By providing a flexible spectrum of binding times, System R permits transaction-oriented programs and ad hoc query users to share a database without loss of efficiency.

System R is an experimental database management system designed and built by members of the IBM San Jose Research Laboratory as part of a research program on the relational model of data. This paper describes the architecture of System R, and gives some preliminary measurements of system performance in both the ad hoc query and the “canned program” environments.
Partial-match hash coding
Authors: Burkhard Walter A.
Published: July 2002

File designs suitable for retrieval from a file of
k
-field records when queries may be partially specified are examined. Storage redundancy is introduced to obtain improved worst-case and average-case performances. The resulting storage schemes are appropriate for replicated distributed database environments; it is possible to improve the overall average and worst-case behavior for query response as well as provide an environment with very high reliability. Within practical systems it will be possible to improve the query response time performance as well as reliability over comparable systems without replication.
Design of a balanced multiple-valued file-organization scheme with the least redundancy
Authors: Yamamoto Sumiyasu , Tazawa Shinsei , Ushio Kazuhiko , Ikeda Hideto
Published: July 2002

A new balanced file-organization scheme of order two for multiple-valued records is presented. This scheme is called HUBMFS
2
(Hiroshima University Balanced Multiple-valued File-organization Scheme of order two). It is assumed that records are characterized by
m
attributes having
n
possible values each, and the query set consists of queries which specify values of two attributes. It is shown that the redundancy of the bucket (the probability of storing a record in the bucket) is minimized if and only if the structure of the bucket is a partite-claw. A necessary and sufficient condition for the existence of an HUBMFS
2
, which is composed exclusively of partite-claw buckets, is given. A construction algorithm is also given. The proposed HUBMFS
2
is superior to existing BMFS
2
(Balanced Multiple-valued File-organization Schemes of order two) in that it has the least redundancy among all possible BMFS
2
's having the same parameters and that it can be constructed for a less restrictive set of parameters.
Batched searching of sequential and tree structured files
Authors: Shneiderman Ben
Published: July 2002

The technique of batching searches has been ignored in the context of disk based online data retrieval systems. This paper suggests that batching be reconsidered for such systems since the potential reduction in processor demand may actually reduce response time. An analysis with sample numerical results and algorithms is presented.
Performance evaluation of a relational associative processor
Authors: Ozkarahan E. A. , Schuster S. A. , Sevcik K. C.
Published: July 2002

An associative processor called RAP has been designed to provide hardware support for the use and manipulation of databases. RAP is particularly suited for supporting relational databases. In this paper, the relational operations provided by the RAP hardware are described, and a representative approach to providing the same relational operations with conventional software and hardware is devised. Analytic models are constructed for RAP and the conventional system. The execution times of several of the operations are shown to be vastly improved with RAP for large relations.
On Asymptotic Estimates in Switching and Automata Theory
Authors: Harrison Michael A.
Published: July 2002

Formulas and algorithms have recently been given for calculating the number of symmetry types of functions, networks and automata under various transformation groups. In almost all cases, the computations involved are quite difficult and require the use of a digital computer. In this paper, asymptotic estimates are given for these numbers, which are trivial to compute and which are very accurate in most cases even for small values of the parameters.
Modeling generalized cylinders via Fourier morphing
Authors: Aguado Alberto S. , Montiel Eugenia , Zaluska Ed
Published: July 2002

Generalized cylinders provide a compact representation for modeling many components of natural objects as well as a great variety of human-made industrial parts. This paper presents a new approach to modeling generalized cylinders based on cross-sectional curves defined using Fourier descriptors. This modeling is based on contour interpolation and is implemented using a subdivision technique. The definition of generalized cylinders uses a three-dimensional trajectory which provides an adequate control for the smoothness of bend with a small number of parameters and includes the orientation of each cross-section (i.e, the local coordinate system) in the interpolation framework. Fourier representations of cross-sectional curves are obtained from contours in digital images, and

corresponding points are identified by considering angular and arc-length parametrizations. Changes in cross-section shape through the trajectory are performed using Fourier morphing. The technique proposed provides a comprehensive definition that allows the modeling of a wide variety of shapes, while maintaining a compact characterization to facilitate the description of shapes and displays.
Designing a Portable Natural Language Database Query System
Authors: Kaplan S. Jerrold
Published: July 2002

One barrier to the acceptance of natural language database query systems is the substantial installation effort required for each new database. Much of this effort involves the encoding of semantic knowledge for the domain of discourse, necessary to correctly interpret and respond to natural language questions. For such systems to be practical, techniques must be developed to increase their portability to new domains.

This paper discusses several issues involving the portability of natural language interfaces to database systems, and presents the approach taken in
CO-OP
— a natural language database query system that provides cooperative responses to English questions and operates with a typical CODA-SYL database system.
CO-OP
derives its domain-specific knowledge from a
lexicon
(the list of words known to the system) and the information already present in the structure and content of the underlying database. Experience with the implementation suggests that strategies that are not directly derivative of cognitive or linguistic models may nonetheless play an important role in the development of practical natural language systems.
Building tractable disjunctive constraints
Authors: Cohen David , Jeavons Peter , Jonsson Peter , Koubarakis Manolis
Published: July 2002

Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified.
Algorithm 428: Hu-Tucker minimum redundancy alphabetic coding method [Z]
Authors: Yohe J. M.
Published: July 2002

This algorithm implements the Hu-Tucker method of variable length, minimum redundancy alphabetic binary encoding [1]. The symbols of the alphabet are considered to be an ordered forest of
n
terminal nodes. Two nodes in an ordered forest are said to be tentative-connecting if the sequence of nodes between the two given nodes is either empty or consists entirely of nonterminal nodes.
A learning program which plays partnership dominoes
Authors: Smith Michael H.
Published: July 2002

A learning program has been written in BASIC to play four-player partnership dominoes. Because dominoes is a game of incomplete information, the program uses somewhat different principles of artificial intelligence from those used in programs for games of complete information, such as checkers, chess, and go. The program was constructed to use a “strategy signature table” which classifies board situations through the interactions of game parameters. Each entry in the table contains adaptively determined weights indicating the advisability of various strategies. Once chosen, a strategy then employs probability analysis and linear polynomial evaluation to choose a move. Our program wins approximately two-thirds of its games in tournament situations, and has defeated championship players.
An axiomatic basis for computer programming
Authors: Hoare C. A. R.
Published: July 2002

In this paper an attempt is made to explore the logical foundations of computer programming by use of techniques which were first applied in the study of geometry and have later been extended to other branches of mathematics. This involves the elucidation of sets of axioms and rules of inference which can be used in proofs of the properties of computer programs. Examples are given of such axioms and rules, and a formal proof of a simple theorem is displayed. Finally, it is argued that important advantages, both theoretical and practical, may follow from a pursuance of these topics.
Long term file migration: development and evaluation of algorithms
Authors: Smith Alan Jay
Published: July 2002

The steady increase in the power and complexity of modern computer systems has encouraged the implementation of automatic file migration systems which move files dynamically between mass storage devices and disk in response to user reference patterns. Using information describing 13 months of user disk data set file references, we develop and evaluate (replacement) algorithms for the selection of files to be moved from disk to mass storage. Our approach is general and demonstrates a general methodology for this type of problem. We find that algorithms based on both the file size and the time since the file was last used work well. The best realizable algorithms tested condition on the empirical distribution of the times between file references. Acceptable results are also obtained by selecting for replacement that file whose size times time to most recent reference is maximal. Comparisons are made with a number of standard algorithms developed for paging, such as Working Set, VMIN, and GOPT. Sufficient information (parameter values, fitted equations) is provided so that our algorithms may be easily implemented on other systems.
Production and employment of Ph.D.'s in computer science—1977 and 1978
Authors: Taulbee Orrin E. , Conte S. D.
Published: July 2002

This brief report summarizes the results of the third and fourth annual surveys on the production and employment of Ph.D.'s in computer science. Responses were solicited from department chairmen, and aggregated for presentation. Results of the previous surveys were reported in [1] and [2]. Tabular results of the two latest surveys are presented in Tables I-VII. Numbered years in the tables refer to calendar years. Comparisons are made with corresponding data from previous years, and discussion is limited to comments on changes and trends.
An academic program providing realistic training in software engineering
Authors: Busenberg Stavros N. , Tam Wing C.
Published: July 2002

An academic program at Harvey Mudd College, called the Clinic program, brings projects from industry on campus to be studied and solved by student teams. The objective of the Clinic is to provide students, working as small teams under careful faculty supervision, an opportunity to work on real world problems of sufficient magnitude and complexity. Under this program, students can acquire essential skills of software engineering, such as team work, software project management, software design methodology, and communication skills, in a realistic environment. Sample software projects undertaken by the Clinic are described. Experience so far has shown that the program is a viable transition from an academic to industrial world.
Structured programming in Cobol
Authors: van Gelder Allen
Published: July 2002

Techniques for designing and writing Cobol programs are presented. Previous work in structured programming is drawn upon and adapted. The presentation is informal: the terminology is nonmathematical as far as possible, no theorems are proved, and examples are used frequently. Top-down program design is implemented through the use of structured flowcharts, disciplined specifications, and step by step verification. A well-formed Cobol program is defined. The proper use of the GO TO and other Cobol coding practices are discussed.
Memory management and response time
Authors: Brown R. M. , Browne J. C. , Chandy K. M.
Published: July 2002

This paper presents a computationally tractable methodology for including accurately the effects of finite memory size and workload memory requirements in queueing network models of computer systems. Empirical analyses and analytic studies based on applying this methodology to an actual multiaccess interactive system are reported. Relations between workload variables such as memory requirement distribution and job swap time, and performance measures such as response time and memory utilization are graphically displayed. A multiphase, analytically soluble model is proposed as being broadly applicable to the analysis of interactive computer systems which use nonpaged memories.
Feedback coupled resource allocation policies in the multiprogramming-multiprocessor computer system
Authors: Brice Richard S. , Browne J. C.
Published: July 2002

Model studies of some integrated, feedback-driven scheduling systems for multiprogrammed-multiprocessor computer systems are presented. The basic control variables used are the data-flow rates for the processes executing on the CPU. The model systems feature simulated continuous-flow and preempt-resume scheduling of input-output activity. Attention is given to the amount of memory resource required for effective processing of the I/O activity (buffer space assignment). The model studies used both distribution-driven and trace-driven techniques. Even relatively simple dynamic schedulers are shown to improve system performance (as measured by user CPU time) over that given by optimal or near-optimal static schedulers imbedded in identical system structures and workload environments. The improvement is greatest under a heavy I/O demand workload.
Generalized working sets for segment reference strings
Authors: Denning Peter J. , Slutz Donald R.
Published: July 2002

The working-set concept is extended for programs that reference segments of different sizes. The generalized working-set policy (GWS) keeps as its resident set those segments whose retention costs do not exceed their retrieval costs. The GWS is a model for the entire class of demand-fetching memory policies that satisfy a resident-set inclusion property. A generalized optimal policy (GOPT) is also defined; at its operating points it minimizes aggregated retention and swapping costs. Special cases of the cost structure allow GWS and GOPT to simulate any known stack algorithm, the working set, and VMIN. Efficient procedures for computing demand curves showing swapping load as a function of memory usage are developed for GWS and GOPT policies. Empirical data from an actual system are included.
Production and employment of Ph.D.'s in computer science—1976
Authors: Taulbee Orrin E. , Conte S. D.
Published: July 2002

Statistics are presented on the production and employment of Ph.D.'s in computer science for the calendar year 1975-76. Data include profiles of graduate students and of faculty at 60 Ph.D.-producing departments as well as a breakdown of degrees granted by specialty areas. Significant trends are noted and comparisons with comparable data gathered for the 1974-75 calendar year are made.
The GRE advanced test in computer science
Authors: Austing Richard H.
Published: July 2002

This report describes the Advanced Test in Computer Science which was recently introduced in the Graduate Record Examination Program. The GRE program is described in general, and, the events leading to the establishment of the Advanced Computer Science Test are discussed. Content specifications and their rationale are given. A set of sample questions is included.
On maintenance of the opportunity list for class-teacher timetable problems
Authors: Smith Graham
Published: July 2002

One of the principal components of procedures for the solution of class-teacher timetable problems is that for maintenance of the opportunity list. Opportunity list maintenance methods are based on necessary conditions for the existence of a solution. A general framework for necessary conditions, together with four specific sets of necessary conditions, is given.
A high security log-in procedure
Authors: Purdy George B.
Published: July 2002

The protection of time sharing systems from unauthorized users is often achieved by the use of passwords. By using one-way ciphers to code the passwords, the risks involved with storing the passwords in the computer can be avoided. We discuss the selection of a suitable one-way cipher and suggest that for this purpose polynomials over a prime modulus are superior to one-way ciphers derived from Shannon codes.
Teacher/student authored CAI using the NEWBASIC system
Authors: Dwyer T. A.
Published: July 2002

The pedagogical advantages of a general purpose interactive system called NEWBASIC/CATALYST are discussed. NEWBASIC/CATALYST incorporates an advanced implementation of BASIC, system-level interactive features, and a general capability for extension through user oriented function attachment. Application of this last feature to provide a flexible CAI scan capability is illustrated. An example of interaction at the system level shows how students can mix the advantages of independent or “solo” mode computing with those of guided or “dual” mode interaction. Preliminary experience with the system in an urban secondary school setting is discussed.
Matrix computations with Fortran and paging
Authors: Moler Cleve B.
Published: July 2002

The efficiency of conventional Fortran programs for matrix computations can often be improved by reversing the order of nested loops. Such modifications produce modest savings in many common situations and very significant savings for large problems run under an operating system which uses paging.
Interference between communicating parallel processes
Authors: Gilbert Philip , Chandler W. J.
Published: July 2002

Various kinds of interference between communicating parallel processes have been examined by Dijkstra, Knuth, and others. Solutions have been given for the mutual exclusion problem and associated subproblems, in the form of parallel programs, and informal proofs of correctness have been given for these solutions.

In this paper a system of parallel processes is regarded as a machine which proceeds from one
state S
(i.e. a collection of pertinent data values and process configurations) to a next state
S
′ in accordance with a
transition rule S
⇒
S
′.

A set of such rules yields sequences of states, which dictate the system's behavior. The mutual exclusion problem and the associated subproblems are formulated as questions of inclusion between sets of states, or of the existence of certain sequences. A mechanical proof procedure is shown, which will either verify (prove the correctness of) or discredit (prove the incorrectness of) an attempted solution, with respect to any of the interference properties.

It is shown how to calculate transition rules from the “partial rules” by which the individual processes operate. The formation of partial rules and the calculation of transition rules are both applicable to hardware processes as well as to software processes, and symmetry between processes is not required.
Some complete calculi for matrices
Authors: Bayer Rudolf , Witzgall Christoph
Published: July 2002

A matrix calculus is introduced with the intention of developing data structures suitable for a high level algorithmic language for mathematical programming. The paper investigates how the special structure of matrices can be described and utilized for efficient computing by saving memory space and superfluous operations.

Sequences of matrices (and sequences of sequences of matrices) are considered, and matrix operators are extended to sequence operators and cumulative operators.

Algorithms are given which use symbol manipulation of matrix expressions so as to find the forms best suited for computation. These forms are called
normal forms
. Several completeness results are obtained in the sense that for each expression an equivalent expression in normal form can be found within a specified calculus.
Multiple terminals under user program control in a time-sharing environment
Authors: McGeachie John S.
Published: July 2002

User-written programs on the Dartmouth Time-Sharing System can communicate with many remote terminals simultaneously and can control the interactions between these terminals. Such programs can be written using standard input and output instructions in any language available on the system. This paper describes how this multiple-terminal facility was implemented without requiring any changes in the system executive or in any of the system's compilers or interpreters.