bluuebunny/crossref_metadata_2025 huggingface dataset:
The INCINERATE data model
Authors: Jagadish H. V.
Published: July 2002

In this article, we present an extended relational algebra with universally or existentially quantified classes as attribute values. The proposed extension can greatly enhance the expressive power of relational systems, and significantly reduce the size of a database, at small additional computational cost. We also show how the proposed extensions can be built on top of a standard relational database system.
On deductive databases with incomplete information
Authors: Kong Q. , Chen G.
Published: July 2002

In order to extend the ability to handle incomplete information in a definite deductive database, a Horn clause-based system representing incomplete information as incomplete constants is proposed. By using the notion of incomplete constants the deductive database system handles incomplete information in the form of sets of possible values, thereby giving more information than null values. The resulting system extends Horn logic to express a restricted form of indefiniteness. Although a deductive database with this kind of incomplete information is, in fact, a subset of an indefinite deductive database system, it represents indefiniteness in terms of value incompleteness, and therefore it can make use of the existing Horn logic computation rules. The inference rules for such a system are presented, its model theory discussed, and a model theory of indefiniteness proposed. The theory is consistent with minimal model theory and extends its expressive power.
Process cost and value analysis
Authors: Nejmeh Brian A.
Published: July 2002

After years of pursuing fragments of a solution to the challenges of software engineering, including the development of methods, tools, and the like, the software engineering community has come to realize that over-emphasizing any one of these areas to the exclusion of others is incorrect. The community now recognizes that well-defined and well-supported processes are the critical issue for producing high-quality software systems on-time and within budget.
Beware, techies bearing gifts
Authors: Soloway Elliot
Published: July 2002

The latest techie panacea for fixing education is to just connect all the students to the Internet; with all that information out there, surely they will learn. In Project Globe, Vice President Gore, the U.S.'s chief techie, proposes to connect thousands of schools worldwide.
NSF Center for Intelligent Information Retrieval
Authors: Croft W. Bruce
Published: July 2002

The Center for Intelligent Information Retrieval (CIIR) was started at the University of Massachusetts two years ago to do research and technology transfer in the area of distributed, text-based information systems. The CIIR is part of the NSF State/Industry University Collaborative Research Centers program and relies heavily on government and industrial partners, in addition to federal funding. There are currently 24 members from a variety of industries and government agencies, and many of these are involved in both research and development projects.
The Stanford Digital Library Project
Authors: The Stanford Digital Libraries Group CORPORATE
Published: July 2002

The Stanford Integrated Digital Library Project will develop enabling technologies for an integrated “virtual” library to provide an array of new services and uniform access to networked information collections. The Integrated Digital Library will create a shared environment linking everything from personal information collections, to collections of conventional libraries, to large data collections shared by scientists.
Information superhighway 2015
Authors: Denning Peter J.
Published: July 2002

hospitable as the traditional ones.
Theory and application of Marsaglia's monkey test for pseudorandom number generators
Authors: Percus Ora E. , Whitlock Paula A.
Published: July 2002

A theoretical analysis is given for a new test, the “Monkey” test, for pseudorandom number sequences, which was proposed by Marsaglia. Selected results, using the test on several pseudorandom number generators in the literature, are also presented.
Extending temporal logic to support high-level simulations
Authors: Tuzhilin Alexander
Published: July 2002

A high-level simulation language based on temporal logic is described. The language combines a large set of temporal tenses and a rich class of high-level modeling primitives. Also an implementation of the language interpreter is presented. Finally, a real-world case study is described that shows how a programmer can develop structured, reliable, and well-maintainable simulation programs using the language.
A set of Ada packages for high-precision calculations
Authors: Doman B. G. S. , Pursglove C. J. , Coen W. M.
Published: July 2002

The packages described here are designed to perform efficient high-accuracy calculations in cases where there can be serious loss of significance due to rounding errors. Numbers are represented by a value part with a variable number of digits in the mantissa and an error estimate which is updated throughout the calculation and which gives a range of possible values for the result of the calculation. For economy and speed, intermediate results are truncated so that the least-significant digits correspond to values only a few orders of magnitude smaller than the error estimate. Type definitions and the standard arithmetic operations, together with conversions to and from integers, are provided in one package. The mathematical constants π and Euler's gamma are incorporated to a maximum precision of 320 digits in a package that also contains all of the standard elementary functions. Separate packages contain input and output procedures and conversion to and from floating-point types.
Algorithm 753: TENPACK
Authors: Buis Paul E. , Dyksen Wayne R.
Published: July 2002

This article presents the interface of an implementation of methods to manipulate equations of this form A
1
⊗·⊗A
m
where the A
i
are matrices. The methods described are independent of
m
. The code is based on LAPACK and the BLAS* and supports virtually all of the matrix formats supported by those packages. Timings of the implementation on several machines are also given.
Consensus
versus
speed
Authors: Rada Roy
Published: July 2002

While international consensus seems assured through the traditional processes of the International Organization of Standardization (ISO), the best known and most powerful standards body, the long time required to make decisions is a major impediment to ISO's influence in the rapidly changing information technology arena.
Implementation aids for optimization algorithms that solve sequences of linear programs
Authors: Nazareth J. L.
Published: July 2002

We describe a collection of modules designed to facilitate the implementation of optimization (LP) algorithms that must solve one or more linear programs in a suitably coordinated sequence. Our collection also provides a basis for discussing some of the broader issues of LP software development and serves as a tutorial on state-of-the-art techniques that may be used to implement LP algorithms in a practical manner.
Simulation run lengths to estimate blocking probabilities
Authors: Srikant Rayadurgam , Whitt Ward
Published: July 2002

We derive formulas approximating the asymptotic variance of four estimators for steady-state blocking probability in a multiserver loss system, exploiting diffusion process limits. These formulas can be used to predict simulation run lengths required to obtain desired statistical precision before the simulation has been run, which can aid in the design of simulation experiments. They also indicate that one estimator can be much better than another, depending on the loading. An indirect estimator based on estimating the mean occupancy is significantly more (less) efficient than a direct estimator for heavy (light) loads. A major concern is the way computational effort scales with system size. For all the estimators, the asymptotic variance tends to be
inversely
proportional to the system size, so that the computational effort (regarded as proportional to the product of the asymptotic variance and the arrival rate) does not grow as system size increases. Indeed, holding the blocking probability fixed, the computational effort with a good estimator decreases to zero as the system size increases. The asymptotic variance formulas also reveal the impact of the arrival-process and service-time variability on the statistical precision. We validate these formulas by comparing them to exact numerical results for the special case of the classical Erlang M/M/s/0 model and simulation estimates for more general G/GI/s/0 models. It is natural to delete an initial portion of the simulation run to allow the system to approach steady state when it starts out empty. For small to moderately size systems, the time to approach steady state tends to be negligible compared to the time required to obtain good estimates in steady state. However, as the system size increases, the time to approach steady state remains approximately unchanged, or even increases slightly, so that the computational effort associated with letting the system approach steady state becomes a greater portion of the overall computational effort as system size increases.
Associative table lookup processing for multioperand residue arithmetic
Authors: Papachristou Christos A.
Published: July 2002

This paper investigates the complexity of multioperand residue addition and multiplication implemented by associative table lookup processing. The complexity measure used is the size of the associative memory, that is, the number of matching words in memory. This measure largely depends on the residue recurrencies, or multiplicities, in the addition and multiplication tables module
M
. The major effort in this work is to evaluate the recurrencies in simultaneous multioperand residue addition and multiplication. The evaluation is simple in case of addition mod
M
, and also in multiplication mod
M
if
M
is prime. To treat the more difficult case of
M
nonprime, a recursive procedure was developed for computing the 2-operand multiplication recurrencies mod
M
. The basis of this technique is the precedence relationships associated with a tree representation of the factors of
M
. It is then shown that the general
D
-operand multiplication mod
M, D
> 2 and
M
nonprime, can be reduced to the 2-operand case by isomorphic transformation. Computation results of 2-operand residue arithmetic operations are provided. Applications to RNS arithmetic implementation are discussed.
On the combinatorial and algebraic complexity of quantifier elimination
Authors: Basu Saugata , Pollack Richard , Roy Marie-Françoise
Published: July 2002

In this paper, a new algorithm for performing quantifier elimination from first order formulas over real closed fields in given. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this data. A new feature of this algorithm is that the role of the algebraic part (the dependence on the degrees of the imput polynomials) and the combinatorial part (the dependence on the number of polynomials) are sparated. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that is output, are independent of the number of input polynomials. As special cases of this algorithm new and improved algorithms for deciding a sentence in the first order theory over real closed fields, and also for solving the existential problem in the first order theory over real closed fields, are obtained.
Second-generation image coding
Authors: Reid M. M. , Millar R. J. , Black N. D.
Published: July 2002

This article gives an overview of a diverse selection of currently used second-generation image coding techniques. These techniques have been grouped into similar categories in order to allow a direct comparison among the varying methods. An attempt has been made, where possible, to expand upon and clarify the details given by the original authors. The relative merits ans shortcomings of each of the techniques are compared and contrasted.
Parallel logic simulation on a network of workstations using parallel virtual machine
Authors: Kormicki Maciek , Mahmood Ausif , Carlson Bradley S.
Published: July 2002

This paper explores parallel logic simulation on a network of workstations using a parallel virtual machine (PVM). A novel parallel implementation of the centralized-time event-driven logic simulation algorithm is carried out such that no global controlling workstation is needed to synchronize the advance of simulation time. Further advantages of our new approach include a random partitioning of the circuit onto available workstations and a pipelined execution of the different phases of the simulation algorithm. To achieve a better load balance, we employ a semioptimistic scheme for gate evaluations (in conjunction with a centralized-time algorithm) such that no rollback is required. The performance of this implementation has been evaluated using the ISCAS benchmark circuits. Speedups improve with the size of the circuit and the activity level in the circuit. Analyses of the communication overhead show that the techniques developed here will yield even higher gains as newer networking technologies like ATM are employed to connect workstations.
Hmap
Authors: Yang Cheng-Hsing , Tsai Chia-Chun , Ho Jan-Ming , Chen Sao-Jie
Published: July 2002

A fast and efficient algorithm for technology mapping of electrically programmable gate arrays (EPGAs) is proposed. This Hmap algorithm covers the Boolean network with programmed logic modules bottom-up. The covering operation is based on collapsing the fanins of a node to form a bigger supernode such that fewer clusters are needed to be detected. Then Boolean matching is used to detect whether the collapsed supernode can be mapped into a logic module by looking up an extended GBDD hash table. The use of this table look-up matching can shorten the matching time significantly. As shown in the experiments, the average running time of Hmap is 20 times faster than that of MIS-pga2.
Decomposition of tautologies into regular formulas and strong completeness of connection-graph resolution
Authors: Bibel W. , Eder E.
Published: July 2002

This paper addresses and answers a fundamental question about resolution. Informally, what is gained with respect to the search for a proof by performing a single resolution step? It is first shown that any unsatisfiable formula may be decomposed into regular formulas provable in linear time (by resolution). A relevant resolution step strictly reduces at least one of the formulas in the decomposition while an irrelevant one does not contribute to the proof in any way. the relevance of this insight into the nature of resolution and of the unsatisfiability problem for the development of proof strategies and for complexity considerations are briefly discussed.

The decomposition also provides a technique for establishing completeness proofs for refinements of resolution. As a first application, connection-graph resolution is shown to be strongly complete. This settles a problem that remained open for two decades despite many proff attempts. The result is relevant for theorem proving because without strong completeness a connection graph resolution prover might run into an infinite loop even on the ground level.
Measurement and analysis of sequential design processes
Authors: Johnson E. W. , Brockman J. B.
Published: July 2002

As design processes continue to increase in complexity it is important to base process-improvement decisions on quantitative analysis. We describe the development of an analytical approach for evaluating sequential design-process completion time and for determining the sensitivities of design time with respect to individual task durations and transition probabilities. Techniques are also detailed for collecting process metadata and calibrating a design proecess model. Example applications illustrate the use of the methodology in analyzing and improving software and hardware design processes.
Cost-benefit methodology for office systems
Authors: Sassone Peter G.
Published: July 2002

The
time savings times salary
(TSTS) approach is a widely used methodology for the financial justification of office information systems, yet its theoretical basis is largely unexplored. In this paper, we identify its underlying economic model, including five critical assumptions. We find that the model, though somewhat restrictive, is not unreasonable. However, we find that the time-saving-times-salary calculation, per se, is implicitly based on a very particular assumption about how saved time will be used. This assumption has neither a behavioral nor normative basis, and we conclude that the TSTS calculation is not meaningful in most cases. An alternate approach, the hedonic wage model, is proposed. This model overcomes most of the deficiencies of the TSTS approach, although it has somewhat greater data requirements and computational complexity. A case study illustrating the use of the hedonic wage model is presented.
Programmer perceptions of productivity and programming tools
Authors: Hanson Stephen José , Rosinski Richard R.
Published: July 2002

Psychometric scaling methods are applied to programmer productivity assessments of 20 tools to recommend a set of minimal, as well as more comprehensive, tools.
A rejection technique for sampling from log-concave multivariate distributions
Authors: Leydold Josef
Published: July 2002

Different universal methods (also called automatic or black-box methods) have been suggested for sampling form univariate log-concave distributions. The descriptioon of a suitable universal generator for multivariate distributions in arbitrary dimensions has not been published up to now. The new algorithm is based on the method of transformed density rejection. To construct a hat function for the rejection algorithm the multivariate density is transformed by a proper transformation
T
into a concave function (in the case of log-concave density
T(x)
= log(
x
).) Then it is possible to construct a dominating function by taking the minimum of serveral tangent hyperplanes that are transformed back by
T
-1
into the original scale. The domains of different pieces of the hat function are polyhedra in the multivariate case. Although this method can be shown to work, it is too slow and complicated in higher dimensions. In this article we split the ℝ
n
into simple cones. The hat function is constructed piecewise on each of the cones by tangent hyperplanes. The resulting function is no longer continuous and the rejection constant is bounded from below but the setup and the generation remains quite fast in higher dimensions; for example,
n
= 8. The article describes the details of how this main idea can be used to construct algorithm TDRMV that generates random tuples from a multivariate log-concave distribution with a computable density. Although the developed algorithm is not a real black box method it is adjustable for a large class of log-concave densities.
Breakpoints and breakpoint detection in source-level emulation
Authors: Koch Gernot H. , Rosenstiel W. , Kebschull U.
Published: July 2002

We present an approach for accelerating the validation speed of behavioral system descriptions through hardware emulation. The method allows source-level debuggingof running hardware specified in behavioral VH DL in a way similar to sorce-leve debugging in software programing languages. We discuss breakpoints in source-level emulation and how the circuit generated by high-level synthesis has to be modified to work with breakpoints. Breakpoint encoding and detection are shown in detail. Our approach allows breakpoint detection by hardware with seriously slowing the circuit or dramitically increasing its size.
Estimating the storage requirements of the rectangular and L-shaped corner stitching data structures
Authors: Mehta Dinesh P.
Published: July 2002

This paper proposes a technique for estimating the storage requirements of the Rectangular Corner Stitching (RCS) data structure [Ousterhout 1984] and the L-shaped Corner Stitching (LCS) data structure [Mehta and Blust 1997] on a given circuit by studying its (the circuit's) geometric properties. This provides a method for estimating the storage requirements of a circuit without having to implement the corner stitching data structure, which is a tedious and time-consuming task. This technique can also be used to estimate the amount of space saved by employing the LCS data structure over the RCS data structure on a given circuit.
Certification of algorithm 734
Authors: Hopkins Tim
Published: July 2002

A Fortran 90 Code for Unconstrained Nonlinear Minimization (
ACM Trans. Math. Softw. 20
, 3 (Sept. 1994), pages 354-372; CALGO Supplement 131) was ported to a number of compiler-platform combinations. The necessary changes to the code are given along with some comparative timings.
Auxiliary variables for BDD-based representation and manipulation of Boolean functions
Authors: Cabodi Gianpiero , Camurati Paolo , Quer Stefano
Published: July 2002

BDDs are the state-of-the-art technique for representing and manipulating Boolean functions. Their introduction caused a major leap forward in synthesis, verification, and testing. However, they are often unmanageable because of the large amount of nodes. To attack this problem, we insert auxiliary variables that decompose monolithic BDDs in smaller ones. This method works very well for Boolean function representation. As far as combinational circuits are concerned, representing their functions is the main issue. Going into the sequential domain, we focus on traversal techniques. We show that, once we have Boolean functions in decomposed form, symbolic manipulations are viable and efficient. We investigate the relation between auxiliary variables and static and dynamic ordering strategies. Experimental evidence shows that we achieve a certain degree of independence from variable ordering. Thus, this approach can be an alternative to dynamic re-ordering. Experimental results on Boolean function representation, and exact and approximate forward symbolic traversal of FSMs, demonstrate the benefits both in terms of memory requirements and of CPU time.
ATM switch design by high-level modeling, formal verification and high-level synthesi
Authors: Rajan S. P. , Fujita M. , Yuan K. , Lee M. T-C.
Published: July 2002

Asynchronous Transfer Mode (ATM) has emerged as a backbone for high-speed broadband telecommunication networks. In this paper, we present ATM switch design, starting from a parametric high-level model and debugging the model using a combination of formal verification and simulation. The model has been used to synthesize ATM switches according to customers' choices, by choosing concrete values for each of the generic parameters. We provide a pragmatic combination of simulation, model checking, and theorem proving to gain confidence in the ATM switch design correctness.
Power reduction and power-delay trade-offs using logic transformations
Authors: Wang Qi , Vrudhula Sarma B. K. , Yeap Gary , Ganguly Shantanu
Published: July 2002

We present an efficient technique to reduce the switching activity in a technology-mapped CMOS combinational circuit based on local logic transformations. The transformations consist of adding redundant connections or gates so as to reduce switching activity. We describe simple and efficient procedures, based on logic implication, for identifying the sources and targets of the redundant connections. Additionally, we give procedures that permit the designer to trade-off power and delay after the transformations. Results of experiments on both the MCNC benchmark circuits and the circuits of a PowerPC microprocessor chip are given. The results indicate that significant power reduction of a CMOS combinational circuit can be achieved with very low area overhead, delay penalty, and computational cost.
Profiles in computing: Brian K. Reid: a graphics tale of a hacker tracker
Authors: Frenkel Karen A.
Published: July 2002

"When the Securities Exchange Commission was created by Franklin Roosevelt, he was trying to fix a lot of problems on Wall Street. There were various Ivan Boesky-type crimes being committed on the stock market, and Roosevelt wanted to create a regulatory agency that would keep it in line. He wanted to hire a sheriff to police Wall Street. What he did was he hired the person who was absolutely, unarguably, the biggest criminal on Wall Street—the person who was guilty of the most crimes. And he put him in charge of the Securities Exchange Commission, figuring that that person, being the most successful Wall Street bandit, knew all the tricks and could police his friends. And that person did a really good job of cleaning up Wall Street actually, because he did know all the tricks."

"In a certain sense, I got my start in the computer business by bending the rules, or not knowing what the rules were. I was extremely good at penetrating everyone's computer security when I was a kid. And, because of my tremendous knowledge in this area, I have frequently been called in to help catch people who break in. . . ."
Commentaries on the past 15 years
Authors: Weiss Eric A.
Published: July 2002

A longtime member comments on the trends, happenings, events, and accomplishments of ACM in the period 1972-1987, followed by "Self-Assessment Procedure XVII."
Excerpts from
Authors: Martin James , Kleinrock Leonard
Published: July 2002

James Martin talks with Leonard Kleinrock about the state of the art in data processing—how corporate and MIS managers should manage the new technology, and how computer science education should relate to it.
Efficient locking for concurrent operations on B-trees
Authors: Lehman Philip L. , Yao s. Bing
Published: July 2002

The B-tree and its variants have been found to be highly useful (both theoretically and in practice) for storing large amounts of information, especially on secondary storage devices. We examine the problem of overcoming the inherent difficulty of concurrent operations on such structures, using a practical storage model. A single additional “link” pointer in each node allows a process to easily recover from tree modifications performed by other concurrent processes. Our solution compares favorably with earlier solutions in that the locking scheme is simpler (no read-locks are used) and only a (small) constant number of nodes are locked by any update process at any given time. An informal correctness proof for our system is given.
Heuristics for trie index minimization
Authors: Comer Douglas
Published: July 2002

A trie is a digital search tree in which leaves correspond to records in a file. Searching proceeds from the root to a leaf, where the edge taken at each node depends on the value of an attribute in the query. Trie implementations have the advantage of being fast, but the disadvantage of achieving that speed at great expense in storage space. Of primary concern in making a trie practical, therefore, is the problem of minimizing storage requirements. One method for reducing the space required is to reorder attribute testing. Unfortunately, the problem of finding an ordering which guarantees a minimum-size trie is NP-complete. In this paper we investigate several heuristics for reordering attributes, and derive bounds on the sizes of the worst tries produced by them in terms of the underlying file. Although the analysis is presented for a binary file, extensions to files of higher degree are shown.

Another alternative for reducing the space required by a trie is an implementation, called an Ο-trie, in which the order of attribute testing is contained in the trie itself. We show that for most applications, Ο-tries are smaller than other implementations of tries, even when heuristics for improving storage requirements are employed.
Algorithms for parsing search queries in systems with inverted file organization
Authors: Liu Jane W. S.
Published: July 2002

In an inverted file system a query is in the form of a Boolean expression of index terms. In response to a query the system accesses the inverted lists corresponding to the index terms, merges them, and selects from the merged list those records that satisfy the search logic. Considered in this paper is the problem of determining a Boolean expression which leads to the minimum total merge time among all Boolean expressions that are equivalent to the expression given in the query. This problem is the same as finding an optimal merge tree among all trees that realize the truth function determined by the Boolean expression in the query. Several algorithms are described which generate optimal merge trees when the sizes of overlaps between different lists are small compared with the length of the lists.
On Exponential Digital Filters
Authors: Blum Marvin
Published: July 2002

This paper derives the weighting sequence of a linear digital filter whose output is an estimate of the predicted values of the derivatives of the input. The input functions considered are arbitrary linear combinations of
n
+ 1 known functions, plus a random stationary signal and a random stationary noise component. The filter differs from previously considered minimum variance optimum filters in that the primary consideration here is the computational ease with which one can obtain the final solution. An optimization in the minimum variance sense is obtained as a secondary consideration in order to provide some control of the mean square output error. The exponential filter has its simplest form for the class of nonrandom input functions (

h
n

) which are the complete solutions of a set of homogeneous linear difference equations of order
n
with constant coefficients. For this class the input and output are related by a time invariant recursion formula. The output contains a bias error which can be made to approach zero exponentially as the mean square error increases monotonically to a limit with increasing time.

A modification of the exponential filter is considered such that the bias error is zero. The solution then involves a recursion formula with time varying coefficients.
On an Application of Dynamic Programming to the Synthesis of Logical Systems
Authors: Bellman Richard , Holland John , Kalaba Robert
Published: July 2002

In this paper we wish to initiate the study of the application of dynamic programming to the domain of problems arising in the synthesis of logical systems.

In a number of fields one encounters the problem of converting a system in one state into another state in a most efficient fashion—in mathematical economics, in the theory of control processes, in network theory, and in trajectory processes. Here we wish to consider a type of question which arises in the design of computers and switching circuits.

We shall first treat the problem in general terms, and then consider a special example to illustrate the methods.
Boundary Contraction Solution of Laplace's Differential Equation II
Authors: Chow Tse-Sun , Milnes Harold Willis
Published: July 2002

In this paper the numerical solution of Laplace's equation for the circle is discussed and consideration is given to the convergence of the solution obtained by the boundary contraction method to the analytic solution. It is proved that in order to achieve this a relation between the mesh sizes in the circumferential and radial direction must exist. It is also demonstrated that the error due to the contraction of boundaries can be made insignificant.
A New Method for the Payment of Bills and the Transfer of Credit
Authors: Salton Gerard
Published: July 2002

The transfer of credit and the processing of receivables play important roles in most business systems. Present procedures require a
dual handling
of payments— they are processed both by the payee and again by the banks involved in the transfer of credit. The banks must necessarily process payments made by check; it is therefore reasonable to inquire whether the processing now required of the payee is not largely redundant, and whether it would not therefore be profitable to alter the present system.

Three questions deserve examination:

Can the present system be simplified?

Will simplification lead to net savings?

How should the savings be shared?
Computational Aids for Determining the Minimal Form of a Truth Function
Authors: Prather Ronald
Published: July 2002

The literature concerned with methods for finding the minimal form of a truth function is, by now, quite extensive. This article extends this knowledge by introducing an algorithm whereby all calculations are performed on decimal numbers obtained from binary-decimal conversion of the terms of the Boolean function. Several computational aids are presented for the purpose of adapting this algorithm to the solution of large-scale problems on a digital computer.
Tables for the Step-by-Step Integration of Ordinary Differential Equations of the First Order
Authors: Pickard William F.
Published: July 2002

A study is made of the step-by-step integration of ordinary differential equations of the first order by means of formulas obtained from the Gregory-Newton backward interpolating formula. Tables of relevant constants are presented.
Numerical Experiments in Conformal Mapping by the Method of Orthonormal Polynomials
Authors: Rabinowitz Philip
Published: July 2002

Conformal maps of simply connected regions onto the interior and exterior of the unit circle can be computed from complex polynomials orthonormal over the boundary of the given region. As an example of this method, maps of ellipses, rectangles, limacons and ovals of Cassini were computed on the IBM 7070. The results indicate that, in general, the method gives good accuracy, but roundoff error can become very serious, indicating the desirability of computing with greater precision. For fourfold symmetric regions, the algorithm can be simplified to decrease significantly the amount of computation resquired to achieve the same accuracy as that achieved by the algorithm for the general case.
A Class of Integration Formulas
Authors: Hamming R. W. , Pinkham R. S.
Published: July 2002

Gregory's formula for numerically integrating a function is one of the most promising formulas for use in a computer library. This paper shows how Gregory's formula can be generalized, and examines special cases which have a number of very favorable properties for library use.
Modified Multistep Methods Based on a Nonpolynomial Interpolant
Authors: Shaw Brian
Published: July 2002

A new class of multistep formulas with variable coefficients is derived for the numerical integration of the ordinary differential equation
y
′ =
f
(
x
,
y
) whose theoretical solution possesses a singularity. A first numerical solution is obtained along with estimates for the behavior of the singularity, and these estimates are then used to obtain further numerical solutions.
A Universal Syntax-Directed Top-Down Analyzer
Authors: Chartres B. A. , Florentin J. J.
Published: July 2002

An algorithm is described that will recognize, and fully analyze, strings of unbounded length, using the rewriting rules of any context-free grammar. It uses a finite random access store, three pushdown tapes, and a counter. It imposes no restrictions on the grammar defined by the rewriting rules, excepting only that it be a context-free phrase structure grammar. The analysis printed out is a linearized form of the structural description tree (or trees, in an ambiguous case) of the input string. A proof that the analyzer will always stop in a finite time is provided. The upper bound on the running time increases exponentially with input string length.
Synchronizations and General Repetitive Machines, with Applications to Ultimate Definite Automata
Authors: Reynolds R. G. , Cutlip W. F.
Published: July 2002

Let
s
and
t
be states of a finite (deterministic) automaton
A
.
t
can be reached from
s
if there is a tape
x
such that, if
A
is in state
s
and receives
x
,
A
goes to state
t
.

We consider (1) automata in which the initial state can be reached from any final state, and (2) automata which can be brought to a known state from any unknown state by applying a predetermined tape
x
.

Necessary and sufficient conditions for an ultimate definite automaton to have the former property are obtained. Every ultimate definite automaton
A
is shown to have the latter property; and a characterization is obtained for all tapes which bring
A
to a known state. Finally, those ultimate definite automata having the former property are shown to be precisely those which can be brought to the start state from any state by some tape
x
.
The Time Required for Group Multiplication
Authors: Spira Philip M.
Published: July 2002

Winograd has considered the time necessary to perform numerical addition and multiplication and to perform group multiplication by means of logical circuits consisting of elements each having a limited number of input lines and unit delay in computing their outputs. In this paper the same model as he employed is adopted, but a new lower bound is derived for group multiplication—the same as Winograd's for an Abelian group but in general stronger. Also a circuit is given to compute the multiplication which, in contrast to Winograd's, can be used for non-Abelian groups. When the group of interest is Abelian the circuit is at least as fast as his. By paralleling his method of application of his Abelian group circuit, it is possible also to lower the time necessary for numerical addition and multiplication.
Random Sets in Subrecursive Hierarchies
Authors: Di Paola Robert A.
Published: July 2002

Successive modifications of Church's definition of a random sequence are considered in terms of their relative position in the Ritchie hierarchy of Kalmar elementary functions. A general result is derived governing the classification of Church random sequences in subrecursive hierarchies which include the elementary functions, such as the Grzegorczyk and Kleene subrecursive hierarchies.
Legality and Other Properties of Graph Models of Computations
Authors: Baer J. L. , Bovet D. P. , Estrin G.
Published: July 2002

Directed graphs having logical control associated with each vertex have been introduced as models of computational tasks for automatic assignment and sequencing on parallel processor systems. A brief review of their properties is given. A procedure to test the “legality” of graphs in this class is described, and leads to algorithms for counting the number of all possible executions (AND-type subgraphs), and for evaluating the probability of ever reaching a given vertex in the graph. Numerical results are given for some example graphs.
A Method for Solving Large Matrix Equations Reduced From Fredholm Integral Equations of the Second Kind
Authors: Hashimoto Masahiro
Published: July 2002

The method of reducing a Fredholm integral equation of the second kind to a matrix equation and then inverting the matrix is well suited to a machine computation. The number of the dimension of the matrix equation is desired to be large for a well approximated solution. However, much computing time may be required to invert the matrix or the number of the elements of the matrix may exceed the memory capacity. A successive iterative method is suggested to avoid these difficulties.
A Class of Merging Algorithms
Authors: Hwang F. K. , Deutsch D. N.
Published: July 2002

Suppose we are given two disjoint linearly ordered subsets
A
and
B
of a linearly ordered set
C
, say
A
= {
a
1
<
a
2
< ··· <

a
m

} and
B
= {
b
1
<
b
2
< ··· <

b
n

}. The problem is to determine the linear ordering of their union (i.e. to merge
A
and
B
) by means of a sequence of pairwise comparisons between an element of
A
and an element of
B
(which we refer to in the paper as the (
m, n
) problem). Given any algorithm
s
to solve the (
m, n
) problem, we are interested in the maximum number of comparisons

K
s

(
m, n
) required under all possible orderings of
A
∪
B
. An algorithm
s
is said to be minimax if

K
s

(
m, n
) =
K
(
m, n
) where
K
(
m, n
) = mins

K
s

(
m, n
)

It is a rather difficult task to determine
K
(
m, n
) in general. In this study the authors are only concerned with the minimax over a particular class of merging algorithms. This class includes the tape merge algorithm, the simple binary algorithm, and the generalized binary algorithm.
Canonical Precedence Schemes
Authors: Gray James N. , Harrison Michael A.
Published: July 2002

A general theory of canonical precedence analysis is defined and studied. The familiar types of precedence analysis such as operator precedence or simple precedence occur as special cases of this theory. Among the theoretical results obtained are a characterization of the structure of precedence relations and the relation of canonical precedence schemes to operator sets.
Cyclic Queues with Bulk Arrivals
Authors: Adiri Igal
Published: July 2002

This paper deals with a single-server station (a computer) where each customer's demand comprises an independent random number of jobs (programs). Under certain assumptions, two cyclic disciplines are mathematically analyzed: (a) continuous job service—a round-robin discipline where the quantum's length is distributed as the service requirement of a job; (b) intermittent job service—a double round-robin discipline—in the first instance in terms of the jobs within the customer's demand, and in the second in terms of the customer himself.
Computing a Subinterval of the Image
Authors: Richman Paul L.
Published: July 2002

The problem of computing a desired function value to within a prescribed tolerance can be formulated in the following two distinct ways:
Formulation
I: Given x and ∈ > 0, compute
f
(x) to within ∈.
Formulation
II: Given only that x is in a closed interval X, compute a subinterval of the image,
f
(X) = {
f
(x) : x ∈ X}. The first formulation is applicable when x is known to arbitrary accuracy. The second formulation is applicable when x is known only to a limited accuracy, in which case the tolerance is prescribed albeit indirectly by the interval X, and one must be satisfied with all or part of the set
f
(X) of possible function values.

Elsewhere the author has presented an efficient solution to Formulation I for any rational
f
and many nonrational
f
. B. A. Chartres has presented an efficient solution to Formulation II for a very restricted class of rational
f
and for a few nonrational
f
.

In this paper a solution to Formulation II for the arbitrary nonconstant rational
f
is presented. By bounding
df/dx
away from zero over some subset of X, it is shown how to reduce Formulation II to Formulation I, yielding the solution given here.

In generalizing to vector-valued functions f, Chartres has solved Formulation II only for rational f which satisfy a linear system of equations, while this paper presents a solution for arbitrary non-degenerate rational vector-valued f.
Multilevel Queues with Extremal Priorities
Authors: Rosberg Z. , Adiri I.
Published: July 2002

This paper deals with a single server serving
N
priority classes (
N
being finite or infinite) and working under an FB
z
regime, namely, one in which the waiting line consists of infinitely many separate queues obeying the FIFO rule. Each priority class is assigned to one of the queues. A customer from the
k
th priority class (“
k
-customer”) in the
n
th queue is eligible for

θ
n,k

time units of service, at the end of which he either departs, because his requirement is satisfied, or joins the tail of the (
n
+ 1)-th queue. When a quantum of service is completed, the server turns to the first customer in the lowest index (highest priority) nonempty queue.

The arrival process of
k
-customers is assumed to be homogeneous Poisson, and their service requirements are independent, generally distributed, random variable. A set of recursive linear equations is derived for the expected flow time of a
k
-customer whose service requirement is known, and some examples are discussed and presented graphically.

This paper corrects some errors in an earlier paper by the second author.
On Certain Output-Buffer Management Techniques—A Stochastic Model
Authors: Hofri Micha
Published: July 2002

A queueing-type model is used to analyze the storage requirements of a component of a real-time data entry system. The objectives and criteria of the buffer management procedure are identified and related to the variables of the model. Both infinite and finite buffers are considered. The analysis is done symbolically in part and numerically in part to accommodate input processes that are peculiar to the system. Techniques to obtain overflow probabilities are described in detail. It is shown that creating a pool of storage blocks for all the terminals is a better policy than maintaining a separate buffer for each station. The savings brought about by this policy are remarkably insensitive to the characteristics of the input process.
Can Any Stationary Iteration Using Linear Information Be Globally Convergent?
Authors: Wasilkowski G. W.
Published: July 2002

All known globally convergent iterations for the solution of a nonlinear operator equation ƒ(
x
) = 0 are either nonstationary or use nonlinear information. It is asked whether there exists a globally convergent stationary iteration which uses linear information. It is proved that even if global convergence is defined in a weak sense, there exists
no
such iteration for as simple a class of problems as the set of all analytic complex functions having only simple zeros. It is conjectured that even for the class of all real polynomials which have real simple zeros there does not exist a globally convergent stationary iteration using linear information.
Semantic multicast
Authors: Dao Son , Shek Eddie , Vellaikal Asha , Muntz Richard R. , Zhang Lixia , Potkonjak Miodrag , Wolfson Ouri
Published: July 2002

We introduce the concept of semantic multicast to implement a large-scale shared interaction infrastructure providing mechanisms for collecting, indexing, and disseminating the information produced in collaborative sessions. This infrastructure captures the interactions between users (as video, text, audio and other data streams) and promotes a philosophy of filtering, archiving, and correlating collaborative sessions in user and context sensitive groupings. The semantic multicast service efficiently disseminates relevant information to every user engaged in the collaborative session, making the aggregated streams of the collaborative session available to the correct users at the right amount of detail. This contextual focus is accomplished by introducing proxy servers to gather, annotate, and filter the streams appropriate for specific interest groups. Users are subscribed to appropriate proxies, based on their profiles, and the collaborative session becomes a multi-level multicast of data from sources through proxies and to user interest groups.
Creation and performance analysis of user representations in collaborative virtual environments
Authors: Martin Kevin
Published: July 2002

In distributed collaborative virtual environments, participants are often embodied or represented in some form within a virtual world. The representations take many different forms and are often driven by limitations in the available technology. Desktop Web based environments typically use textual or two dimensional representations, while high end environments use motion trackers to embody a participant and their actions in an
avatar
or human form. This paper describes this wide range of virtual user representations and their creation and performance issues investigated as part of the Human-Computer Symbiotes project within DARPA's Intelligent Collaboration and Visualization (IC&V) program.