bluuebunny/crossref_metadata_2025 huggingface dataset:
Converting a textbook to hypertext
Authors: Rada Roy
Published: July 2002

Traditional documents may be transformed into hypertext by first reflecting the document's logical markup in the hypertext (producing first-order hypertext) and then by adding links not evident in the document markup (producing second-order hypertext). In our transformation of a textbook to hypertext, the textbook is placed in an intermediate form based on a semantic net and is then placed into the four hypertext systems: Emacs-Info, Guide, HyperTies, and Super-Book. The first-order Guide and SuperBook hypertexts reflect a depth-first traversal of the semantic net, and the Emacs-Info and HyperTies hypertexts reflect a breadth-first traversal. The semantic net is augmented manually, and then new traversal programs automatically generate alternate outlines. An index based on work patterns in the textbook is also automatically generated for the second-order hypertext. Our suite of programs has been applied to a published textbook, and the resulting hypertexts are publicly available.
Three-dimensional alpha shapes
Authors: Edelsbrunner Herbert , Mücke Ernst P.
Published: July 2002

Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the “shape” of the set. For that purpose, this article introduces the formal notion of the family of α-shapes of a finite point set in R3. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter α ε R controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of sizenin time0(n2), worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.
Equational inference, canonical proofs, and proof orderings
Authors: Bachmair Leo , Dershowitz Nachum
Published: July 2002

We describe the application of proof orderings—a technique for reasoning about inference systems-to various rewrite-based theorem-proving methods, including refinements of the standard Knuth-Bendix completion procedure based on critical pair criteria; Huet's procedure for rewriting modulo a congruence; ordered completion (a refutationally complete extension of standard completion); and a proof by consistency procedure for proving inductive theorems.
Extending context-free grammars with permutation phrases
Authors: Cameron Robert D.
Published: July 2002

A
permutation phrase
is a grammatical phrase that specifies a syntactic construct as any permutation of a set of constituent elements. Permutation phrases allow for the concise and natural expression of free-order constructs as found in programming languages and notations such as C, Cobol, BibTEX, and Unix command lines.

The conciseness and clarity of expression that permutation phrase grammars offer over context-free grammars are illustrated through a case study of the declarations in C. The parsing problem for permutation phrase grammars is considered, and it is shown how efficient linear-time parsing can be achieved for permutation phrase grammars satisfying an extended notion of the LL(1) property.
A framework for undoing actions in collaborative systems
Authors: Prakash Atul , Knister Michael J.
Published: July 2002

The ability to undo operations is a standard feature in most single-user interactive applications. We propose a general framework for implementing undo in collaborative systems. The framework allows users to reverse their own changes individually, taking into account the possibility of conflicts between different users' operations that may prevent an undo. The proposed framework has been incorporated into DistEdit, a toolkit for building group text editors. Based on our experience with DistEdit's undo facilities, we discuss several issues that need to be taken into account in using the framework, in order to ensure that a reasonable undo behavior is provided to users. We show that the framework is also applicable to single-user systems, since the operations to undo can be selected not just on the basis of who performed them, but by any appropriate criterion, such as the document region in which the operations occurred or the time interval in which the operations were carried out.
The Totem single-ring ordering and membership protocol
Authors: Amir Y. , Moser L. E. , Melliar-Smith P. M. , Agarwal D. A. , Ciarfella P.
Published: July 2002

Fault-tolerant distributed systems are becoming more important, but in existing systems, maintaining the consistency of replicated data is quite expensive. The Totem single-ring protocol supports consistent concurrent operations by placing a total order on broadcast messages. This total order is derived from the sequence number in a token that circulates around a logical ring imposed on a set of processors in a broadcast domain. The protocol handles reconfiguration of the system when processors fail and restart or when the network partitions and remerges. Extended virtual synchrony ensures that processors deliver messages and configuration changes to the application in a consistent, systemwide total order. An effective flow control mechanism enables the Totem single-ring protocol to achieve message-ordering rates significantly higher than the best prior total-ordering protocols.
Monitor classification
Authors: Buhr Peter A. , Fortier Michel , Coffin Michael H.
Published: July 2002

One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for systems with shared memory, is the
monitor
. Over the past twenty years many kinds of monitors have been proposed and implemented, and many modern programming languages provide some form of monitor for concurrency control. This paper presents a taxonomy of monitors that encompasses all the extant monitors and suggests others not found in the literature or in existing programming languages. It discusses the semantics and performance of the various kinds of monitors suggested by the taxonomy, and it discusses programming techniques suitable to each.
An introduction to partial evaluation
Authors: Jones Neil D.
Published: July 2002

Partial evaluation provides a unifying paradigm for a broad spectrum of work in program optimization compiling interpretation and the generation of automatic program generators [Bjørner et al. 1987; Ershov 1992; and Jones et al. 1993]. It is a program optimization technique, perhaps better called
program specialization
, closely related to but different from Jørring and Scherlis'
staging transformations
[1986]. It emphasizes, in comparison with Burstall and Darlington [1977] and Jørring and Scherlis [1986] and other program transformation work,
full automation
and the generation of
program generators
as well as transforming single programs. Much partial evaluation work to date has concerned automatic compiler generation from an interpretive definition of programming language, but it also has important applications to scientific computing, logic programming, metaprogramming, and expert systems; some pointers are given later.
Making a digital library
Authors: Entlich Richard , Olsen Jan , Garson Lorrin , Lesk Michael , Normore Lorraine , Weibel Stuart
Published: July 2002

The CORE (Chemical Online Retrieval Experiment) project is a library of primary journal articles in chemistry. Any library has an inside and an outside; in this article we describe the inside of the library and the methods for building the system and accumulating the database. A later article will describe the outside (user experiences). Among electronic-library projects, the CORE project is unusual in that it has both ASCII derived from typesetting and image data for all its pages, and among experimental electronic-library projects, it is unusually large. We describe here (a) the processes of scanning and analyzing about 400,000 pages of primary journal material, (b) the conversion of a similar amount of textual database material, (c) the linking of these two data sources, and (d) the indexing of the text material.
The effect of accessing nonmatching documents on relevance feedback
Authors: Dunlop Mark D.
Published: July 2002

Traditional information retrieval (IR) systems only allow users access to documents that match their current query, and therefore, users can only give relevance feedback on matching documents (or those with a matching strength greater than a set threshold. This article shows that, in systems that allow access to nonmatching documents (e.g., hybrid hypertext and information retrieval systems), the strength of the effect of giving relevance feedback varies between matching and nonmatching documents. For positive feedback the results shown here are encouraging, as they can be justified by an intuitive view of the process. However, for negative feedback the results show behavior that cannot easily be justified and that varies greatly depending on the model of feedback used.
Algorithms to compute bridging fault coverage ofIDDQtest sets
Authors: Thadikaran Paul , Chakravarty Sreejit , Patel Janak
Published: July 2002

We present two algorithms, called list-based scheme and tree-based scheme, to compute bridging fault (BF) coverage ofIDDQtests. These algorithms use the novel ideal of “indistinguishable pairs,” which makes it more efficient and versatile than known fault simulation algorithms. Unlike known algorithms, the two algorithms can be used for combinational as well as sequential circuits and for arbitrary sets of BFs. Experiments show that the tree-based scheme is, in general, better than the list-based scheme. But the list-based scheme is better for some classes of faults.
Software process modeling and execution within virtual environments
Authors: Doppke John C. , Heimbigner Dennis , Wolf Alexander L.
Published: July 2002

In the past, multiuser virtual environments have been developed as venues for entertainment and social interaction. Recent research focuses instead on their utility in carrying out work in the real world. This research has identified the importance of a mapping between the real and the virtual that permits the representation of real tasks in the virtual environment. We investigate the use of virtual environments—in particular, MUDs (Multi-User Dimensions)—in the domain of software process. In so doing, we define a mapping, ormetaphor, that permits the representation of software processes within a MUD. The system resulting from this mapping, calledPromo, permits the modeling and execution of software processes by geographically dispersed agents.
Grosch's law re-revisited: CPU power and the cost of computation
Authors: Ein-Dor Phillip
Published: July 2002

Does Grosch's law, which postulated that the costs of computer systems increase at a rate equivalent to the square root of their power, still hold? The age of mini-, micro-, and supercomputers seems to have complicated the situation. When computers are grouped according to their size and power, Grosch's law seems to hold within each group, but not between different groups.
Curve-drawing algorithms for Raster displays
Authors: Van Aken Jerry , Novak Mark
Published: July 2002

The
midpoint
method for deriving efficient scan-conversion algorithms to draw geometric curves on raster displays in described. The method is general and is used to transform the nonparametric equation
f(x,y)
= 0, which describes the curve, into an algorithms that draws the curve. Floating point arithmetic and time-consuming operations such as multiplies are avoided. The maximum error of the digital approximation produced by the algorithm is one-half the distance between two adjacent pixels on the display grid. The midpoint method is compared with the
two-point
method used by Bresenham, and is seen to be more accurate (in terms of the linear error) in the general case, without increasing the amount of computation required. The use of the midpoint method is illustrated with examples of lines, circles, and ellipses. The considerzations involved in using the method to derive algorithms for drawing more general classes of curves are discussed.
A study of probability kinematics in information retrieval
Authors: Crestani F. , van Rijsbergen C. J.
Published: July 2002

We analyze the kinematics of probabilistic term weights at retrieval time for different Information Retrieval models. We present four models based on different notions of probabilistic retrieval. Two of these models are based on classical probability theory and can be considered as prototypes of models long in use in Information Retrieval, like the Vector Space Model and the Probabilistic Model. The two other models are based on a logical technique of evaluating the probability of a conditional called imaging; one is a generalization of the other. We analyze the transfer of probabilities occurring in the term space at retrieval time for these four models, compare their retrieval performance using classical test collections, and discuss the results. We believe that our results provide useful suggestions on how to improve existing probabilistic models of Information Retrieval by taking into consideration term-term similarity.
Algorithm 651
Authors: Boisvert Ronald F.
Published: July 2002

HFFT is a software package for solving the Helmholtz equation on bounded two- and three-dimensional rectangular domains with Dirichlet, Neumann, or periodic boundary conditions. The software is the result of combining new fourth-order accurate compact finite difference (HODIE) discretizations and a fast-direct solution technique (the Fourier method). In this paper we briefly describe the user interface to HFFT and present an example of its usage and several details of its implementation.
On threshold pivoting in the multifrontal method for sparse indefinite systems
Authors: Liu Joseph W. H.
Published: July 2002

A simple modification to the numerical pivot selection criteria in the multifrontal scheme of Duff and Reid for sparse symmetric matrix factorization is presented. For a given threshold value, the modification allows a broader choice of block 2 X 2 pivots owing to a less restrictive pivoting condition. It also extends the range of permissible threshold values from [0, 1/2) to [0, 0.6404). Moreover, the bound on element growth for stability consideration in the modified scheme is nearly the same as that of the original strategy.
An object-oriented programming discipline for standard Pascal
Authors: Jacky Jonathan P. , Kalet Ira J.
Published: July 2002

A successful application, using standard Pascal in a large medical application program, demonstrates that benefits similar to those of specialized languages are possible in object-oriented programming.
BIFEST
Authors: Lee Kuen-Jong , Tang Jing-Jou , Huang Tsung-Chu
Published: July 2002

This paper presents BIFEST, an ATPG system that employs the built-in intermediate voltage test technique in an efficient ATPG process to deal with CMOS bridging faults. Fast and accurate calculations of the intermediate bridging voltages and the variant threshold tolerance margins on a resistive bridging fault model are presented. A PODEM-like, PPSFP-based ATPG process is developed to generate test patterns for faults that are conventionally logic-testable. The remaining faults are then dealt with by special circuits, called built-in intermediate voltage sensors (BIVSs). By this methodology, almost the same fault coverage as that employingIDDQtesting can be achieved with only logic monitoring required.
Theseus—a programming language for relational databeses
Authors: Shopiro Jonathan E.
Published: July 2002

Theseus, a very high-level programming language extending EUCLID, is described. Data objects in Theseus include relations and a-sets, a generalization of records. The primary design goals of Theseus are to facilitate the writing of well-structured programs for database applications and to serve as a vehicle for research in automatic program optimization.
Spatial management of data
Authors: Herot Christopher F.
Published: July 2002

Spatial data management is a technique for organizing and retrieving information by positioning it in a graphical data space (GDS). This graphical data space is viewed through a color raster-scan display which enables users to traverse the GDS surface or zoom into the image to obtain greater detail. In contrast to conventional database management systems, in which users access data by asking questions in a formal query language, a spatial data management system (SDMS) presents the information graphically in a form that seems to encourage browsing and to require less prior knowledge of the contents and organization of the database.

This paper presents an overview of the SDMS concept and describes its implementation in a prototype system for retrieving information from both a symbolic database management system and an optical videodisk.
A New Method of Checking the Consistency of Precedence Matrices
Authors: Marimont Rosalind B.
Published: July 2002

A new method of checking the consistency of precedence matrices is demonstrated. The method is based on the theorem that a precedence matrix is consistent if and only if every principal submatrix has at least one zero row or zero column. Because this method recognizes inconsistencies in their implicit form whereas the conventional method recognized only explicit contradictions, a considerable saving in time and effort can be effected, since the process of making explicit all the implications of a precedence matrix particularly a larger one, is a tedious time-consuming operation.
A Modification of Nordsieck's Method Using an ``Off-Step'' Point
Authors: Kohfeld J. J. , Thompson G. T.
Published: July 2002

In 1962, Nordsieck presented a series of numerical methods for solving ordinary differential equations which rely on Taylor's series, but which are equivalent to the correctors in the Adams methods. In a method of Nordsieck, simplifications, such as in the often desirable process of changing step size, are made, since it is unnecessary to store more than one previous step. In 1964, Gragg and Stetter published a series of numerical methods for solving ordinary differential equations which rely on very accurate correctors, using a “nonstep” point within the interval of integration. The method in the present paper is equivalent, for uniform step size, to one of these very accurate correctors but is in the form of Nordsieck. The strengths and weaknesses of the method are discussed.
Automorphisms of Polyadic Automata
Authors: Grzymala-Busse Jerzy W.
Published: July 2002

This paper is a continuation of the studies of Fleck, Weeg, and others concerning the theory of automorphisms of ordinary automata and of the work of Gil pertaining to time varying automata. A certain restricted class of time-varying automata, namely the class of polyadic automata, is investigated in detail. The results of an investigation of relationships concerning the group of automorphisms, the polyadic group of defined polyadic automata and the structure of the polyadic automation and the ordinary automata associated and with the polyadic automaton is presented.
Analysis and Optimization of Disk Storage Devices for Time-Sharing Systems
Authors: Frank H.
Published: July 2002

A major limitation for time-sharing systems is the time delay encountered in transferring records between central “fast” memory and peripheral memory devices. In this paper the transfer characteristics of disk storage devices are considered. Expected seek time and expected rotational latency are taken as measures of performance for the disk. The following aspects of disk files and their behavior are considered: the speed profile of the positioning mechanism and its effect on seek time; effects of the probability distribution of information stored on tracks; track overflow of records; dynamic queuing strategies; reduction of rotation time by buffered read techniques; and strategies for using multiple-arm devices.
Bounds on the Complexity of the Longest Common Subsequence Problem
Authors: Ullman J. D. , Aho A. V. , Hirschberg D. S.
Published: July 2002

The problem of finding a longest common subsequence of two strings is discussed. This problem arises in data processing applications such as comparing two files and in genetic applications such as studying molecular evolution. The difficulty of computing a longest common subsequence of two strings is examined using the decision tree model of computation, in which vertices represent “equal - unequal” comparisons. It is shown that unless a bound on the total number of distinct symbols is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings. A general lower bound as a function of the ratio of alphabet size to string length is derived. The case where comparisons between symbols of the same string are forbidden is also considered and it is shown that this problem is of linear complexity for a two-symbol alphabet and quadratic for an alphabet of three or more symbols.
Size complexity in context-free grammars forms
Authors: Ginsburg Seymour , Lynch Nancy
Published: July 2002

Grammar forms are compared for their efficiency in representing languages, as measured by the sizes (i.e. total number of symbols, number of variable occurrences, number of productions, and number of distinct variables) of interpretation grammars. For every regular set, right- and left-linear forms are essentially equal in efficiency. Any form for the regular sets provides, at most, polynomial improvement over right-linear form. Moreover, any polynomial improvement is attained by some such form, at least on certain languages. Greater improvement for some languages is possible using forms expressing larger classes of languages than the regular sets. However, there are some languages for which no improvement over right-linear form is possible.

While a similar set of results holds for forms expressing exactly the linear languages, only linear improvement can occur for forms expressing all the context-free languages.
Algorithm 799: revolve
Authors: Griewank Andreas , Walther Andrea
Published: July 2002

In its basic form, the reverse mode of computational differentiation yields the gradient of a scalar-valued function at a cost that is a small multiple of the computational work needed to evaluate the function itself. However, the corresponding memory requirement is proportional to the run-time of the evaluation program. Therefore, the practical applicability of the reverse mode in its original formulation is limited despite the availability of ever larger memory systems. This observation leads to the development of checkpointing schedules to reduce the storage requirements. This article presents the function revolve, which generates checkpointing schedules that are provably optimal with regard to a primary and a secondary criterion. This routine is intended to be used as an explicit “controller” for running a time-dependent applications program.
PYTHIA-II
Authors: Houstis Elias N. , Catlin Ann C. , Rice John R. , Verykios Vassilios S. , Ramakrishnan Naren , Houstis Catherine E.
Published: July 2002

Often scientists need to locate appropriate software for their problems and then select from among many alternatives. We have previously proposed an approach for dealing with this task by processing performance data of the targeted software. This approach has been tested using a customized implementation referred to as PYTHIA. This experience made us realize the complexity of the algorithmic discovery of knowledge from performance data and of the management of these data together with the discovered knowledge. To address this issue, we created PYTHIA-II—a modular framework and system which combines a general
knowledge discovery in databases
(KDD) methodology and
recommender
system technologies to provide advice about scientific software/hardware artifacts. The functionality and effectiveness of the system is demonstrated for two existing performance studies using sets of software for solving partial differential equations. From the end-user perspective, PYTHIA-II allows users to specify the problem to be solved and their computational objectives. In turn, PYTHIA-II (i) selects the software available for the user's problem (ii) suggests parameter values, and (iii) assesses the recommendation provided. PYTHIA-II provides all the necessary facilities to set up database schemas for testing suites and associated performance data in order to test sets of software. Moreover, it allows easy interfacing of alternative data mining and recommendation facilities. PYTHIA-II is an open-ended system implemented on public domain software and has been used for performance evaluation in several different problem domains.
Web-based network analysis and design
Authors: Rao Dhananjai Madhava , Radhakrishnan Radharamanan , Wilsey Philip A.
Published: July 2002

The gradual acceptance of high-performance networks as a fundamental component of today's computing environment has allowed applications to evolve from static entities located on specific hosts to dynamic, distributed entities that are resident on one or more hosts. In addition, vital components of software and data used by an application may be distributed across the local/wide area network. Given such a fluid and dynamic environment, the design and analysis of high-performance communication networks (using off-the-shelf components offered by third party manufacturers) has been further complicated by the diversity of the available components. To alleviate these problems and to address the verification and validation issues involved in engineering such complex networks, a web-based framework for the design and analysis of computer networks was developed. Using the framework, a designer can explore design alternatives by constructing and analyzing configurations of the design using components offered by different researchers and manufacturers. The framework provides a flexible and robust environment for selecting and verifying the optimal solution from a large and complex solution space. This paper presents issues involved in the design and development of the framework.
A Survey of Data Structures for Computer Graphics Systems
Authors: Williams Robin
Published: July 2002

This is a survey of a data structures and their use in computer graphics systems. First, the reasons for using data structures are given. Then the sequential, random, and list organizations are discussed, and it is shown how they may be used to build complex data structures. Representative samples of languages specifically designed for creating and manipulating data structures are described next. Finally some typical computer graphics systems and their data structures are described. It is also pointed out that much work remains to be done to develop a satisfactory theoretical foundation for designing data structures.
Grapevine
Authors: Birrell Andrew D. , Levin Roy , Schroeder Michael D. , Needham Roger M.
Published: July 2002

Grapevine is a multicomputer system on the Xerox research internet. It provides facilities for the delivery of digital messages such as computer mail; for naming people, machines, and services; for authenticating people and machines; and for locating services on the internet. This paper has two goals: to describe the system itself and to serve as a case study of a real application of distributed computing. Part I describes the set of services provided by Grapevine and how its data and function are divided among computers on the internet. Part II presents in more detail selected aspects of Grapevine that illustrate novel facilities or implementation techniques, or that provide insight into the structure of a distributed system. Part III summarizes the current state of the system and the lesson learned from it so far.
The external auditor's review of computer controls
Authors: Litecky Charles R. , Rittenberg Larry E.
Published: July 2002

The Foreign Corrupt Practices Act of 1977, coupled with growing demands for corporate accountability, have forced both auditors and computer administrators to evaluate computer based controls. Computer administrators can benefit from both a knowledge of an auditor's approaches to evaluating controls and his/her recommendations for control improvements. Here, a survey of the control evaluation practices and desirable control features identified by computer auditors is presented, along with recommendations to ease the burden of the auditor's review. The authors' suggestions should ease the tasks of internal control analysis and of preparation for possible public reports on an organization's system of internal control.
Segment sizes and liftetimes in Algol 60 programs
Authors: Batson A. P. , Brundage R. E.
Published: July 2002

The characteristics of the virtual memory requirements of a sample of Algol 60 programs have been measured. Distributions are presented for the sizes of memory requests and for their holding times (lifetimes). The results are presented in terms of Johnston's contour model and a simple abstract machine. They provide new empirical evidence of certain aspects of the construction and behavior of real programs, and some of their implications for the design of virtual memory systems are presented and discussed.
An optimal method for deletion in one-sided height-balanced trees
Authors: Zweben S. H. , McDonald M. A.
Published: July 2002

A one-sided height-balanced tree is a binary tree in which every node's right subtree has a height which is equal to or exactly one greater than the height of its left subtree. It has an advantage over the more general AVL tree in that only one bit of balancing information is required (two bits are required for the AVL tree).

It is shown that deletion of an arbitrary node of such a tree can be accomplished in
O
(log
n
) operations, where
n
is the number of nodes in the tree. Moreover the method is optimal in the sense that its complexity cannot be reduced in order of magnitude. This result, coupled with earlier results by Hirschberg, indicates that, of the three basic problems of insertion, deletion, and retrieval, only insertion is adversely affected by this modification of an AVL tree.
Abstraction mechanisms in CLU
Authors: Liskov Barbara , Snyder Alan , Atkinson Russell , Schaffert Craig
Published: July 2002

CLU is a new programming language designed to support the use of abstractions in program construction. Work in programming methodology has led to the realization that three kinds of abstractions—procedural, control, and especially data abstractions—are useful in the programming process. Of these, only the procedural abstraction is supported well by conventional languages, through the procedure or subroutine. CLU provides, in addition to procedures, novel linguistic mechanisms that support the use of data and control abstractions. This paper provides an introduction to the abstraction mechanisms in CLU. By means of programming examples, the utility of the three kinds of abstractions in program construction is illustrated, and it is shown how CLU programs may be written to use and implement abstractions. The CLU library, which permits incremental program development with complete type checking performed at compile time, is also discussed.
Two-level control structure for nondeterministic programming
Authors: Montangero C. , Pacini G. , Turini F.
Published: July 2002

The basic ideas of nondeterministic programming are critically reconsidered to single out a proper attitude and programming style for languages allowing direct control of nondeterministic features. The proposed attitude aims at retaining the purity of the nondeterministic formulation of search processes on one level (the
attempt
level), deferring the coordination of problem solving efforts to another (the
choice
level). The feasibility of recognizing these two levels is discussed, stressing that the structure to be managed at the choice level is a tree of contexts. The leaves are computational environments, each holding an alternative under inspection, while the other nodes are associated with choice points. According to the proposed programming style, a
generative function
is associated with each choice point, which expresses the desired choice strategy. The main advantage of this approach is the localization of the search strategies: Each nonterminal node of the tree keeps track of the state of the computation as it was when the choice point was last interrogated, holding at the same time the strategy to coordinate the available alternatives. Examples are given in term of ND-Lisp, an extension of Lisp designed and implemented according to these guidelines.
Heaps applied to event driven mechanisms
Authors: Gonnet Gaston H.
Published: July 2002

I read with great interest F.P. Wyman's paper “Improved Event-Scanning Mechanisms for Discrete Event Simulation” [10] which, I found, makes a careful study of some techniques for event-list scanning.
A fast method for solving a class of tridiagonal linear systems
Authors: Malcolm Michael A. , Palmer John
Published: July 2002

The solution of linear systems having real, symmetric, diagonally dominant, tridiagonal coefficient matrices with constant diagonals is considered. It is proved that the diagonals of the
LU
decomposition of the coefficient matrix rapidly converge to full floating-point precision. It is also proved that the computed
LU
decomposition converges when floating-point arithmetic is used and that the limits of the
LU
diagonals using floating point are roughly within machine precision of the limits using real arithmetic. This fact is exploited to reduce the number of floating-point operations required to solve a linear system from 8
n
- 7 to 5
n
+ 2
k
- 3, where
k
is much less than
n
, the order of the matrix. If the elements of the subdiagnals and superdiagonals are 1, then only 4
n
+ 2
k
- 3 operations are needed. The entire
LU
decomposition takes
k
words of storage, and considerable savings in array subscripting are achieved. Upper and lower bounds on
k
are obtained in terms of the ratio of the coefficient matrix diagonal constants and parameters of the floating-point number system.

Various generalizations of these results are discussed.
The synthesis of loop predicates
Authors: Wegbreit Ben
Published: July 2002

Current methods for mechanical program verification require a complete predicate specification on each loop. Because this is tedious and error prone, producing a program with complete, correct predicates is reasonably difficult and would be facilitated by machine assistance. This paper discusses techniques for mechanically synthesizing loop predicates. Two classes of techniques are considered: (1) heuristic methods which derive loop predicates from boundary conditions and/or partially specified inductive assertions: (2) extraction methods which use input predicates and appropriate weak interpretations to obtain certain classes of loop predicates by an evaluation on the weak interpretation.
Algorithm 483: Masked three-dimensional plot program with rotations
Authors: Watkins Steven L.
Published: July 2002

PLOT3D
will accept three-dimensional data in various forms, rotate it in three-space, and plot the projection of the resulting figure onto the
x-y
plane. Those lines or portions of lines which should be hidden by previous lines are masked.
Computer programming as an art
Authors: Knuth Donald E.
Published: July 2002

When
Communications of the ACM
began publication in 1959, the members of ACM's Editorial Board made the following remark as they described the purposes of ACM's periodicals [2]: “If computer programming is to become an important part of computer research and development, a transition of programming from an art to a disciplined science must be effected.” Such a goal has been a continually recurring theme during the ensuing years; for example, we read in 1970 of the “first steps toward transforming the art of programming into a science” [26]. Meanwhile we have actually succeeded in making our discipline a science, and in a remarkably simple way: merely by deciding to call it “computer science.”
A practical approach to managing resources and avoiding deadlocks
Authors: Frailey Dennis J.
Published: July 2002

Resource scheduling and allocation can be expensive with regard to time and space in multiprogramming or time-sharing environments involving large numbers of tasks and resources with conflicting requirements. Detection and/or prevention of deadlocks can require massive amounts of additional overhead if efficient usage of resources is to be maintained.

A resource management program is described which uses linked lists along with other techniques to overcome a large portion of this overhead. The program, which is currently running as part of a large scale general purpose operating system, keeps resources relatively active but does not detect or prevent all deadlocks in its implemented state. Certain changes, which would permit more comprehensive levels of deadlock prevention/detection at additional cost, have not been incorporated in the running system due to the infrequency of deadlock situations.
Comment on the working set model for program behavior
Authors: Bernstein Arthur
Published: July 2002

In the paper “The Working Set Model for Program Behavior” by Peter Denning [
Comm. ACM 11
, 5 (May 1968), 323-333], an algorithm is described for the management of a paged memory under demand paging. In the process of analyzing this model, the author presents what appears to be an incorrect expression for Φ(
τ
), the real-time rate at which page faults occur in the system [eq. (13)]. Under the assumptions made in the article it appears that the best one can do in this area is to place an upper and lower bound on Φ(
τ
). These bounds are given below.
Simulation of traffic flows in a network
Authors: Sakai Toshiyuki , Nagao Makoto
Published: July 2002

A computer simulation program which deals with traffic flows in the network of a large area is described. Each road is segmented into blocks of several ten-meter lengths and is represented by a bidirectional list in computer memory. The movement of cars, i.e. the transfer of cars from one block to the next, is expressed by a proper formula. This formula is based on the supposition that the speed of cars in a block is determined only by the density of cars in the block, and this speed-versus-density curve is empirically given the numerical values.

This simulation scheme has its excellent point in that it makes it possible to trace the dynamic behavior of traffic flows in a variety of situations, some examples of which are given for an actual area of the city of Kyoto, Japan.
Protecting privacy using the decentralized label model
Authors: Myers Andrew C. , Liskov Barbara
Published: July 2002

Stronger protection is needed for the confidentiality and integrity of data, because programs containing untrusted code are the rule rather than the exception. Information flow control allows the enforcement of end-to-end security policies, but has been difficult to put into practice. This article describes the decentralized label model, a new label model for control of information flow in systems with mutual distrust and decentralized authority. The model improves on existing multilevel security models by allowing users to declassify information in a decentralized way, and by improving support for fine-grained data sharing. It supports static program analysis of information flow, so that programs can be certified to permit only acceptable information flows, while largely avoiding the overhead of run-time checking. The article introduces the language Jif, an extension to Java that provides static checking of information flow using the decentralized label model.
Some remarks on the syntax of symbolic programming languages
Authors: Di Forino Alfonso Caracciolo
Published: July 2002

This paper concerns some preliminary results of an investigation of certain syntactical features of symbolic programming languages (SPL), which is a part of a wider research in the field of problem-oriented languages for automatic processor construction [1]. Our main aim is to point out certain peculiar features of SPL's which yield a deeper insight into their linguistic nature from a formal point of view, in order to take further steps in the direction of finding a proper way to define them. The general approach suggested here might be of some interest in the broader field of general linguistics, since many languages, including natural languages, show similar properties.
A note on the dangling else ALGOL 60
Authors: Kaupe Arthur F.
Published: July 2002

Some revisions of ALGOL 60 are proposed, which not only eliminate certain ambiguous statements but also add some convenience to the language. A discussion of the background of the problem and a sketch of a proof that the ambiguities have been removed is included.
Sequential formula translation
Authors: Samelson K. , Bauer F. L.
Published: July 2002

The syntax of an algorithmic language such as ALGOL is conveniently described as a sequence of states indicated by an element called cellar. Transitions are controlled by admissible state-symbol pairs which may be represented by a transition matrix. This description of syntax furnishes at the same time an extremely simple rule for translating into machine programs statements in the algorithmic language. Sequential treatment, however, is not feasible in the case of certain optimizing processes such as recursive address calculation.
A redundancy check for ALGOL programs
Authors: Thacher Henry C.
Published: July 2002

In using ALGOL, or any other common language for communicating among computers with different input-output media, one or more human beings is normally present in the communication channel. In the otherwise convenient method of communication by published algorithms, at least three humans are directly involved: a typist to prepare the manuscript in reference or publication language, a typesetter, and a keypunch operator to prepare the program for the computer in its hardware language. In spite of checking by authors, proof readers, editors, and verifiers, this process is a noisy one, involving as it does not only copying a synthetic (and therefore unfamiliar) language, but also translation to and from the publication dialect. The number of minor typographical errors which have been detected and reported in published algorithms confirms this observation. Clearly some check of the accuracy with which an algorithm has been transmitted through this noisy channel would be desirable. The solution which we propose is directed particularly to ALGOL 60, but the same problems exist with other common languages, and the principles which we use could be readily adapted to them.
Analytic differentiation by computer
Authors: Hanson James W. , Caviness Jane Shearin , Joseph Camilla
Published: July 2002

During the past few years a major portion of the work in computer applications has been concentrated in the two closely related fields of automatic programming and symbol manipulation. The results of this effort have been a wealth of new computer languages, a better understanding and definition of the basic principles and problems of symbol manipulation, and a growing body of algorithms and techniques for use in the applications.
Criteria for acceptable abstracts
Authors: Borko Harold
Published: July 2002

Recently, a personal reaction to a published abstract started a study which may lead to criteria for abstracts. This particular abstract seemed inadequate to those who were familiar with the original journal article. This brought up the question of how the adequacy of an abstract is determined. Is it a matter of opinion, or is it a measure of excellence? Assuming it is the latter, are the means for measuring it specified?
Usability analysis with Markov models
Authors: Thimbleby Harold , Cairns Paul , Jones Matt
Published: July 2002

How hard to users to find interactive devices to use to achieve their goals, and how can we get this information early enough to influence design? We show that Markov modeling can obtain suitable measures, and we provide formulas that can be used for a large class of systems. We analyze and consider alternative designs for various real examples. We introduce a “knowledege/usability graph,” which shows the impact of even a smaller amount of knowledge for the user, and the extent to which designers' knowledge may bias their views of usability. Markov models can be built into design tools, and can therefore be made very convenient for designers to utilize. One would hope that in the future, design tools would include such mathematical analysis, and no new design skills would be required to evaluate devices. A particular concern of this paper is to make the approach accessible. Complete program code and all the underlying mathematics are provided in appendices to enable others to replicate and test all results shown.
A generalized user interface for applications programs (II)
Authors: Bass Leonard J.
Published: July 2002

A display-screen management system for user interaction with an arbitrary application program is simple enough so that the end user controls the dialogue and screens yet powerful enough to provide for user specification of screen geometry, input constraints, computation facilities, and display logic—quite independently of the application system.
Role-based access control on the web
Authors: Park Joon S. , Sandhu Ravi , Ahn Gail-Joon
Published: July 2002

Current approaches to access control on the Web servers do not scale to enterprise-wide systems because they are mostly based on individual user identities. Hence we were motivated by the need to manage and enforce the strong and efficient RBAC access control technology in large-scale Web environments. To satisfy this requirement, we identify two different architectures for RBAC on the Web, called
user-pull
and
server-pull
. To demonstrate feasibility, we implement each architecture by integrating and extending well-known technologies such as cookies, X.509, SSL, and LDAP, providing compatibility with current web technologies. We describe the technologies we use to implement RBAC on the Web in different architectures. Based on our experience, we also compare the tradeoffs of the different approaches.
Applications of Ramsey's theorem to decision tree complexity
Authors: Moran Shlomo , Snir Marc , Manber Udi
Published: July 2002

Combinatorial techniques for extending lower bound results for decision trees to general types of queries are presented. Problems that are defined by simple inequalities between inputs, called
order invariant
problems, are considered. A decision tree is called
k-bounded
if each query depends on at most
k
variables. No further assumptions on the type of queries are made. It is proved that one can replace the queries of any
k
-bounded decision tree that solves an order-invariant problem over a large enough input domain with
k
-bounded queries whose outcome depends only on the relative order of the inputs. As a consequence, all existing lower bounds for comparison-based algorithms are valid for general
k
-bounded decision trees, where
k
is a constant.

An Ω(
n
log
n
) lower bound for the element uniqueness problem and several other problems for any
k
-bounded decision tree, such that
k
=
O
(

n
c

) and
c
< 1/2 is proved. This lower bound is tight since there exist
n
1/2
-bounded decision trees of complexity
O
(
n
) that solve the element-uniqueness problem. All the lower bounds mentioned above are shown to hold for nondeterministic and probabilistic decision trees as well.
The world's fastest Scrabble program
Authors: Appel Andrew W. , Jacobson Guy J.
Published: July 2002

An efficient backtracking algorithm makes possible a very fast program to play the SCRABBLE® Brand Crossword Game. The efficiency is achieved by creating data structures before the backtracking search begins that serve both to focus the search and to make each step of the search fast.