bluuebunny/crossref_metadata_2025 huggingface dataset:
Predictor-Corrector Methods of High Order With Improved Stability Characteristics
Authors: Krogh Fred T.
Published: July 2002

Some new predictors are presented for use with the Adams-Moulton correctors of orders 4 through 8. The resulting algorithms have better stability characteristics than the usual ones which employ the Adams Bashforth predictors and at the same time require no additional storage. The regions of absolute and relative stability for the methods mentioned above and for the iterated Adams-Moulton correctors are given. Results obtained using the various methods are compared.
Generalized Single-Ended Counters
Authors: Bailey John S.
Published: July 2002

Conventional shift counters are shown to be a special case of the general class of counters that use single-ended information on all but one bit position of
JK
flip-flops. The resultant class of counters preserves the autocorrelation characteristics necessary for pseudo-random number generation while allowing a saving in the physical mechanization of a given characteristic equation. A companion matrix in canonical form is developed that yields a direct mapping from the characteristic equation to the requisite logic on each flip-flop.
Discrete Analogs for Continuous Filters
Authors: Shaw H.
Published: July 2002

A substitution rule for obtaining discrete analogs for continuous filters is given. Transient responses of filters related by the rule are in exact agreement. Steady-state responses are in close agreement.
A Modification of Davidon's Minimization Method to Accept Difference Approximations of Derivatives
Authors: Stewart G. W.
Published: July 2002

A modification of Davidon's method for the unconstrained minimization of a function of several variables is proposed in which the gradient vector is approximated by differences. The step sizes for the differencing are calculated from information available in the course of the minimization and are chosen to approximately balance off the effects of truncation error and cancellation error. Numerical results and comparisons with other methods are given.
Note Concerning the Algebraic Theory of Automata
Authors: Pickett H. E.
Published: July 2002

If an automaton is strongly connected, all of its automorphisms are regular permutations. It is proved that given any two groups
G
and
H
of regular permutations on finite sets
A
and
B
, respectively, there exists strongly connected automata @@@@ and @@@@ such that
G
and
H
are the automorphisms groups of @@@@ and @@@@, @@@@ × @@@@ is strongly connected and the automorphism group of @@@@ × @@@@ is
G
×
H
. Also it is proved that the reduced semigroup of an automaton is a regular group of permutations iff the automorphism group of @@@@ is regular and @@@@ is strongly connected. Using this result we construct examples where the automorphism groups have the above property for
all
strongly connected automata on
A
and
B
, and other examples where the automorphism group of @@@@ × @@@@ properly contains
G
×
H
.
Decidable and Undecidable Questions About Automata
Authors: Hopcroft J. E. , Ullman J. D.
Published: July 2002

Four types of balloon automata (defined by one- or two-way input and deterministic or nondeterministic finite control) and closed classes of balloon automata were previously defined by the authors. A set of closed classes, one for each of the four types, is called a
family
if the classes use their infinite storage in the same way. The recursiveness and solvability of the emptiness problem for closed classes are investigated in the present paper. It is shown that in many cases the solvability of one of these questions for one closed class in a family implies that some other question are solvable for the closed classes of that family.
On the Independence of Real-Time Definability and Certain Structural Properties of Context-Free Languages
Authors: Rosenberg Arnold L.
Published: July 2002

An operator precedence language which is not real-time definable by any multitple Turing machine is constructed. This strengthens previous results about the existence of unambiguous context-free languages (CFL's) which are not real-time definable. In contrast, a family of CFL's of increasing degree of inherent ambiguity, each real-time definable by a one-tape Turing machine, is exhibited. In fact, an unboundedly ambiguous CFL, also real-time definable by a one-tape Turing machine, is presented. These results are the basis for the assertion that real-time definability of a CFL is independent from each of the structural properties considered.
Analysis of a Drum Input/Output Queue Under Scheduled Operation in a Paged Computer System
Authors: Coffman E. G.
Published: July 2002

Properly scheduling the usage of input output devices is an important aspect of the design of modern multiprogramming systems featuring a paged environment. In this paper magnetic drums in the role of auxiliary memories are studied in the context of these systems. It is the nature of the drum, its usage by the system, and the organization of information on the drum are discussed in the light of current system designs. Mathematical models are then defined such that two extremes in scheduling disciplines are represented in a system in which page requests are assumed to arrive singly and at random. The analysis leads to results for a measure of drum utilization, a generating function for the queue length probabilities in equilibrium, the mean queue length, and the mean waiting time. Finally, the significance of the results is discussed along with some examples.
Nonnormality and Jordan Condition Numbers of Matrices
Authors: Loizou Georghios
Published: July 2002

A lower bound for the departure from normality of an
n
X
n
matrix
A
is given. Furthermore, various inequalities are obtained for certain condition numbers associated with the reduction of
A
to its Jordan canonical form.
Toward Abstract Numerical Analysis
Authors: Miller Webb
Published: July 2002

This paper deals with a technique for proving that certain problems of numerical analysis are numerically unsolvable. So that only methods which are natural for dealing with analytic problems may be presented, notions from recursive function theory have been avoided. Instead, the number of necessary function evaluations is taken as the measure of computational complexity. The role of topological concepts in the study of computability is examined. Last, a topological result is used to prove that a simple initial-value problem is numerically unsolvable.
An Implementation of the Model Elimination Proof Procedure
Authors: Fleisig S. , Loveland D. , Smiley A. K. , Yarmush D. L.
Published: July 2002

The model elimination (ME) and resolution algorithms for mechanical theorem-proving were implemented so as to maximize shared features. The identical data structures and large amount of common programming permit meaningful comparisons when the two programs are run on standard problems. ME does better on some classes of problems, and resolution better on others. The depth-first search strategy used in this ME implementation affects the performance profoundly. Other novel features in the implementation are new control parameters to govern extensions, and modified rules for generating and rejecting chains. The resolution program incorporates unit preference and set-of-support. An appendix reproduces the steps of a machine-derived ME refutation.
A Theorem in the Theory of Compromise Merge Methods
Authors: Kritzinger P. S. , Graham J. W.
Published: July 2002

Let
r
be the total number of cycles required to complete a compromise merge of a given number of initial strings. Define row vectors m

r
-
j

and d

j

whose components represent the number and length respectively of strings at the end of the
j
th cycle of the merge. It is shown in this paper that there are asymptotic approximations to these vectors, which enables one to compute their respective components directly. Consequently, the number of cycles
r
can be computed directly, as in the case of the balanced merge.
A Modified List Technique Allowing Binary Search
Authors: Berman G. , Collin A. W.
Published: July 2002

A modification of linked lists is presented which permits searching almost as efficiently as a pure binary search. The method depends on using consecutive memory locations for consecutive list elements whenever possible.
A Document Storage Method Based on Polarized Distance
Authors: Chien R. T. , Mark E. A.
Published: July 2002

Some elementary mathematical properties of term matching document retrieval systems are developed. These properties are used as a basis for a new file organization technique. Some of the advantages of this new method are (1) the key-to-address transformation is easily determined; (2) the documentary information is stored only once in the file; (3) the file organization allows the use of various matching functions and thresholds; and (4) the dimensionality of the transform is easily expanded to accommodate various sized data bases.
An Algorithm for the Bounded Variable Integer Programming Problem
Authors: Trotter L. E. , Shetty C. M.
Published: July 2002

An algorithm is proposed for the bounded variable pure integer programming problem which treats general integer variables directly in an implicit enumeration procedure closely related to that advanced by Balas and Geoffrion for binary programming problems. Means of obtaining near optimum solutions through a slight modification of the algorithm are discussed. Techniques which use bounds on variables to improve algorithmic efficiency are developed and examined computationally. Further computational results indicate that direct treatment of general integer variables is significantly more effective than binary expansion.
Note on Hopcroft and Tarjan's Planarity Algorithm
Authors: Deo Narsingh
Published: July 2002

Errata are given for “Efficient Planarity Testing” by John Hopcroft and Robert Tarjan [
J. ACM 21
, 4 (Oct. 1974), 549-568].
A Completeness Theorem for Straight-Line Programs with Structured Variables
Authors: Hoffmann Christoph M. , Landweber Lawrence H.
Published: July 2002

A program scheme which models straight-line code admitting structured variables such as arrays, lists, and queues is considered. A set of expressions is associated with a program reflecting the input-output transformations. A basic set of axioms is given and program equivalence is defined in terms of expression equivalence. Program transformations are then defined such that two programs are equivalent if and only if one program can be transformed to the other via the transformations. An application of these results to code optimization is then discussed.
Convergence Estimates for the Distribution of Trailing Digits
Authors: Feldstein Alan , Goodman Richard
Published: July 2002

This paper analyzes the distribution of trailing digits (tail end digits) of positive real floating-point numbers represented in arbitrary base
β
and randomly chosen from a logarithmic distribution. The analysis shows that the
n
th digit for
n
≥ 2 is actually approximately uniformly distributed. The approximation depends upon both
n
and the base
β
. It becomes better as
n
increases, and it is exact in the limit as
n
⇒ ∞. A table of this distribution is presented for various β and
n
, along with a table of the maximum digit by digit deviation Δ of the logarithmic distribution from the uniform distribution. Various asymptotic results for Δ are included. These results have application in resolving open questions of Henrici, of Kaneko and Liu, and of Tsao.
Linear Programming Computational Procedures for Ordinal Regression
Authors: Srinivasan V.
Published: July 2002

The ordinal regression problem is an extension to the standard multiple regression problem in terms of assuming only ordinal properties for the dependent variable (rank order of preferred brands in a product class, academic ranks for students in a class, etc.) while retaining the interval scale assumption for independent (or predictor) variables. The linear programming formulation for obtaining the regression weights for ordinal regression, developed in an earlier paper, is outlined and computational improvements and alternatives which utilize the special structure of this linear program are developed and compared for their computational efficiency and storage requirements. A procedure which solves the dual of the original linear programming formulation by the dual simplex method with upper bounded variables, in addition to utilizing the special structure of the constraint matrix from the point of view of storage and computation, performs the best in terms of both computational efficiency and storage requirements. Using this special procedure, problems with 100 observations and 4 independent variables take less than 1/2 minute, on an average, on the IBM 360/67. Results also show that the linear programming solution procedure for ordinal regression is valid — the correlation coefficient between “true” and predicted values for the dependent variable was greater than .9 for most of the problems tested.
A Syntactic Theory of Message Passing
Authors: Ward Stephen A. , Halstead Robert H.
Published: July 2002

Recent developments by Hewitt and others have stimulated interest in message-passing constructs as an alternative to the more conventional applicative semantics on which most current languages are based. The present work illuminates the distinction between applicative and message-passing semantics by means of the
μ
-calculus, a syntactic model of message-passing systems similar in mechanism to the λ-calculus. Algorithms for the translation of expressions from the λ- to the
μ
-calculus are presented, and differences between the two approaches are discussed.

Message-passing semantics seem particularly applicable to the study of multiprocessing. The
μ
-calculus, through the mechanism of
conduits,
provides a simple model for a limited but interesting class of parallel computations. Multiprocessing capabilities of the
μ
-calculus are illustrated, and multiple-processor implementations are discussed briefly.
Case study: IBM's system/360-370 architecture
Authors: Gifford David , Spector Alfred
Published: July 2002

The architecture of IBM's System/360-370 series of compatible processors is one of the most durable artifacts of the computer age. Through two major revisions of the product line and 23 years of technological change, it has remained a viable and versatile interface between machine and user.
Introduction to the Electronic Symposium on Computer-Supported Cooperative Work
Authors: Mills Kevin L.
Published: July 2002

Computer-supported cooperative work (CSCW) holds great importance and promise for modern society. This paper provides an overview of seventeen papers comprising a symposium on CSCW. The overview also discusses some relationships among the contributions made by each paper, and places those contributions into a larger context by identifying some of the key challenges faced by computer science researchers who aim to help us work effectively as teams mediated through networks of computers. The paper also describes why the promise of CSCW holds particular salience for the U.S military. In the context of a military setting, the paper describes five particular challenges for CSCW researchers. While most of these challenges might seem specific to military environments, many others probably already face similar challenges, or soon will, when attempting to collaborate through networks of computers. To support this claim, the paper includes a military scenario that might hit fairly close to home for many, and certainly for civilian emergency response personnel. After discussing the military needs for collaboration technology, the paper briefly outlines the motivation for a recent DARPA research program along these lines. That program, called Intelligent Collaboration and Visualization, sponsored the work reported in this symposium.
Intermediary Architecture
Authors: Thompson Craig , Pazandak Paul , Vasudevan Venu , Manola Frank , Palmer Mark , Hansen Gil , Bannon Tom
Published: July 2002

This paper describes the
Intermediary Architecture
, a middleware architecture which interposes distributed object services between Web client and server. The architecture extends current Web architectures with a new kind of plug-in, making a new colleciton of Web applications easier to develop. Example services including Web annotations and Web performance monitoring are described.
Parallel RAMs with owned global memory and deterministic context-free language recognition
Authors: Dymond Patrick W. , Ruzzo Walter L.
Published: July 2002

We identify and study a natural and frequently occurring subclass of Concurrent Read, Exclusive Write Parallel Random Access Machines (CREW-PRAMs). Called Concurrent Read,
Owner
Write, or CROW-PRAMS, these are machines in which each global memory location is assigned a unique “owner” processor, which is the only processor allowed to write into it. Considering the difficulties that would be involved in physically realizinga full CREW-PRAM model and demonstrate its stability under several definitional changes. Second, we precisely characterize the power of the CROW-PRAM by showing that the class of languages recognizable by it in time
O
(log n) (and implicity with a polynomial number of processors) is exactly the class LOGDCFL of languages log space reducible to deterministic context-free languages. Third, using the same basic machinery, we show that the recognition problem for deterministic context-free languages can be solved quickly on a deterministic auxilliary pushdown automation having random access to its input tape, a log
n
space work tape, and pushdown store of small maximum height. For example, time
O
(
n
1 + ε
) is achievable with pushdown height
O
(log
2
n
). These result extend and unify work of von Braunmöhl, Cook, Mehlhorn, and Verbeek, Klein and Reif; and Rytter.
A Database Management System for the Federal Courts
Authors: Buchanan Jack R. , Fennell Richard D. , Samet Hanan
Published: July 2002

A judicial systems laboratory has been established and several large-scale information management systems projects have been undertaken within the Federal Judicial Center in Washington, D.C. The newness of the court application area, together with the experimental nature of the initial prototypes, required that the system building tools be as flexible and efficient as possible for effective software design and development. The size of the databases, the expected transaction volumes, and the long-term value of the court records required a data manipulation system capable of providing high performance and integrity. The resulting design criteria, the programming capabilities developed, and their use in system construction are described herein. This database programming facility has been especially designed as a technical management tool for the database administrator, while providing the applications programmer with a flexible database software interface for high productivity.

Specifically, a network-type database management system using SAIL as the data manipulation host language is described. Generic data manipulation verb formats using SAIL's macro facilities and dynamic data structuring facilities allowing in-core database representations have been developed to achieve a level of flexibility not usually attained in conventional database systems.
Power optimization of technology-dependent circuits based on symbolic computation of logic implications
Authors: Bahar R. Iris , Lampe Ernest T. , Macii Enrico
Published: July 2002

This paper presents a novel approach to the problem of optimizing combinational circuits for low power. The method is inspired by the fact that power analysis performed on a technology mapped network gives more realistic estimates than it would at the technology-independent level. After each node's switching activity in the circuit is determined, high-power nodes are eliminated through redundancy addition and removal. To do so, the nodes are sorted according to their switching activity, they are considered one at a time, and learning is used to identify direct and indirect logic implications inside the network. These logic implications are exploited to add gates and connections to the circuit; this may help in eliminating high-power dissipating nodes, thus reducing the total switching activity and power dissipation of the entire circuit. The process is iterative; each iteration starts with a different target node. The end result is a circuit with a decreased switching power. Besides the general optimization algorithm, we propose a new BDD-based method for computing satisfiability and observability implications in a logic network; futhermore, we present heuristic techniques to add and remove redundancy at the technology-dependent level, that is, restructure the logic in selected places without destroying the topology of the mapped circuit. Experimental results show the effectiveness of the proposed technique. On average, power is reduced by 34%, and up to a 64% reduction of power is possible, with a negligible increase in the circuit delay.
Managing stored voice in the Etherphone system
Authors: Terry Douglas B. , Swinehart Daniel C.
Published: July 2002

Thevoice managerin the Etherphone system provides facilities for recording, editing, and playing stored voice in a distributed personal-computing environment. It provides the basis for applications such as voice mail, annotation of multimedia documents, and voice editing using standard text-editing techniques. To facilitate sharing, the voice manager stores voice on a special voice file server that is accessible via the local internet. Operations for editing a passage of recorded voice simply build persistent data structures to represent the edited voice. These data structures, implementing an abstraction calledvoice ropes, are stored in a server database and consist of lists of intervals within voice files. Clients refer to voice ropes solely by reference.Interests, additional persistent data structures maintained by the server, serve two purposes: First, they provide a sort of directory service for managing the voice ropes that have been created. More importantly, they provide a reliable reference-counting mechanism, permitting the garbage collection of voice ropes that are no longer needed. These interests are grouped into classes; for some important classes, obsolete interests can be detected and deleted by a class-specific algorithm that runs periodically.
Law-governed interaction
Authors: Minsky Naftaly H. , Ungureanu Victoria
Published: July 2002

Software technology is undergoing a transition form monolithic systems, constructed according to a single overall design, into conglomerates of semiautonomous, heterogeneous, and independently designed subsystems, constructed and managed by different organizations, with little, if any, knowledge of each other. Among the problems inherent in such conglomerates, none is more serious than the difficulty to
control
the activities of the disparate agents operating in it, and the difficulty for such agents to
coordinate
their activities with each other. We argue that the nature of coordination and control required for such systems calls for the following principles to be satisfied: (1) coordination policies need to be enforced: (2) the enforcement needs to be decentralized; and (3) coordination policies need to be formulated explicitly—rather than being implicit in the code of the agents involved—and they should be enforced by means of a generic, broad spectrum mechanism; and (4) it should be possible to deploy and enforce a policy incrementally, without exacting any cost from agents and activities not subject to it. We describe a mechansim called law-governed interaction (LGI), currently implemented by the Moses toolkit, which has been designed to satisfy these principles. We show that LGI is at least as general as a conventional centralized coordination mechanism (CCM), and that it is more scalable, and generally more efficient, then CCM.
Dynamic verification of operating system decisions
Authors: Fabry R. S.
Published: July 2002

Dynamic verification of a decision implies that every time the decision is made there is a consistency check performed on the decision using independent hardware and software. The dynamic verification of operating system decisions is used on the PRIME system being designed and constructed at the University of California, Berkeley. PRIME is an experimental time-sharing system which is to have the properties of continuous availability, data privacy, and cost effectiveness. The technique of dynamic verification allows the construction of an operating system which does not make certain decisions improperly even in the presence of a single hardware or software fault. Furthermore, multiple faults lead to unreliable operation only if the faults happen to reinforce each other. On PRIME, dynamic verification is used to ensure that one user's information cannot become available to another user gratuitously even in the presence of a single hardware or software fault. The amount of additional hardware and software required for dynamic verification can be modest.
On generation of test problems for linear programming codes
Authors: Charnes A. , Raike W. M. , Stutz J. D. , Walters A. S.
Published: July 2002

Users of linear programming computer codes have realized the necessity of evaluating the capacity, effectiveness, and accuracy of the solutions provided by such codes. Large scale linear programming codes at most installations are assumed to be generating correct solutions without ever having been “bench-marked” by test problems with known solutions. The reason for this failure to adequately test the codes is that rarely are there large problems with known solutions readily available. This paper presents a theoretical justification and an Illustrative implementation of a method for generating linear programming test problems with known solutions. The method permits the generation of test problems that are of arbitrary size and have a wide range of numerical characteristics.
Audit trail compaction for database recovery
Authors: Kaunitz John , van Ekert Louis
Published: July 2002

Total elapsed recovery time from disk-based database corruption can be shortened by reprocessing the audit trail off-line and thereby avoiding excessive resource utilization penalties. Using a bit map, the audit trail is compacted by eliminating irrelevant or superseded records. The compacted trail is then partitioned, and the partitions are processed in parallel.
Triform programs
Authors: Crockett Dan W.
Published: July 2002

The concept that three process functions—initialization, production, and completion—and a separate supervisory control function are sufficient to describe the execution of a program is the basis for Triform Program design. Triform programs are composed of modules arranged in a trifurcate tree structure with each branch devoted to the performance of one and only one of the process functions. The root of the program tree is a control module which supervises process-function execution. Such trifurcate tree structures are shown to be minimum complexity structures.
Quo Vadimus
: computer science in a decade
Authors: Traub J. F.
Published: July 2002

A panel discussion was held during the third biennial meeting of chairmen of Ph.D.-granting computer science departments in June, 1978 at Snowbird, Utah, a meeting sponsored by the Computer Science Board. Invitees from industry and government were also present. A report was prepared from tapes made of the discussion (Department of Computer Science, Carnegie-Mellon University: Report #CMU-CS-80-127, June 1980). It contained all the prepared statements of the panelists, lightly edited, and the panelists' discussion in its entirety. A selection of the audience discussion was also included, rather heavily edited. The following presentation is derived from that report.
Recursive data structures in APL
Authors: Gull W. E. , Jenkins M. A.
Published: July 2002

A mathematical study of three approaches for defining nested arrays in APL is presented. Theorems exhibiting the relationships between the definitional systems are given and illustrated through graph representations. One of the approaches is used to define an APL array to be a recursive data structure equivalent to a tree structure in which all data is stored at the leaves as homogeneous arrays of numbers and characters. An extension of APL is proposed that includes new primitive functions to manipulate the nesting level of arrays and new operators to assist in the construction of data-driven algorithms.
Management utilization of computers in American local governments
Authors: Dutton William H. , Kraemer Kenneth L.
Published: July 2002

Traditional concepts of management information systems (MIS) bear little relation to the information systems currently in use by top management in most US local governments. What exists is management-oriented computing, involving the use of relatively unsophisticated applications. Despite the unsophisticated nature of these systems, management use of computing is surprisingly common, but also varied in its extent among local governments. Management computing is most prevalent in those governments with professional management practices where top management is supportive of computing and tends to control computing decisions and where department users have less control over design and implementation activities. Finally, management computing clearly has impacts for top managers, mostly involving improvements in decision information.
A technique for isolating differences between files
Authors: Heckel Paul
Published: July 2002

A simple algorithm is described for isolating the differences between two files. One application is the comparing of two versions of a source program or other file in order to display all differences. The algorithm isolates differences in a way that corresponds closely to our intuitive notion of difference, is easy to implement, and is computationally efficient, with time linear in the file length. For most applications the algorithm isolates differences similar to those isolated by the longest common subsequence. Another application of this algorithm merges files containing independently generated changes into a single file. The algorithm can also be used to generate efficient encodings of a file in the form of the differences between itself and a given “datum” file, permitting reconstruction of the original file from the diference and datum files.
A language extension for expressing constraints on data access
Authors: Jones Anita K. , Liskov Barbara H.
Published: July 2002

Controlled sharing of information is needed and desirable for many applications and is supported in operating systems by access control mechanisms. This paper shows how to extend programming languages to provide controlled sharing. The extension permits expression of access constraints on shared data. Access constraints can apply both to simple objects, and to objects that are components of larger objects, such as bank account records in a bank's data base. The constraints are stated declaratively, and can be enforced by static checking similar to type checking. The approach can be used to extend any strongly-typed language, but is particularly suitable for extending languages that support the notion of abstract data types.
Detection of logical errors in decision table programs
Authors: Ibramsha M. , Rajaraman V.
Published: July 2002

In this paper an algorithm to detect logical errors in a limited-entry decision table and in loop-free programs with embedded decision tables is developed. All the conditions in the decision tables are assumed to be inequalities or equalities relating linear expressions. It is also assumed that actions in a decision table are linear in variables which occur in the condition stub of the decision table (or tables) to which control is transferred from the table. The algorithm is based on determining whether a set of linear inequalities has or does not have a solution. The algorithm described in the paper is implemented in Fortran IV.
Regular right part grammars and their parsers
Authors: LaLonde Wilf R.
Published: July 2002

This paper introduces an alternative to context-free grammars called regular right part (RRP) grammars, which resemble PASCAL syntax diagrams. Formally, RRP grammars have production right parts, which are nondeterministic finite state machines (FSMs), and, as a special case, regular expression, since these can be converted to FSMs. RRP grammars describe the syntax of programming languages more concisely and more understandably than is possible with CF grammars. Also introduced is a class of parsers, RRP LR(m, k) parsers, which includes the CF LR(k) parsers and provides the same advantages. Informally, an RRP LR(m, k) parser can determine the right end of each handle by considering at most k symbols to the right of the handle and the left end, after the right end has been found, by considering at most m symbols to the left of the handle. A mechanism for determining the left end is required because there is no bound on the length of the handle.
Faster retrieval from context trees
Authors: Wegbreit Ben
Published: July 2002

Context trees provide a convenient way of storing data which is to be viewed as a hierarchy of contexts. This note presents an algorithm which improves on previous context tree retrieval algorithms. It is based on the observation that in typical uses context changes are infrequent relative to retrievals, so that data can be cached to speed up retrieval. A retrieval is started from the position of the previous retrieval and auxiliary structures are built up to make the search rapid. Algorithms for addition and deletion of data and for garbage collection are outlined.
A precise numerical analysis program
Authors: Aberth Oliver
Published: July 2002

A description is given of a program for computing the solution to a small number of standard numerical analysis problems to any specified accuracy, up to a limit of 2000 correct decimal places. Each computed number is bounded in an interval with a multiple precision midpoint. Arithmetic operations involving these numbers are executed according to interval arithmetic concepts, with non-significant digits automatically discarded. Details are supplied of problem specification and problem computation.
MUSE
Authors: McCalla Gordon I. , Sampson Jeffrey R.
Published: July 2002

MUSE is a computer model for natural language processing, based on a semantic memory network like that of Quillian's TLC. MUSE, from a Model to Understand Simple English, processes English sentences of unrestricted content but somewhat restricted format. The model first applies syntactic analysis to eliminate some interpretations and then employs a simplified semantic intersection procedure to find a valid interpretation of the input. While the semantic processing is similar to TLC's, the syntactic component includes the early use of parse trees and special purpose rules. The “relational triple” notation used during interpretation of input is compatible with MUSE's memory structures, allowing direct verification of familiar concepts and the addition of new ones. MUSE also has a repertoire of actions, which range from editing and reporting the contents of its own memory to an indirect form of question answering. Examples are presented to demonstrate how the model interprets text, resolves ambiguities, adds information to memory, generalizes from examples, and performs various actions.
Computers and society
Authors: Horowitz E. , Morgan H. L. , Shaw A. C.
Published: July 2002

The purpose of this paper is to describe a course concerned with both the effects of computers on society and the responsibilities of computer scientists to society. The impact of computers is divided into five components: political, economic, cultural, social, and moral; the main part of the paper defines each component and presents examples of the relevant issues. In the remaining portions the possible formats for such a course are discussed, a topic by topic outline is given, and a selected set of references is listed. It is hoped that the proposal will make it easier to initiate courses on this subject.
Some approaches to best-match file searching
Authors: Burkhard W. A. , Keller R. M.
Published: July 2002

The problem of searching the set of keys in a file to find a key which is closest to a given query key is discussed. After “closest,” in terms of a metric on the the key space, is suitably defined, three file structures are presented together with their corresponding search algorithms, which are intended to reduce the number of comparisons required to achieve the desired result. These methods are derived using certain inequalities satisfied by metrics and by graph-theoretic concepts. Some empirical results are presented which compare the efficiency of the methods.
A deductive question-answerer for natural language inference
Authors: Schwarcz Robert M. , Burger John F. , Simmons Robert F.
Published: July 2002

The question-answering aspects of the Protosynthex III prototype language processing system are described and exemplified in detail. The system is written in LISP 1.5 and operates on the Q-32 time-sharing system. The system's data structures and their semantic organization, the deductive question-answering formalism of relational properties and complex-relation-forming operators, and the question-answering procedures which employ these features in their operation are all described and illustrated. Examples of the system's performance and of the limitations of its question-answering capability are presented and discussed. It is shown that the use of semantic information in deductive question answering greatly facilitates the process, and that a top-down procedure which works from question to answer enables effective use to be made of this information. It is concluded that the development of Protosynthex III into a practically useful system to work with large data bases is possible but will require changes in both the data structures and the algorithms used for question answering.
Mixed solutions for the deadlock problem
Authors: Howard John H.
Published: July 2002

Mixtures of detection, avoidance, and prevention provide more effective and practical solutions to the deadlock problem than any one of these alone. The individual techniques can be tailored for subproblems of resource allocation and still operate together to prevent deadlocks. This paper presents a method, based on the concept of the hierarchical operating system, for constructing appropriate mixtures and suggests appropriate subsystems for the most frequently occurring resource allocation problems
Curriculum recommendations for graduate professional programs in information systems
Authors: McFarlan F. Warren , Nolan Richard L.
Published: July 2002

An addendum to the Report of the ACM Curriculum Committee on Computer Education for Management is proposed. The proposed addendum is to include in the curriculum a course on Information Systems Administration. It is important for two reasons: (1) the systems designer must understand the administrative framework in which he must operate to work effectively, and (2) an important objective of the curriculum recommendations is to prepare the future manager of the computer activity. It is felt that the importance of these two reasons justifies the addition of the recommended course. The course is outlined in the format of the original report.
Using page residency to select the working set parameter
Authors: Prieve Barton G.
Published: July 2002

Denning's method for selecting the working set parameter, which uses interreference intervals, is examined. Several omissions in his model are noted, and new assumptions are introduced to overcome these omissions. Using this modified model, Denning's results on page residency are rederived and reconsidered for selecting the working set parameter.
A programmmer training project
Authors: Bernstein Arthur J.
Published: July 2002

A project is described whose purpose is to train selected black residents of the Albany-Schenectady area in computer programming and arrange for jobs for them in the computer field. Both the organization and curriculum of the course are discussed.
User program measurement in a time-shared environment
Authors: Nemeth Alan G. , Dovner Paul D.
Published: July 2002

A general discussion of the measurement of software systems is followed by a description of a hardware and software scheme for measuring user programs in a time-shared environment. The TX-2 computer at MIT Lincoln Laboratory was used for the implementation of such a system and the characteristics of this implementation are reported. A scenario showing the system in use is presented. Finally, it is shown how other time-sharing systems may provide similar measuring facilities.
Computing polynomial resultants
Authors: Ku S. Y. , Adler R. J.
Published: July 2002

Algorithms for computing the resultant of two polynomials in several variables, a key repetitive step of computation in solving systems of polynomial equations by elimination, are studied. Determining the best algorithm for computer implementation depends upon the extent to which extraneous factors are introduced, the extent of propagation of errors caused by truncation of real coeffcients, memory requirements, and computing speed. Preliminary considerations narrow the choice of the best algorithm to Bezout's determinant and Collins' reduced polynomial remainder sequence (p.r.s.) algorithm. Detailed tests performed on sample problems conclusively show that Bezout's determinant is superior in all respects except for univariate polynomials, in which case Collins' reduced p.r.s. algorithm is somewhat faster. In particular Bezout's determinant proves to be strikingly superior in numerical accuracy, displaying excellent stability with regard to round-off errors. Results of tests are reported in detail.
An algorithm for solving a special class of tridiagonal systems of linear equations
Authors: Rose Donald J.
Published: July 2002

An algorithm is presented for solving a system of linear equations
Bu
=
k
where
B
is tridiagonal and of a special form. This form arises when discretizing the equation - d/d
x
(
p
(
x
)
du
/
dx
) =
k
(
x
) (with appropriate boundary conditions) using central differences. It is shown that this algorithm is almost twice as fast as the Gaussian elimination method usually suggested for solving such systems. In addition, explicit formulas for the inverse and determinant of the matrix
B
are given.
Programming Languages: A general purpose graphic language
Authors: Kulsrud H. E.
Published: July 2002

Interactive use of computers with graphic terminals will permit many new problems to be solved using machines. In order to handle a variety of applications, it is expedient to develop a general purpose graphic language that is useful on a number of graphic devices. A system has been designed to produce such a language quickly and cheaply. A model graphic language which has been developed with the system is presented.
Automatic dimensioning
Authors: Klerer Melvin , May Jack
Published: July 2002

Examples of algorithms that will accomplish automatic storage reservation without the need for explicit array declarations are described.
An application of FORMAC
Authors: Neidleman L. D.
Published: July 2002

A nonlinear circuit analysis problem is stated and the way in which it was solved using FORMAC is indicated. The solution of the problem using FORMAC was notable since several other methods that were tried failed. The problem is straightforward (although untenable by hand) but nevertheless involved an elaborate use of the FORMAC language. The program was fairly large and utilized practically every command. In particular, it made extensive use of the PART command. Several tricks were necessary in order to circumvent some of the shortcomings of the FORMAC system.

This paper is more concerned with the use of programming techniques in FORMAC than with the actual engineering problem, although readers may be interested in the problem because it is stated in a general (mathematical) sense and could be of interest in areas other than circuit analysis.
A general business-oriented language based on decision expressions
Authors: Lombardi Lionello A.
Published: July 2002

The structure of a digital computer programming language which covers a wide class of business and file processing applications is presented. Such a structure, based on identifying and incorporating into a compiler the aspects common to all processes of such class, permits writing extremely compact programs, even for comparatively complex applications, in terms of tables of control expressions which express only information characteristic of the particular application. Furthermore, local changes of a process (e.g. changes affecting only one of the output files involved) can be effected by local modifications in the program (e.g. modification of only one entry of the tables). This structure also allows for inexpensive preparation of loading-speed compilers which translate the source programs into efficient machine codes.

The approach adopted here departs from conventional mechanical language design philosophies. It stresses the structural analysis of the class of processes to be represented in the languages, as opposed to emphasizing formal (i.e., contents-independent) syntactical definitions. It relies exclusively on nonprocedural representation of processes as sets (tables) of relations between data and results (there are no control statements such as GO TO, etc.), instead of using procedure descriptions (which are one-to-one translations of flowcharts). Here an invariant pattern of procedure is identified as characteristic of the class of all batch file processes.
A new approach to developing and implementing eager database replication protocols
Authors: Kemme Bettina , Alonso Gustavo
Published: July 2002

Database replication is traditionally seen as a way to increase the availability and performance of distributed databases. Although a large number of protocols providing data consistency and fault-tolerance have been proposed, few of these ideas have ever been used in commercial products due to their complexity and performance implications. Instead, current products allow inconsistencies and often resort to centralized approaches which eliminates some of the advantages of replication. As an alternative, we propose a suite of replication protocols that addresses the main problems related to database replication. On the one hand, our protocols maintain data consistency and the same transactional semantics found in centralized systems. On the other hand, they provide flexibility and reasonable performance. To do so, our protocols take advantage of the rich semantics of group communication primitives and the relaxed isolation guarantees provided by most databases. This allows us to eliminate the possibility of deadlocks, reduce the message overhead and increase performance. A detailed simulation study shows the feasibility of the approach and the flexibility with which different types of bottlenecks can be circumvented.
A note on some compiling algorithms
Authors: Anderson James P.
Published: July 2002

Two compiling generators for arithmetic expressions are discussed: one presently in use in an experimental compiler, and an improvement suggested by K. Speierman of Burroughs.
Closed form solutions to simultaneous buffer insertion/sizing and wire sizing
Authors: Chu Chris , Wong D. F.
Published: July 2002

In this paper, we consider the delay minimization problem of an
interconnect wire by simultaneously considering buffer insertion, buffer sizing and wire sizing. We consider three cases, namely using no buffer (i.e., wire sizing alone), using a given number of buffers, and using the optimal number of buffers. We provide elegant closed form optimal solutions for all three problems. These closed form solutions are useful in early stages of the VLSI design flow such as logic synthesis and floorplanning.