bluuebunny/crossref_metadata_2025 huggingface dataset:
Strong loss tolerance of electronic coin systems
Authors: Pfitzmann Birgit , Waidner Michael
Published: July 2002

Untraceable electronic cash means prepaid digital payment systems, usually with offline payments, that protect user privacy. Such systems have recently been given considerable attention by both theory and development projects. However, in most current schemes, loss of a user device containing electronic cash implies a loss of money, just as with real cash. In comparison with credit schemes, this is considered a serious shortcoming. This article shows how untraceable electronic cash can be made loss tolerant, i.e., how the monetary value of the lost data can be recovered. Security against fraud and preservation of privacy are ensured; strong loss tolerance means that not even denial of recovery is possible. In particular, systems based on electronic coins are treated. We present general design principles and options and their instantiation in one concrete payment system. The measures are practical.
Working-memory failure in phone-based interaction
Authors: Huguenard Brian R. , Lerch F. Javier , Junker Brian W. , Patz Richard J. , Kass Robert E.
Published: July 2002

This article investigates working-memory (WM) failure in phone-based interaction (PBI). We used a computational model of phone-based interaction (PBI USER) to generate predictions about the impact of three factors on WM failure:PBI features (i.e. menu structure), individual differences (i.e., WM capacity), and task characteristics (i.e., number of tasks). Our computational model stipulates that both the storage
and
the processing of information contribute to WM failure. In practical terms the model and the empirical results indicate that, contrary to guidelines for the design of phone-based interfaces, deep menu hierarchies (no more than three options per menu) do not reduce WM error rates in PBI. At a more theoretical level, the study shows that the use of a computational model in HCI research provides a systematic approach for explaining complex empirical results.
Combining constructive and equational geometric constraint-solving techniques
Authors: Joan-Arinyo R. , Soto-Riera A.
Published: July 2002

In the past few years, there has been a strong trend towards developing parametric, computer-aided design systems based on geometric constraint solving. An effective way to capture the design intent in these systems is to define relationships between geometric and technological variables. In general, geometric constraint solving including functional relationships requires a general approach and appropriate techniques to achieve the expected functional capabilities. This work reports on a hybrid method that combines two geometric constraint solving techniques: constructive and equational. The hybrid solver has the capability of managing functional relationships between dimension variables and variables representing conditions external to the geometric problem. The hybrid solver is described as a rewriting system and is shown to be correct.
Schema analysis for database restructuring
Authors: Navathe Shamkant B.
Published: July 2002

The problem of generalized restructuring of databases has been addressed with two limitations: first, it is assumed that the restructuring user is able to describe the source and target databases in terms of the implicit data model of a particular methodology; second, the restructuring user is faced with the task of judging the scope and applicability of the defined types of restructuring to his database implementation and then of actually specifying his restructuring needs by translating them into the restructuring operations on a foreign data model. A certain amount of analysis of the logical and physical structure of databases must be performed, and the basic ingredients for such an analysis are developed here. The distinction between hierarchical and nonhierarchical data relationships is discussed, and a classification for database schemata is proposed. Examples are given to illustrate how these schemata arise in the conventional hierarchical and network systems. Application of the schema analysis methodology to restructuring specification is also discussed. An example is presented to illustrate the different implications of restructuring three seemingly identical database structures.
Sequentiality and prefetching in database systems
Authors: Smith Alan Jay
Published: July 2002

Sequentiality of access is an inherent characteristic of many database systems. We use this observation to develop an algorithm which selectively prefetches data blocks ahead of the point of reference. The number of blocks prefetched is chosen by using the empirical run length distribution and conditioning on the observed number of sequential block references immediately preceding reference to the current block. The optimal number of blocks to prefetch is estimated as a function of a number of “costs,” including the cost of accessing a block not resident in the buffer (a miss), the cost of fetching additional data blocks at fault times, and the cost of fetching blocks that are never referenced. We estimate this latter cost, described as memory pollution, in two ways. We consider the treatment (in the replacement algorithm) of prefetched blocks, whether they are treated as referenced or not, and find that it makes very little difference. Trace data taken from an operational IMS database system is analyzed and the results are presented. We show how to determine optimal block sizes. We find that anticipatory fetching of data can lead to significant improvements in system operation.
Time-Shared Computer Operations With Both Interarrival and Service Times Exponential
Authors: Krishnamoorthi B. , Wood Roger C.
Published: July 2002

The concept of time-shared computer operations is briefly described and a model of a time-sharing system is proposed, based on the assumption that both interarrival and service times possess an exponential distribution. Although the process described by this model is non-Markovian, an imbedded Markov chain is analyzed by exploiting the fact that the instants of completion of a “quantum” of service are regeneration points. It is shown that user congestion possesses a limiting distribution, and the method of generating functions is used to derive this distribution. The concept of cycle time is discussed and two measures of cycle time developed for a scheduling discipline employing a single queue. Finally, a number of numerical examples are presented to illustrate the effect of the system parameters upon user congestion, system response time and computer efficiency.
The Perspective Representation of Functions of Two Variables
Authors: Kubert B. , Szabo J. , Giulieri S.
Published: July 2002

A perspective transformation is developed whereby an object in space as viewed from an arbitrary point can be projected into a plane and plotted. Families of curves which can be used to define such an object are discussed and examples are given. An algorithm which eliminates the plotting of hidden portions of the object is discussed.
The String-to-String Correction Problem
Authors: Wagner Robert A. , Fischer Michael J.
Published: July 2002

The
string-to-string correction problem
is to determine the distance between two strings as measured by the minimum cost sequence of “edit operations” needed to change the one string into the other. The edit operations investigated allow changing one symbol of a string into another single symbol, deleting one symbol from a string, or inserting a single symbol into a string. An algorithm is presented which solves this problem in time proportional to the product of the lengths of the two strings. Possible applications are to the problems of automatic spelling correction and determining the longest subsequence of characters common to two strings.
Information Content of Programs and Operation Encoding
Authors: Hehner Eric C. R.
Published: July 2002

The problem of determining the minimum representation of programs for execution by a computer is considered. The methods of measuring space requirements suggest practical methods for encoding programs and for designing machine languages. An analysis of the operation portion of instructions finds that the 47 operation codes used by a well-known compiler require, on average, fewer than two bits each.
Power-delay optimizations in gate sizing
Authors: Sapatnekar Sachin S. , Chuang Weitong
Published: July 2002

The problem of power-delay tradeoffs in transistor sizing is examined using a nonlinear optimization formulation. Both the dynamic and the short-circuit power are considered, and a new modeling technique is used to calculate the short-circuit power. The notion of transition density is used, with an enhancement that considers the effect of gate delays on the transition density. When the short-cuircuit power is neglected, the minimum power circuit is idential to the minimum area circuit. However, under our more realistic models, our experimental results on several circuits show that the minimum power circuit is not necessarily the same as the minimum area circuit.
Computing in the home: shifts in the time allocation patterns of households
Authors: Vitalari Nicholas P. , Venkatesh Alladi , Gronhaug Kjell
Published: July 2002

An empirical study of 282 users of home computers was conducted to explore the relationship between computer use and shifts in time allocation patterns in the household. Major changes in time allocated to various activities were detected. Prior experience with computers (i.e., prior to purchase of the home computer) was found to have a significant impact on the time allocation patterns in the household. The study provides evidence that significant behavior changes can occur when people adopt personal computers in their homes.
Algorithm 803
Authors: Ward William A.
Published: July 2002

Macro processors have been in the computing tool chest since the late 1950's. Their use, though perhaps not what it was in the heyday of assembly language programming, is still widespread. In the past, producing a full-featured macro processor has required significant effort, similar to that required to implement the front-end to a compiler augmented by appropriate text substitution capabilities. The tool described here adopts a different approach. The text containing macro definitions and substitutions is, in a sense, “compiled” to produce a program, and this program must then be executed to produce the final output.
Tight bounds for
k
-set agreement
Authors: Chaudhuri Soma , Erlihy Maurice , Lynch Nancy A. , Tuttle Mark R.
Published: July 2002

We prove tight bounds on the time needed to solve
k-set agreement
. In this problem, each processor starts with an arbitrary input value taken from a fixed set, and halts after choosing an output value. In every execution, at most
k
distinct output values may be chosen, and every processor's output value must be some processor's input value. We analyze this problem in a synchronous, message-passing model where processors fail by crashing. We prove a lower bound of ⌊f/k⌋+1 degree of coordination required, and the number of faults tolerated, even in idealized models like the synchronous model. The proof of this result is interesting because it is the first to apply topological techniques to the synchronous model.
Double-precision square root for the CDC-3600
Authors: Cody W. J.
Published: July 2002

In January of 1960, the late Hans J. Maehly completed a summary of approximations to the elementary functions for the CDC-1604 computer. The approximations and techniques suggested by Maehly are equally applicable to the second large computer in the CDC line, the 3600. Unlike the 1604, however, the 3600 has built-in double-precision floating-point arithmetic. The present work, largely inspired by the successes of Maehly and his associates, concerns the extension of one of Maehly's ideas to a double-precision subroutine for the 3600.
Integer and signed constants in ALGOL
Authors: Petrone L. , Vandoni C. E.
Published: July 2002

A few remarks are given on the relations between syntax and semantics in the programming languages.

The aim is to point out that, it is true that the grammar of a contex-free language should be conceived not only as a strings-generating device but also as a method for expressing a meaning, then the grammar of ALGOL is open to some criticism.
A note on the calculation of average working set size
Authors: Slutz D. R. , Traiger I. L.
Published: July 2002

Finite-length reference string of arbitrary structure are considered, and an exact expression for average working set size in terms of “corrected” interreference interval statistics is derived. An example is discussed; upper and lower bounds are obtained; and the average working set size function is shown to be efficiently obtained for a set of page sizes, in a single pass of the reference string.

This work follows the developments of a paper by Denning and Schwartz, who consider infinite-length reference strings which satisfy certain statistical properties and who derive an expression relating the asymptotic average working set size to the asymptotic missing page rate function under working set replacement.
Table Lookup Techniques
Authors: Price C. E.
Published: July 2002

Consideration is given to the basic methodology for table searching in computer programming. Only static tables are treated, but references are made to techniques for handling dynamic tables. Methods described are: sequential search, merge search, binary search, estimated entry, and direct entry. The rationale of key transformation is discussed, with some consideration of methods of “hash addressing.” A general guide to technique selection is given in conclusion.
Monte Carlo debugging
Authors: Bell R. Charles
Published: July 2002

Monte Carlo debugging, which has been relied upon for some applications at the author's data center, is briefly discussed with the presentation of some guidelines.
Comparing two microcomputer operating systems
Authors: Pechura Michael A.
Published: July 2002

Two moderate operating systems are compared, with the intent to demonstrate how each may satisfy the needs of a different set of users. The clear superiority of either systems does not emerge, but rather a difference in “design philosophy.” A method for comparing other similar systems is demonstrated.
Speeding up an overrelaxation method of division in Radix-2

n

machine
Authors: Asai Hitohisa , Cheng C. K.
Published: July 2002

For normalized floating point division, digital computers can take advantage of a division process that uses an iterative multiplying operation instead of repeated subtractions. An improvement of this division process by using accelerating constants in the overrelaxation has previously been proposed. Multiplication by a chosen accelerating constant accelerates the process of generating accurate digits of a quotient in division. We propose a further improvement by generalizing the accelerating constants in the overrelaxation method. Two benefits resulting from this improvement promise to yield faster division in digital computers.
From Washington
Authors: Steier Rosalie
Published: July 2002

The National Science Foundation's Advisory Committee for Advanced Scientific Computing Resources was formed to provide leadership for large-scale scientific computing throughout the United States. Consisting of 15 members representing universities, industry, and national laboratories, the Committee held its first meeting in January 1984. A summary of the meeting issued by Chairman Neal F. Lane of Rice University makes the following points.
A large font virtual terminal interface
Authors: Glinert Ephraim P.
Published: July 2002

A large font software interface running under UNIX
1
is of great assistance to the severely visually impaired in the interactive use of computers. The interface, which functions as a
virtual terminal
as far as other processes are concerned, displays all characters (both user and system generated) at user-selectable degrees of magnification, yet is compatible with any standard CRT
/
keyboard terminal
.
A null-object detection algorithm for constructive solid geometry
Authors: Tilove Robert B.
Published: July 2002

Constructive solid geometry
(
CSG
)
is the primary scheme used for representing solid objects in many contemporary solid modeling systems. A CSG representation is a binary tree whose nonterminal nodes represent Boolean operations and whose terminal nodes represent primitive solids. This paper deals with algorithms that operate directly on CSG representations to solve two computationally difficult geometric problems—null-object detection
(
NOD
)
and same-object detection
(
SOD
).
The paper also shows that CSG trees representing null objects may be reduced to null trees through the use of a new concept called primitive redundancy, and that, on average, tree reduction can be done efficiently by a new technique called spatial localization. Primitive redundancy and spatial localization enable a single complex instance of NOD to be converted into a number of simpler subproblems and lead to more efficient algorithms than those previously known.
Pracniques: coordinated text and tranperiences
Authors: Bemer R. W.
Published: July 2002

An economical method of producing both hard copy and projection forms of text, without duplication of effort.
A critque of the stage hypothesis
Authors: Benbasat Izak , Dexter Albert S. , Drury Donald H. , Goldstein Robert C.
Published: July 2002

The stage hypothesis on the assimilation of computing technology provides one of the most popular models for describing and managing the growth of administrative information systems. Despite little formal evidence of its reliability or robustness, it has achieved a high level of acceptance among practitioners. We describe and summarize the findings of seven empirical studies conducted during the past six years that tested various hypotheses derived from this model. The accumulation of evidence from these studies casts considerable doubt on the validity of the stage hypothesis as an explanatory structure for the growth of computing in organizations.
Visibility aspects of programmed dynamic data structures
Authors: Madhavji Nazim H.
Published: July 2002

Unlike static structures, dynamic Pascal-like data structures often suffer visibility problems due to the unrestricted use of the general pointer mechanism. By classifying these structures and identifying the different kinds of pointers, a methodology is proposed for achieving improved visibility.
Building a user-derived interface
Authors: Good Michael D. , Whiteside John A. , Wixon Dennis R. , Jones Sandra J.
Published: July 2002

Many human-computer interfaces are designed with the assumption that the user must adapt to the system, that users must be trained and their behavior altered to fit a given interface. The research presented here proceeds from the alternative assumption: Novice behavior is inherently sensible, and the computer system can be made to adapt to it. Specifically, a measurably easy-to-use interface was built to accommodate the actual behavior of novice users. Novices attempted an electronic mail task using a command-line interface containing no help, no menus, no documentation, and no instruction. A hidden operator intercepted commands when necessary, creating the illusion of an interactive session. The software was repeatedly revised to recognize users' new commands; in essence, the interface was derived from user behavior. This procedure was used on 67 subjects. The first version of the software could recognize only 7 percent of all the subjects' spontaneously generated commands; the final version could recognize 76 percent of these commands. This experience contradicts the idea that user input is irrelevant to the design of command languages. Through careful observation and analysis of user behavior, a mail interface unusable by novices evolved into one that let novices do useful work within minutes.
A simple method for generating gamma variables
Authors: Marsaglia George , Tsang Wai Wan
Published: July 2002

We offer a procedure for generating a gamma variate as the cube of a suitably scaled normal variate. It is fast and simple, assuming one has a fast way to generate normal variables. In brief: generate a normal variate
x
and a uniform variate
U
until In (
U
)<0.5
x
2
+
d
-
dv
+
d
ln(
v
), then return
dv
. Here, the gamma parameter is α ≥ 1, and
v
= (1 +
x
/ *** with
d
= α - 1/3. The efficiency is high, exceeding 0.951, 0.981, 0.992, 0.996 at α = 1,2,4,8. The procedure can be made to run faster by means of a simple squeeze that avoids the two logarithms most of the time; return
dv
if
U
< 1-0.0331
x
4
. We give a short C program for any α ≥ 1, and show how to boost an α <1 into an α > 1. The gamma procedure is particularly fst for C implementation if the normal variate is generated in-line, via the #define feature. We include such an inline version, based on our ziggurat method. With it, and an inline uniform generator, gamma variates can be produced in 400MHz CPUs at better than 1.3 million per second, with the parameter α changing from call to call.
Programming pearls: Writing correct programs
Authors: Bentley Jon
Published: July 2002

In the late 1960s people were talking about the promise of programs that verify the correctness of other programs. Unfortunately, it is now the middle of the 1980s, and, with precious few exceptions, there is still little more than talk about automated verification systems. Despite unrealized expectations, however, the research on program verification has given us something far more valuable than a black box that gobbles programs and flashes “good” or “bad”—we now have a fundamental understanding of computer programming.

The purpose of this column is to show how that fundamental understanding can help programmers write correct programs. But before we get to the subject itself, we must keep it in perspective. Coding skill is just one small part of writing correct programs. The majority of the task is the subject of the three previous columns: problem definition, algorithm design, and data structure selection. If you perform those tasks well, then writing correct code is usually easy.
Reducing the retrieval time of hashing method by using predictors
Authors: Nishihara Seiichi , Ikeda Katsuo
Published: July 2002

Many methods for resolving collisions in hashing techniques have been proposed. They are classified into two main categories: open addressing and chaining. In this paper, other methods are presented that are intermediate between the two categories. The basic idea of our methods is the use of one or more predictors reserved per cell instead of a link field as in the chaining method. The predictors are used to maintain loose synonym chains. After describing the methods, the efficiencies are estimated theoretically and verified experimentally. In comparison with the chaining method, we prove that our methods significantly reduce the average number of probes necessary to retrieve a key without expending extra space.
Reducing dictionary size by using a hashing technique
Authors: Dodds D. J.
Published: July 2002

Peterson [3] described a variety of techniques to implement a spelling checker for plain-language documents and discussed the central importance of the structure and size of the dictionary used by such a program. The technique presented here can produce a compact, easily accessed and modified dictionary. This is done by exploiting two characteristics of the spelling checker: the sole use of the dictionary is to determine whether given strings are, or are not, in the dictionary; and a small, but nonzero probability of error is acceptable in many applications. Many other types of programs have similar characteristics and could use this concept equally well.
Algorithms for computing the volume and other integral properties of solids. II. A family of algorithms based on representation conversion and cellular approximation
Authors: Lee Yong Tsui , Requicha Aristides A. G.
Published: July 2002

This paper discusses a family of algorithms for computing the volume, moments of inertia, and other integral properties of geometrically complex solids, e.g. typical mechanical parts. The algorithms produce approximate decompositions of solids into cuboid cells whose integral properties are easy to compute.

The paper focuses on versions of the algorithms which operate on solids represented by Constructive Solid Geometry (CSG), i.e., as set-theoretical combinations of primitive solid “building blocks.” Two known algorithms are summarized and a new algorithm is presented. The efficiencies and accuracies of the three algorithms are analyzed theoretically and compared experimentally.

The new algorithm uses recursive subdivision to convert CSG representations of complex solids into approximate cellular decompositions based on variably sized blocks. Experimental data show that the new algorithm is efficient and has predictable accuracy. It also has other potential applications, e.g., in producing approximate octree representations of complex solids and in robot navigation.
Mxec: parallel processing with an advanced macro facility
Authors: Ash William L.
Published: July 2002

Mxec is a sophisticated computing environment (executive system) which extends and magnifies users' interactions with a computer. Principally, Mxec provides for parallel processing and also assumes many of the mundane, clerical tasks with which users of most systems find themselves burdened. Some of the characteristics of the Mxec system are given, and its motivation and implementation are discussed.
The evolution of user behavior in a computerized conferencing system
Authors: Hiltz Starr Roxanne , Turoff Murray
Published: July 2002

Data from 18-month operational trials of the EIES system indicate that the range of features considered valuable in a computer-based communication system increases with the amount of experience gained by using this medium of communication. Simple message systems alone are not likely to satisfy the communications needs of long term, regular users of computerized communications systems. Among the capabilities which long term, regular users find valuable are group conferences, notebooks for text composition, and self-defined commands.
A linear algorithm for copying binary trees using bounded workspace
Authors: Lee K. P.
Published: July 2002

An algorithm to copy a binary tree in linear time using bounded workspace is presented. The algorithm does not modify the original tree at any time. The copy is constructed in such a way that it can be traversed in a read-only fashion even before the copying process is complete, provided one can distinguish between the original and the copy. The traversal can be carried out in parallel with the copying.
An algorithmic approach to the conversion of decision grid charts into compressed decision tables
Authors: Maes Rik
Published: July 2002

The decision grid chart is investigated as an intermediate form in constructing decision tables; a very natural extension to the basic format is proposed. Five alternative procedures for the conversion of decision grid charts into compressed decision tables are given. All but one avoid the storage of the fully expanded decision table in memory.
The cyclic order property of vertices as an aid in scene analysis
Authors: Shapira R. , Freeman H.
Published: July 2002

A cyclic-order property is defined for bodies bounded by smooth-curved faces. The property is shown to be useful for analyzing pictures of such bodies, particularly when the line data extracted from the pictures are imperfect. This property augments previously known grammatical rules that determine the existence of three-dimensional bodies corresponding to given two-dimensional line-structure data.
An approach to multidimensional data array processing by computer
Authors: Muller Mervin E.
Published: July 2002

Some recent work on the development of general-purpose computer-based statistical and data processing capabilities for handling multidimensional arrays of data is presented. Attention is first given to some of the general problems of multidimensional table and array processing. This is followed by a summary of some recent developments in array processing capabilities at the World Bank, in particular, the system identified as WRAPS (World Bank Retrieval and Array Processing System).
Analysis of the availability of computer systems using computer-aided algebra
Authors: Chattergy Rahul , Pooch Udo W.
Published: July 2002

Analytical results, related to the availability of a computer system constructed of unreliable processors, are presented in this paper. These results are obtained by using various computer-aided algebraic manipulation techniques. A major purpose of this paper is to demonstrate that the difficulties of obtaining analytical solutions to Markov processes can be considerably reduced by the application of symbol manipulation programs. Since many physical systems can be modeled by Markov and semi-Markov processes, the potential range of application of these techniques is much wider than the problem of availability analyzed here.
A note on virtual memory indexes
Authors: Maly Kurt
Published: July 2002

In [4] Maruyama and Smith analyzed design alternatives for virtual memory indexes. The indexes investigated were those modeled on the structure of VSAM [5] which are closely related to B-trees [1]. Maruyama and Smith presented alternatives for search strategies, page format, and whether or not to compress keys. They made a comparative analysis based on the average cost of processing the index for retrieval of a key with its associated data pointer (or a sequence of keys and data pointers). The analysis showed that the optimal solution depends on machine and file characteristics and they provided formulas for selecting the best alternative. In this brief note
1
we propose that another alternative for the page format be considered. The basic idea is to replace the sequential representation within a page by a linked representation. The main advantage of this method is realized in the construction (and maintenance) phase of the index. Although this phase is difficult to analyze quantitatively—as alluded to in [4]—we provide data to substantiate our claim of a net saving in construction cost without any corresponding loss in the average retrieval cost. In the ensuing discussion we assume that the reader is familiar both with B-trees and the paper of Maruyama and Smith [4].
Cold-start vs. warm-start miss ratios
Authors: Easton Malcolm C. , Fagin Ronald
Published: July 2002

In a two-level computer storage hierarchy, miss ratio measurements are often made from a “cold start”, that is, made with the first-level store initially empty. For large capacities the effect on the measured miss ratio of the misses incurred while filling the first-level store can be significant, even for long reference strings. Use of “warm-start” rather than “cold-start” miss ratios cast doubt on the widespread belief that the observed “S-shape” of lifetime (reciprocal of miss ratio) versus capacity curve indicates a property of behavior of programs that maintain a constant number of pages in main storage. On the other hand, if cold-start miss ratios are measured as a function of capacity and measurement length, then they are useful in studying systems in which operation of a program is periodically interrupted by task switches. It is shown how to obtain, under simple assumptions, the cache miss ratio for multiprogramming from cold-start miss ratio values and how to obtain approximate cold-start miss ratios from warm-start miss ratios.
Dynamic response time prediction for computer networks
Authors: Mamrak Sandra A.
Published: July 2002

If the ultimate aim of a computing network is resource sharing, then the human component as well as the technical component of networking must be fully investigated to achieve this goal. This research is a first step toward assisting the user in participating in the vast store of resources available on a network. Analytical, simulation, and statistical performance evaluation tools are employed to investigate the feasibility of a dynamic response time monitor that is capable of providing comparative response time information for users wishing to process various computing applications at some network computing node. The research clearly reveals that sufficient system data are currently obtainable, at least for the five diverse ARPA network systems studied in detail, to describe and predict the response time for network time-sharing systems as it depends on some measure of system activity or load level.
A simple recovery-only procedure for simple precedence parsers
Authors: Ripley G. David
Published: July 2002

A simple method is described enabling simple precedence parsers to recover from syntax errors. No attempt to repair errors is made, yet parsing and most semantic processing can continue. The result is a good “first approximation” to syntax error handling with negligible increase in parsing time, space, and complexity of both the parser and its table generator.
The selection of optimal tab settings
Authors: Peterson James L. , Bitner James R. , Howard John H.
Published: July 2002

A new generation of computer terminals allows tab settings to be selected and set by the computer. This feature can be used to reduce the number of characters that are needed to represent a document for transmission and printing. In this note, an algorithm is given for selecting the optimal set of tab stops for minimizing the number of characters transmitted. An implementation of the algorithm has reduced the number of characters transmitted by from 7 to 30 percent, but requires a prepass through the document to compute a matrix used in determining the optimal set of tab stops. The use of fixed tab stops, as a heuristic alternative, can achieve about 80 percent of optimal with no prepass.
Logic and programming languages
Authors: Scott Dana S.
Published: July 2002

Logic has been long interested in whether answers to certain questions are computable in principle, since the outcome puts bounds on the possibilities of formalization. More recently, precise comparisons in the efficiency of decision methods have become available through the developments in complexity theory. These, however, are applications to logic, and a big question is whether methods of logic have significance in the other direction for the more applied parts of computability theory.

Programming languages offer an obvious opportunity as their syntactic formalization is well advanced; however, the semantical theory can hardly be said to be complete. Though we have many examples, we have still to give wide-ranging mathematical answers to these queries: What is a machine? What is a computable process? How (or how well) does a machine simulate a process? Programs naturally enter in giving descriptions of processes. The definition of the precise meaning of a program then requires us to explain what are the objects of computation (in a way, the statics of the problem) and how they are to be transformed (the dynamics).

So far the theories of automata and of nets, though most interesting for dynamics, have formalized only a portion of the field, and there has been perhaps too much concentration on the finite-state and algebraic aspects. It would seem that the understanding of higher-level program features involves us with infinite objects and forces us to pass through several levels of explanation to go from the conceptual ideas to the final simulation on a real machine. These levels can be made mathematically exact if we can find the right abstractions to represent the necessary structures.

The experience of many independent workers with the method of data types as lattices (or partial orderings) under an information content ordering, and with their continuous mappings, has demonstrated the flexibility of this approach in providing definitions and proofs, which are clean and without undue dependence on implementations. Nevertheless much remains to be done in showing how abstract conceptualizations can (or cannot) be actualized before we can say we have a unified theory.
Hardware estimation of a process' primary memory requirements
Authors: Gifford David K.
Published: July 2002

A minor hardware extension the Honeywell 6180 processor is demonstrated to allow the primary memory requirements of a process in Multics to be approximated. The additional hardware required for this estimate to be computed consists of a program accessible register containing the miss rate of the associative memory used for page table words. This primary memory requirement estimate was employed in an experimental version of Multics to control the level of multiprogramming in the system and to bill for memory usage. The resulting system's tuning parameters display configuration insensitivity, and it is conjectured that the system would also track shifts in the referencing characteristics of its workload and keep the system in tune.
Joining policies in a multipriority multiclass batch computer system
Authors: Babad Jair M. , Modiano Mario M.
Published: July 2002

Consider a multipriority batch computer system which users from several different classes may join, with toll, service, and waiting charges. Such a system is formulated here as a semi-Markov decision process, in which the aim of arriving users is to minimize their expected loss. The optimal joining policy of arriving users who may join the system at some of its queues is a control limit policy, with a single control number for any possible queue and the user's class; a newly arriving user will join a queue that is not filled up to the control number corresponding to this queue and the user's class. In this paper control numbers, as well as lower and upper bounds for the control numbers and the capacities of the system's queues, are derived.
Synthesis of decision rules
Authors: Cheng Cheng-Wen , Rabin Jonas
Published: July 2002

Decision tables can be used as an effective tool during an interview to record the logic of processes to be automated. The result of such an interview is not a structure of complete decision tables but rather sets of decision rules. The purpose of this paper is to provide a procedure for synthesizing the decision rules and thus provide an aid in developing a structure of complete decision tables.
Algorithm 492: Generation of all the cycles of a graph from a set of basic cycles [H]
Authors: Gibbs Norman E.
Published: July 2002

The PL/I procedure
CYCLE_GENERATOR
is an implementation of Gibbs' algorithm [1] for finding all the cycles in a graph from a set of basic cycles.
Addition in an arbitrary base without radix conversion
Authors: Soule Stephen
Published: July 2002

hnique; using it, one may add and subtract numbers represented in any radix, including a mixed radix, and stored one digit per byte in bytes of sufficient size. Radix conversion is unnecessary, no looping is required, and numbers may even be stored in a display (I/O) format. Applications to Cobol, MIX, and hexadecimal sums are discussed.
Optimizing the performance of a relational algebra database interface
Authors: Smith John Miles , Chang Philip Yen-Tang
Published: July 2002

An approach for implementing a “smart” interface to support a relational view of data is proposed. The basic idea is to employ automatic programming techniques so that the interface analyzes and efficiently refines the high level query specification supplied by the user. A relational algebra interface, called SQUIRAL, which was designed using this approach, is described in detail. SQUIRAL seeks to minimize query response time and space utilization by: (1) performing global query optimization, (2) exploiting disjoint and pipelined concurrency, (3) coordinating sort orders in temporary relations, (4) employing directory analysis, and (5) maintaining locality in page references. Algorithms for implementing the operators of E. F. Codd's relational algebra are presented, and a methodology for composing them to optimize the performance of a particular user query is described.
Extending the infomation theory approach to converting limited-entry decision tables to computer programs
Authors: Shwayder Keith
Published: July 2002

This paper modifies an earlier algorithm for converting decision tables into flowcharts which minimize subsequent execution time when compiled into a computer program.

The algorithms considered in this paper perform limited search and, accordingly, do not necessarily result in globally optimal solutions. However, the greater search effort needed to obtain a globally optimal solution for complex decision tables is usually not justified by sufficient savings in execution time.

There is an analogy between the problem of converting decision tables into efficient flowcharts and the well-understood problem in information theory of noiseless coding. The results of the noiseless coding literature are used to explore the limitations of algorithms used to solve the decision table problem.

The analogy between the two problems is also used to develop improvements to the information algorithm in extending the depth of search under certain conditions and in proposing additional conditions to be added to the decision table.

Finally, the information algorithm is compared with an algorithm proposed in a recent paper by Verhelst.
A locally-organized parser for spoken input
Authors: Miller Perry Lowell
Published: July 2002

This paper describes LPARS, a locally-organized parsing system, designed for use in a continuous speech recognizer. LPARS processes a string of phonemes which contains ambiguity and error. The system is locally-organized in the sense that it builds local parse structures from reliable word candidates recognized anywhere in an input utterance. These local structures are used as “islands of reliability” to guide the search for more highly garbledwords which might complete the utterance.
Maximum computing power and cost factors in the centralization problem
Authors: Oldehoeft A. E. , Halstead M. H.
Published: July 2002

A simple analysis of some computer-economic factors involved in comparing multimachine installations versus large single machine installations is given, and a mathematical model is derived to assist policy decisions.
Synchronization of communicating processes
Authors: Habermann A. Nico
Published: July 2002

Formalization of a well-defined synchronization mechanism can be used to prove that concurrently running processes of a system communicate correctly. This is demonstrated for a system consisting of many sending processes which deposit messages in a buffer and many receiving processes which remove messages from that buffer. The formal description of the synchronization mechanism makes it very easy to prove that the buffer will neither overflow nor underflow, that senders and receivers will never operate on the same message frame in the buffer nor will they run into a deadlock.
Algorithm 421: complex gamma function with error control [S14]
Authors: Kuki Hirondo
Published: July 2002

This Fortran program computes either the gamma function or the loggamma function of a complex variable in double precision. In addition, it provides an error estimate of the computed answer. The calling sequences are:
CALL CDLGAM
(
Z, W, E
, 0) for the loggamma, and
CALL CDLGAM
(
Z, W, E
, 1) for the gamma, where
Z
is the double precision complex argument,
W
is the answer of the same type, and
E
is a single precision real variable. Before the call, the value of
E
is an estimate of the error in
Z
, and after the call, it is an estimate of the error in
W
.
The production of better mathematical software
Authors: Fosdick Lloyd D.
Published: July 2002

Some observations are made on steps to be taken toward the creation of better mathematical software. These steps suggest the need for a coordinated effort and the creation of a center to focus activities in this area.
Computers in the instructional process
Authors: Zinn Karl L.
Published: July 2002

A survey is given of computer applications to the instructional process which suggests how the computer professional can contribute to effective educational systems.
Telecommunications using a front-end minicomputer
Authors: Feinroth Y. , Franceschini E. , Goldstein M.
Published: July 2002

The use of a front-end minicomputer to provide varied remote terminal access to a large scale computer is considered. The problems of embedding telecommunications I/O within an operating system are discussed, and it is shown how the decentralization of intelligence acquired by front-end processing vastly simplifies the problem. A specific implementation is discussed with emphasis on the main processor-minicomputer link, the hardware-software implementation, the effect on the main processor operating system, and an assessment of the advantages over a hardwired line controller.
A comparison of error improvement estimates for adaptive trapezoid integration
Authors: Schweikert D. G.
Published: July 2002

Various simple choices of error improvement estimates for the trapezoid rule are studied to demonstrate a comparison procedure which is relatively independent of the profusion of adaptive search and stopping strategies. Comparisons are based on

x
r

, 0 ≤
r
, 0 ≤
x
≤ 1; the inclusion of the non-integer powers makes this more realistic than the usual polynomial based comparison. Behavior near the singularity was found to be the dominant factor, and a new estimate, based on a constant curvature assumption and parametric differences, was considered slightly better than the other choices considered.
Scheduling to reduce conflict in meetings
Authors: Grimes Joseph E.
Published: July 2002

Conflicts in scheduling can be treated as defining an undirected linear graph independently of the relation of the activities in conflict to additional constraints of time and space. Each connected component of such a graph, which can be found by an algorithm described by Gotlieb and Corneil, corresponds to a set of events that must be scheduled at different times.
An analysis of some time-sharing techniques
Authors: Nielsen Norman R.
Published: July 2002

The effectiveness of certain time-sharing techniques such as program relocation, disk rotational delay minimization, and swap volume minimization is investigated. Summary data is presented, and the findings are discussed. The vehicle for this investigation was a SIMULA based simulation model reflecting an early framework for a planned Burroughs B6500 time-sharing system. Inasmuch as the B6500 system is based upon the use of variable sized segments and a dynamic overlay procedure, data is also presented which provides some indication of the effectiveness of this type of organization in a time-sharing environment. The design characteristics and operational capabilities of the simulation model are also described.
General relativity and the application of algebraic manipulative systems
Authors: Barton D. , Fitch J. P.
Published: July 2002

The paper describes some applications of symbolic algebra systems to problems of general relativity including the derivation of the field equations, the Petrov classification of a metric, and the solution of the field equations in the presence of matter in a simple case. Attention is drawn to the strictly algebraic difficulties encountered in this work.
A nonrecursive list compacting algorithm
Authors: Cheney C. J.
Published: July 2002

A simple nonrecursive list structure compacting scheme or garbage collector suitable for both compact and LISP-like list structures is presented. The algorithm avoids the need for recursion by using the partial structure as it is built up to keep track of those lists that have been copied.
Computers in group theory
Authors: Cannon John J.
Published: July 2002

Computers are being applied to an increasingly diverse range of problems in group theory. The most important areas of application at present are coset enumeration, sub-group lattices, automorphism groups of finite groups, character tables, and commutator calculus. Group theory programs range from simple combinatorial or numerical programs to large symbol manipulation systems. In this survey the more important algorithms in use are described and contrasted, and results which have been obtained using existing programs are indicated. An extensive bibliography is included.