bluuebunny/crossref_metadata_2025 huggingface dataset:
Use of the disk file on stretch
Authors: Carlson B. G. , Voorhees E. A.
Published: July 2002

The paper begins by briefly describing the Stretch (IBM 7030) computer with special emphasis given to the organization and operation of its input-output equipment. Physical characteristics of the two-disk system (4,194,304 72-bit words, 8
µ
sec-per-word transmission rate, etc.) are noted. Timing limitations due to arm motion and disk rotation are discussed.

Applications of disk usage are discussed separately for problem programs and for systems programs such as compilers and the supervisory program. Approximately 260,000 words of disk storage are reserved for the storage of systems programs and the subroutine library. Problem programs, however, are not currently filed on the disk.

Certain programming techniques are discussed for transmitting words between disk and core storage with minimum delaying and interruption of the arithmetic unit. Dumps on disk are considered for both recovery from computer malfunction and for mathematical or physical developments during the calculation.
On translation of Boolean expressions
Authors: Bottenbruch H. H. , Grau A. A.
Published: July 2002

A program which translates an algorithmic language such as ALGOL into the machine language of an electronic computer performs the following functions:

Analysis
. From the program in algorithmic language are determined the operations which the computer must perform in the execution of the target program and the logical interdependence of these.

Optimization
. Of the many possibilities for optimization that exist, two are pertinent to this note: (2a) the elimination of superfluous operations, and (2b) the execution at translation time of those operations which do not depend on results produced by the target program.

Synthesis
. The sequence of operations which arise from steps 1 and 2 is expressed in the language of the computer and placed into the target program.
Flexible abbreviation of words in a computer language
Authors: Loomis R. G. , Rubin J.
Published: July 2002

An increasing number of computer programs are designed to accept and translate a symbolic, English-like language which facilitates communication between the user and the computer. A common feature of such programs is a pre-determined vocabulary of expressions for specifying the input to the program. This note describes a generalized technique for permitting flexible abbreviation of such expressions in order to further simplify the task of writing source programs.
Need for an algorithm
Authors: Selden W.
Published: July 2002

As EDPM are more tightly scheduled and programming systems are further developed, increasing attention is being directed to the reduction of idle time between jobs when tapes are being changed, etc.
Nearly optimal importance sampling for Monte Carlo simulation of loss systems
Authors: Lassila Pasi E. , Virtamo Jorma T.
Published: July 2002

In this paper we consider the problem of estimating blocking probabili ties in the multiservice loss system via simulation, applying the static Monte Carlo method with importance sampling. Earlier approaches to this problem include the use of either a single exponentially twisted version of the steady state distribution of the system or a composite of individual exponentially twisted distributions. Here, a different approach is introduced, where the original estimation problem is first decomposed into independent simpler subproblems, each roughly corresponding to estimating the blocking probability contribution from a single link. Then two importance sampling distributions are presented, which very closely approximate the ideal importance sampling distribution for each subproblem. In both methods, the idea is to try to generate samples directly into the blocking state region. The difference between the methods is that the first method, the inverse convolution method, achieves this exactly, while the second one, using a fitted Gaussian distibution, only approximately. The inverse convolution algorithm, however, has a higher memory requirement. Finally, a dynamic control algorithm is given for optimally allocating the samples between different subproblems. The numerical results demonstrate that the variance reduction obtained with the methods, especially with the inverse convolution method, is tryly remarkable, between 670 and 1,000,000 in the examples under consideration.
POSE
Authors: Hsiung Pao-Ann
Published: July 2002

Design automation tools and methodologies always encounter a problem of how systems may be designed efficiently, including issues such as static modeling and dynamic manipulation of system parts. With the rapid progress of design technology, the continuously increasing number of different choices per system part and the growing complexity of today's systems, the efficiency of the design environment is not only a major concern now, but will also be a demanding problem in the near future. In contrast to heuristic methods, a novel environment called POSE is proposed that increases efficiency during design without losing optimality in the final design results. System parts are modeled using the popular object-oriented modeling technique and are dynamically manipulated using the parallel design technique. A complete integration of object-oriented and parallel techniques is one of the major feature of POSE. Common problems related to parallel design such as
emptiness
and
deadlock
are also elegantly solved within POSE. Experimental results and formal analysis based on POSE all show its practical and theoretical usefulness. POSE can be used at any level of synthesis as long as off-the-shelf building-blocks manipulation is required. POSE can be applied especially to
system-level
synthesis, whose targets can be parallel computer architectures, systems-on-chip, or embedded systems. We will show how POSE has been applied to ICOS, a recently proposed synthesis methodology. Furthermore, POSE can be easily integrated with other heuristic design methodologies to allow increased design efficiency.
Reusability and adaptability of interactive resources in Web-based educational systems
Authors: Saddik Abdulmotaleb El , Fischer Stephan , Steinmetz Ralf
Published: July 2002

The production of interactive multimedia content is in most cases an expensive task in terms of time and cost. Hence, optimizing production by exploiting the reusability of interactive multimedia elements is mandatory. Reusability can be triggered by a combination of resuable multimedia components and the appropriate use of metadata to control the components as well as their combination.

In this article, we discuss the reusability aspects of interactive multimedia content in web-based learning systems. In contrast to existing approaches, we extend a component-based architecture to build interactive multimedia visualization units with the use of metadata for reusability and customizability.

In the three-tier model, the lowest layer of the paradigm corresponds to the programmer (code reusability). The user interface of an educational visualization is located at the top layer where the interaction with the end-user (student) takes place. The educator is located between the top and the bottom layers. This medium layer allows adapting interactive multimedia content according to the needs of the user, applying a predefined set of metadata. The teacher can both adjust the level of explanation and the level of interactivity of an animation, and influence the presentation and the results of the algorithms being illustrated (program reusability). After a theoretical overview, we explain our architecture by giving an example of an application.
Comparing the QoS of Internet audio mechanisms via formal methods
Authors: Aldini Alessandro , Bernardo Marco , Gorrieri Roberto , Roccetti Marco
Published: July 2002

We compute and compare the quality of service (QoS) of three soft real-time applications for audio transmissions over the Internet. The main metric we want to capture is the average packet audio playout delay vs. the packet loss rate as perceived by users. Other metrics we take into account are the packet loss rate vs. the receiving buffer capacity, the lateness of discarded packets vs. average packet audio playout delay, and the waiting time in the receiver buffer for the played packets vs. the average packet audio playout delay. The study is conducted in the algebraic language EMPA, by way of formal descriptions of the three audio mechanisms. The mechanisms are analyzed via simulation using the software tool TwoTowers under various (experimentally obtained or randomly generated) traffic conditions. The stochastic process algebra EMPA is used because it compositionally supports system modeling, it allows functional properties of systems to be formally verified (unlike conventional simulatiors), and it represents generally distributed durations (which come into play in the three audio mechanisms). The comparison reveals that in general no one of the three mechanisms outperforms the other two, as their performance depends on the traffic conditions.
Von Neumann hybrid cellular automata for generating deterministic test sequences
Authors: Kagaris D. , Tragoudas S.
Published: July 2002

We propose an on-chip test pattern generator that uses an
one-dimensional cellular automaton (CA) to generate either a precomputed sequence of test patterns or pairs of test patterns for path delay faults. To our knowledge, this is the first approach that guarantees successful on-chip generation of a given test pattern sequence (or a given test set for path delay faults) using a finite number of CA cells. Given a pair of columns (C

u

, C

v

) of the test matrix, the proposed method uses alternative “link procedures” P

j

that compute the number of extra CA cells to enable the generation of (C
u
, C

v

) by the CA. A systematic approach uses the link procedures to minimize the total number of needed CA cells. The performance of the scheme depends on an appropriate choice of link procedures P

j

.
Cautious transaction schedulers with admission control
Authors: Katoh Naoki , Ibaraki Toshihide , Kameda Tiko
Published: July 2002

We propose a new class of schedulers, called
cautious schedulers
, that grant an input request if it will not necessitate any rollback in the future. In particular, we investigate cautious WRW-schedulers that output schedules in class WRW only. Class WRW consists of all schedules that are serializable, while preserving the write-read and read-write conflict, and is the largest polynomially
recognizable
subclass of serializable schedules currently known. It is shown, in this paper however, that cautious WRW-
scheduling
is, in general, NP-complete. Therefore, we introduce a special type (
type 1R
) of transaction, which consists of no more than one read step (an indivisible set of read operations) followed by multiple write steps. It is shown that cautious WRW-scheduling can be performed efficiently if all transactions are of type 1R and if
admission control
can be exercised. Admission control rejects a transaction unless its first request is immediately grantable.
Behavioral experiments on handmarkings
Authors: Gould John D. , Salaun Josiane
Published: July 2002

Handmarkings or handwritten editing marks can be used as direct editing commands to an interactive computer system. Five exploratory experiments studied the potential value of handmarkings for editing text and pictures, as well as for some specific results. Circles are the most frequently used scoping mark, and arrows are the most frequently used operator and target indicators. Experimental comparisons showed that handmarkings have the potential to be faster than keyboards and mice for editing tasks. Their ultimate value will, however, depend on the style and details of their user-interface implementation.
Special section on operating systems
Authors: Shaw Alan
Published: July 2002

This special collection of articles examines recent research in operating systems, focusing on particular systems and projects that are seminal and representative. The areas these articles cover include distributed operating systems, heterogeneous computer systems, distributed programming, and real-time systems.
Extended use of null productions in LR(1) parser applications
Authors: Finn Gerard D.
Published: July 2002

Applications programmed using LR(1) parsers should be designed so that as many functions as possible are controlled by the driving parsing machine through conveniently staged reductions and associated primitive actions; in this paper this is achieved by making extensive use of null productions and nullable nonterminal symbols.
Generating gamma variates
Authors: Minh Do Le
Published: July 2002

An algorithm to generate variates having a gamma distribution with shape parameter greater than one is presented in this paper. This algorithm is faster than Schmeiser and Lal's G4PE, which is the fastest one currently available, yet is equally simple and easy to implement.
An imperative sentence processor for voice interactive office applications
Authors: Biermann Alan W. , Fineman Linda , Gilbert Kermit C.
Published: July 2002

An imperative sentence processor that enables a user to manipulate text with connected speech and touch-graphics input is described. The processor includes capabilities to follow dialogue focus, execute a variety of imperative commands, and handle nested noun groups, pronouns, and other phenomena. A micromodel of the system, giving enough of the structure to enable the reader to observe internal mechanisms in considerable detail, is included. This processor is designed to be transportable to a number of other office automation domains such as calendar management, message-passing, and desk calculation. Various examples and statistics related to its behavior in the text manipulation application are given. The system has been implemented in PASCAL and can run on any machine that supports this language.
Optimal VLSI circuits for sorting
Authors: Cole Richard , Siegel Alan
Published: July 2002

This work describes a large number of constructions for sortingNintegers in the range [0,M- 1], forN≤M≤N2, for the standard VLSI bit model. Among other results, we attain:

VLSI sorter constructions that are within a constant factor of optimal size, for allMand almost all running timesT.

a fundamentally new merging network for sorting numbers in a bit model.

new organizational approaches for optimal tuning of merging networks and the proper management of data flow.
Fourth annual UCLA survey of business school computer usage
Authors: Frand Jason,L. , Britt Julia,A. , Anderson John,E. , McLean Ephraim,R.
Published: July 2002

The Fourth Survey is based upon data from 128 AACSB-accredited business schools. It provides a wide variety of information to deans and others involved in making computer related strategic decisions, resource allocations, and program plans.
Properties and update semantics of consistent views
Authors: Gottlob Georg , Paolini Paolo , Zicari Roberto
Published: July 2002

The problem of translating view updates to database updates is considered. Both databases and views are modeled as data abstractions. A data abstraction consists of a set of states and of a set of primitive update operators representing state transition functions. It is shown how complex update programs can be built from primitive update operators and how view update programs are translated into database update programs. Special attention is paid to a class of views that we call “consistent.” Loosely speaking, a consistent view is a view with the following property: If the effect of a view update program on a view state is determined, then the effect of the corresponding database update is unambiguously determined. Thus, in order to know how to translate a given view update into a database update, it is sufficient to be aware of a functional specification of such a program. We show that consistent views have a number of interesting properties with respect to the concurrency of (high-level) update transactions. Moreover we show that the class of consistent views includes as a subset the class of views that translate updates under maintenance of a constant complement. However, we show that there exist consistent views that do not translate under constant complement. The results of Bancilhon and Spyratos [6] are generalized in order to capture the update semantics of the entire class of consistent views. In particular we show that the class of consistent views is obtained if we relax the requirement of a constant complement by allowing the complement to decrease according to a suitable partial order.
Operating an Emergency Information Service
Authors: Yee Ka-Ping
Published: July 2002

Using the Internet to help cope with disaster.
The Growing Debate Over Science and Technology Advice for Congress
Authors: Peha Jon M.
Published: July 2002

Scientific and policy leaders interact during a rare but useful workshop on Capitol Hill.
The DMCA Needs Fixing
Authors: Phoha Vir V.
Published: July 2002

Reexamining U.S. copyright laws.
Groupware and the Social Infrastructure of Communication
Authors: Kelly Séamas , Jones Matthew
Published: July 2002

Communication technologies can supplement, but never supplant, the value of social bonds and trusting relationships.
Packet delay in models of data networks
Authors: Fukś Henryk , Lawniczak Anna T. , Volkov Stanislav
Published: July 2002

We investigate individual packet delay in a model of data networks with table-free, partial table and full table routing. We present analytical estimation for the average packet delay in a network with small partial routing table. Dependence of the delay on the size of the network and on the size of the partial routing table is examined numerically. Consequences for network scalability are discussed.
On the statistical independence of compound pseudorandom numbers over part of the period
Authors: Levin Mordechay B.
Published: July 2002

This article deals with the compound methods with modulus
m
for generating uniform pseudorandom numbers, which have been introduced recently. Equidistribution and statistical independence properties of the generated sequences over part of the period are studied based on the discrepancy of
d
-tuples of successive pseudorandom numbers. It is shown that there exist parameters in compound methods such that the discrepancy over part of the period of the corresponding point sets in the
d
-dimensional unit cube is of an order magnitude of
O
(
N
-1/2
(log
N
)
d+3
) for all
N
=1, …,
m
. This result is applied to the compound nonlinear, inversive and explicit inversive congruential methods.
Introduction
Authors: Lewis Michael , Jacobson Jeffrey
Published: July 2002

Serious computational results are derived from computer-based games.
Compression of particle data from hierarchical approximate methods
Authors: Yang Dow-Yung , Grama Ananth , Sarin Vivek , Ramakrishnan Naren
Published: July 2002

This article presents an analytical and computational framework for the compression of particle data resulting from hierarchical approximate treecodes such as the
Barnes--Hut
and
Fast Multipole Methods
. Due to approximations introduced by hierarchical methods, various parameters (such as position, velocity, acceleration, potential) associated with a particle can be bounded by distortion radii. Using this distortion radii, we develop storage schemes that guarantee error bounds while maximizing compression. Our schemes make extensive use of spatial and temporal coherence of particle behavior and yield compression ratios higher than 12:1 over raw data, and 6:1 over gzipped (LZ) raw data for selected simulation instances. We demonstrate that for uniform distributions with 2M particles, storage requirements can be reduced from 24 MB to about 1.8 MB (about 7 bits per particle per timestep) for storing particle positions. This is significant because it enables faster storage/retrieval, better temporal resolution, and improved analysis. Our results are shown to scale from small systems (2K particles) to much larger systems (over 2M particles). The associated algorithm is asymptotically optimal in computation time (
O
(
n
)) with a small constant. Our implementations are demonstrated to run extremely fast---much faster than the time it takes to compute a single time-step advance. In addition, our compression framework relies on a natural hierarchical representation upon which other analysis tasks such as segmented and window retrieval can be built.
A revised simplex method with integer Q-matrices
Authors: Azulay David-Olivier , Pique Jean-François
Published: July 2002

We describe a modification of the simplex formulas in which Q-matrices are used to implement exact computations with an integer multiprecision library. Our motivation comes from the need for efficient and exact incremental solvers in the implementation of constraint solving languages such as Prolog. We explain how to reformulate the problem and the different steps of the simplex algorithm. We compare some measurements obtained with integer and rational computations.
General technology mapping for field-programmable gate arrays based on lookup tables
Authors: Chowdhary Amit , Hayes John P.
Published: July 2002

We present a general technology-mapping methodology (TULIP) for field-programmable gate arrays (FPGAs) that can yield optimal results, and is applicable to any FPGA with a logic block composed of lookup tables (LUTs). We introduce the concept of a virtual switch to model the internal connections of a logic block with multiple LUTs; each configuration of virtual switches is called a multiple-LUT block (MLB). A logic block can be precisely defined by a small but complete set of representative configurations called an MLB basis. The MLB bases for various commercial FPGA families are demonstrated. Given a logic block represented by its MLB basis, technology mapping is precisely formulated as a graph-covering problem, which is transformed into a mixed integer-linear programming (MILP) optimization problem in order to achieve our optimality and generality objectives. The MILP model is solved using a general-purpose MILP solver tool. The results of using TULIP for mapping some ISCAS-85 benchmark circuits to a variety of logic blocks are presented. Circuits of a few hundred gates can be mapped directly in a few minutes. To map larger circuits to complex logic blocks, some approximation techniques are proposed based on partitioning the input circuit and simplifying the MLB basis. We show that these approximations result in close-to-optimal mappings of the benchmark circuits.
Umeå University
Authors: Stott Mike , Regan Alistair , Fallman Daniel
Published: July 2002

The Institute of Design was founded in 1989 and is part of
Umeå University
, which has a full-time enrollment of 24,000 students. The university is one of the largest in the north of Sweden and is situated about 600 km (about 373 mi) north of Stockholm and 300 km (about 186 mi) south of the Arctic Circle.The Institute of Design offers four educational programs. Currently about 90 students from representing more than 15 different nationalities are enrolled. One bachelor of arts degree program is offered in industrial design and is open to Swedish-speaking students only. Three two-year master's programs---in transportation design, advanced product design, and interaction design---were started in 1996 and are open to international students. The interaction design program accepts between eight and 10 students each year.
Constantine & Lockwood
Authors: Constantine Larry
Published: July 2002

Constantine & Lockwood, Ltd.
is a network of professionals providing training, design, and consulting services in product usability and user interface design to select clients worldwide.
Novel security techniques for online systems
Authors: Botting Richard
Published: July 2002

By ensuring entry to subsystems (zones) with different facilities and security levels, log-in procedures can do more than simply delay illicit access.
Computation-tuple sequences and object histories
Authors: Ginsburg Seymour , Tanaka Katsumi
Published: July 2002

A record-based, algebraically-oriented model is introduced for describing data for “object histories” (with computation), such as checking accounts, credit card accounts, taxes, schedules, and so on. The model consists of sequences of computation tuples defined by a computation-tuple sequence scheme (CSS). The CSS has three major features (in addition to input data): computation (involving previous computation tuples), “uniform” constraints (whose satisfaction by a computation-tuple sequence
u
implies satisfaction by every interval of
u
), and specific sequences with which to start the valid computation-tuple sequences. A special type of CSS, called “local,” is singled out for its relative simplicity in maintaining the validity of a computation-tuple sequence. A necessary and sufficient condition for a CSS to be equivalent to at least one local CSS is given. Finally, the notion of “local bisimulatability” is introduced for regarding two CSS as conveying the same information, and two results on local bisimulatability in connection with local CSS are established.
AGM: a dataflow database machine
Authors: Bic Lubomir , Hartmann Robert L.
Published: July 2002

In recent years, a number of database machines consisting of large numbers of parallel processing elements have been proposed. Unfortunately, there are two main limitations in database processing that prevent a high degree of parallelism; these are the available I/O bandwidth of the underlying storage devices and the concurrency control mechanisms necessary to guarantee data integrity. The main problem with conventional approaches is the lack of a computational model capable of utilizing the potential of any significant number of processing elements and storage devices and, at the same time, preserving the integrity of the database.

This paper presents a database model and its associated architecture, which is based on the principles of data-driven computation. According to this model, the database is represented as a network in which each node is conceptually an independent, asynchronous processing element, capable of communicating with other nodes by exchanging messages along the network arcs. To answer a query, one or more such messages, called tokens, are created and injected into the network. These then propagate asynchronously through the network in search of results satisfying the given query.

The asynchronous nature of processing permits the model to be mapped onto a computer architecture consisting of large numbers of independent disk units and processing elements. This increases both the available I/O bandwidth as well as the processing potential of the machine. At the same time, new concurrency control and error recovery mechanisms are necessary to cope with the resulting parallelism.
On the path length of binary trees
Authors: Klein Rolf , Wood Derick
Published: July 2002

It is shown that the external path length of a binary tree is closely related to the ratios of means of certain integers and establish the upper bound

External Path Length ≤

N(log
2
N + Δ - log
2
Δ - 0.6623),

where
N
denotes the number of external nodes in the tree and Δ is the difference in length between a longest and shortest path. Then it is proved that this bound is tight up to an
o(N)
term if Δ ≤ √N. If
Δ > √N
, we contstruct binary trees whose external path length is at least as large as

N(log
2
N + Φ(N, Δ)Δ - log
2
Δ -4)

, where
Φ(N, Δ) = 1/(1 + 2(Δ/N))
.
The equivalence of the subregion representation and the wall representation for a certain class of rectangular dissections
Authors: Kundu S.
Published: July 2002

A rectangular dissection is a partition of a rectangular space R info n ≠ 1 disjoint rectangles {r
1
, r
2
, . . ., r
n
. Two classes of dissections that are of particular interest in floor-space design and very-large-scale integration (VLSI) space partitioning are called
T-
plans and T*-plans, where the T*-plans form a subclass of the
T-
plans. We consider here the subregion tree representation t(D) of a T*-plan D, which describes the successive partitioning operations by which the dissection D is derived. There are four types of partitioning operations in a T*-plan: (1) the horizontal partitioning; (2) the vertical partitioning; (3) the left-spiral partitioning; and (4) the right-spiral partitioning. We show that for a T*-plan the subregion representation and the wall representation are equivalent in the sense that one can be obtained from the other in a unique fashion. The importance of this equivalence property lies in that while the two representations allow different types of design constraints to be represented in a more natural way, these constraints may be converted to the same representation for a more efficient solution of the design problem.
A problem-oriented inferential database system
Authors: Lozinskii Eliezer L.
Published: July 2002

Recently developed inferential database systems face some common problems: a very fast growth of search space and difficulties in recognizing inference termination (especially for recursive axioms). These shortcomings stem mainly from the fact that the inference process is usually separated from database operations. A problem-oriented inferential system i8 described which refers to the database prior to query (or subquery) processing, so that the inference from the very beginning is directed by data relevant to the query. A multiprocessor implementation of the system is presented based on a computer network conforming to database relations and axioms. The system provides an efficient indication of query termination, and is complete in the sense that it produces all correct answers to a query in a finite time.
The orders of equidistribution of subsequences of some asymptotically random sequences
Authors: Koopman Raymond F.
Published: July 2002

The orders of equidistribution of subsequences of every
n
th
term of the asymptotically random sequence given by Tootill, Robinson, and Eagle
[5], and of six other asymptotically random sequences, were determined for various values of n and of the number of bits to which each term in the sequence is read. Deficiencies in equidistribution were found to be small enough to qualify the sequences for use in applications with fixed, as well as variable, dimensionality requirements. An improved initialization algorithm is also given.
Storing text retrieval systems on CD-ROM: compression and encryption considerations
Authors: Klein Shmuel T. , Bookstein Abraham , Deerwester Scott
Published: July 2002

The emergence of the CD-ROM as a storage medium for full-text databases raises the question of the maximum size database that can be contained by this medium. As an example, the problem of storing the Trésor de la Langue Française on a CD-ROM is examined in this paper. The text alone of this database is 700 megabytes long, more than a CD-ROM can hold. In addition, the dictionary and concordance needed to access these data must be stored. A further constraint is that some of the material is copyrighted, and it is desirable that such material be difficult to decode except through software provided by the system. Pertinent approaches to compression of the various files are reviewed, and the compression of the text is related to the problem of data encryption: Specifically, it is shown that, under simple models of text generation, Huffman encoding produces a bit-string indistinguishable from a representation of coin flips.
The 1984-1985 Taulbee survey
Authors: Gries David
Published: July 2002

Presented here is the Computer Science Board's survey on the production and employment of Ph.D.'s and faculty in computer science and engineering.
The 1987—1988 Taulbee survey
Authors: Gries David , Marsh Dorothy
Published: July 2002

The Computing Research Board's 1987-1988 Taulbee Survey includes the latest statistics on production and employment of Ph.D.'s and faculty in computer science and engineering. Included also are departments offering Ph.D.'s in computer engineering.
Performance of a two-headed disk system when serving database queries under the scan policy
Authors: Manolopoulos Y. , Kollias J. G.
Published: July 2002

Disk drives with movable two-headed arms are now commercially available. The two heads are separated by a fixed number of cylinders. A major problem for optimizing disk head movement, when answering database requests, is the specification of the optimum number of cylinders separating the two heads. An earlier analytical study assumed a FCFS model and concluded that the optimum separation distance should be equal to 0.44657 of the number of cylinders
N
of the disk. This paper considers that the SCAN scheduling policy is used in file access, and it applies combinatorial analysis to derive exact formulas for the expected head movement. Furthermore, it is proven that the optimum separation distance is
N/2
- 1 (⌈
N
/2 - 1⌉ and ⌊
N
/2 - 1⌋) if
N
is even (odd). In addition, a comparison with a single-headed disk system operating under the same scheduling policy shows that if the two heads are optimally spaced, then the mean seek distance is less than one-half of the value obtained with one head. In fact that the SCAN policy is used for many database applications (for example,batching and secondary key retrieval) demonstrates the potential of two-headed disk systems for improving the performance of database systems.
A uniform approach toward handling atomic and structured information in the nested relational database model
Authors: Gyssens Marc , van Gucht Dirk
Published: July 2002

The algebras and query languages for nested relations defined thus far do not allow us to “flatten” a relation scheme by disregarding the internal representation of data. In real life, however, the degree in which the structure of certain information, such as addresses, phone numbers, etc., is taken into account depends on the particular application and may even vary in time. Therefore, an algebra is proposed that does allow us to simplify relations by disregarding the internal structure of a certain class of information. This algebra is based on a careful manipulation of attribute names. Furthermore, the key operator in this algebra, called “copying,” allows us to deal with various other common queries in a very uniform manner, provided these queries are interpreted as operations on classes of semantically equivalent relations rather than individual relations. Finally, it is shown that the proposed algebra is complete in the sense of Bancilhon and Paredaens.
Generalized predictive TCQ of speech
Authors: Marcellin Michael W. , Fischer Thomas R.
Published: July 2002

Trellis coded quantization (TCQ) is incorporated into a noise feedback coding structure for encoding sampled speech. The effects of varying the encoding delay and the number of symbols released per trace-back on system performance and complexity are investigated.
Indefinite integration with validation
Authors: Corliss George , Krenz Gary
Published: July 2002

We present an overview of two approaches to validated one-dimensional indefinite integration. The first approach is to find an inclusion of the integrand, then integrate this inclusion to obtain an inclusion of the indefinite integral. Inclusions for the integrand may be obtained from Taylor polynomials, Tschebyscheff polynomials, or other approximating forms which have a known error term. The second approach finds an inclusion of the indefinite integral directly as a linear combination of function evaluations plus an interval-valued error term. This requires a self-validating form of a quadrature formula such as Gaussian quadrature. In either approach, composite formulae improve the accuracy of the inclusion.

The result of the validated indefinite integration is an algorithm which may be represented as a character string, a subroutine in a high-level programming language such as Pascal-SC or Fortran, or as a collection of data. An example is given showing the application of validated indefinite integration in constructing a validated inclusion of the error function, erf(
x
).
Concurrency and availability as dual properties of replicated atomic data
Authors: Herlihy M.
Published: July 2002

A replicated data object is a typed object that is stored redundantly at multiple locations in a distributed system. Each of the object's operations has a set of quorums, which are sets of sites whose cooperation is needed to execute that operation. A quorum assignment associates each operation with its set of quorums. An operation's quorums determine its availability, and the constraints governing an object's quorum assignments determine the range of availability properties realizable by replication.

In this paper, the restrictions on quorum assignment imposed by three kinds of atomicity mechanisms found in the literature are analyzed: (1) serial schemes, in which replication and atomicity are implemented independently at different levels in the system, (2) static schemes, in which the transaction serialization order is predetermined, and (3) hybrid schemes in which the serialization order emerges dynamically.

The following results are derived: (1) Although serial schemes place the strongest restrictions on concurrency, they place the weakest restrictions on availability. (2) Although hybrid and static mechanisms place incomparable restrictions on concurrency, hybrid mechanisms place weaker restrictions on availability. (3) Bounding the maximum depth of transaction nesting strengthens restrictions on concurrency for all classes, but weakens restrictions on availability for hybrid schemes only. Concurrency and availability are best considered as dual properties: A complete analysis of an atomicity mechanism should take both into account.
Logic-based approach to semantic query optimization
Authors: Chakravarthy Upen S. , Grant John , Minker Jack
Published: July 2002

The purpose of semantic query optimization is to use semantic knowledge (e.g., integrity constraints) for transforming a query into a form that may be answered more efficiently than the original version. In several previous papers we described and proved the correctness of a method for semantic query optimization in deductive databases couched in first-order logic. This paper consolidates the major results of these papers emphasizing the techniques and their applicability for optimizing relational queries. Additionally, we show how this method subsumes and generalizes earlier work on semantic query optimization. We also indicate how semantic query optimization techniques can be extended to databases that support recursion and integrity constraints that contain disjunction, negation, and recursion.
Chemical equilibrium systems as numerical test problems
Authors: Meintjes Keith , Morgan Alexander P.
Published: July 2002

A system of nonlinear equations has been used as a test case by at least two authors. This system is purported to describe the equilibrium of the products of hydrocarbon combustion. The given system does not describe the stated physical problem, a fact which invalidates it as a test of solution methods for chemical equilibrium systems. In this note, the problem is correctly stated and then solved by the method of element variables.
Disaster recovery planning for academic computing centers
Authors: Rohde Renate , Haskett Jim
Published: July 2002

Planning for recovery from a disaster is quickly becoming recognized as a necessity for higher education computing installations. This article presents a structural framework, describes the stages, and tells how to implement a disaster recovery plan specifically geared to an academic computing organization.
Personal computing: simple complexity and COMDEX
Authors: Press Larry
Published: July 2002

One of today's emerging paradigms is the view that complex behavior or form can emerge from the interaction of relatively simple components, if you have enough of them and they have enough time to do whatever they do. The emergent behavior or form might seem systematic or chaotic. Some examples are neural nets, cellular automata, fractals, electronic mail networks, market economies, whirlpools, and snowflakes. Years ago, similar systems were often called self-organizing, and they were found in models of memory, pattern recognition, multilevel stores, and libraries. The area languished, however, awaiting the development of theory and powerful hardware. Personal workstations played an important role in facilitating experimentation and mass market personal computers are now up to the task.
Computer-aided modeling and planning (CAMP)
Authors: Sagie Ike
Published: July 2002

Many planning methods are based on mathematical modeling. A multitude of computer aids covers different facets of the planning activity: data management, linear programming, statistical analysis, graphics, and word processing. However, the diversity and complexity of the available software inhibit the widespread use of computers for planning.

The integrated Computer-Aided Modeling and Planning (CAMP) system offers a simple and coherent tool for the planner. A Data Definition Language provides the means for building data banks; a Model Definition Language provides the means for defining mathematical models featuring abstract linear programming, advanced array arithmetics, and assertions; a Picture Definition Language facilitates formation of tables and diagrams; a Text Definition Language combines word processing with illustrations of modeling results. The man-machine interface is based on interactive panels for controlling the planning process and on a command language for analyzing modeling results. A multilingual capability allows selection of the national language for interfacing with the system.

The architecture of CAMP is presented, and its design, implementation, and use in regional planning are discussed.
Note on blended linear multistep formulas
Authors: Skeel Robert D. , Vu Thu V.
Published: July 2002

The blended linear multistep methods of Skeel and Kong (1977) are fairly simply expressed in Nordsieck form, but the underlying multistep method turns out to be much more complicated.
SCISOR: extracting information from on-line news
Authors: Jacobs P. S. , Rau Lisa F.
Published: July 2002

The future of natural language text processing is examined in the SCISOR prototype. Drawing on artificial intelligence techniques, and applying them to financial news items, this powerful tool illustrates some of the future benefits of natural language analysis through a combination of bottom-up and top-down processing.
Stellar Structure and Evolution: Deductions from Hipparcos
Authors: Lebreton Yveline
Published: July 2002

▪ Abstract  During the last decade, the understanding of fine features of the structure and evolution of stars has become possible as a result of enormous progress made in the acquisition of high-quality observational and experimental data, and of new developments and refinements in the theoretical description of stellar plasmas. The confrontation of high-quality observations with sophisticated stellar models has allowed many aspects of the theory to be validated, and several characteristics of stars relevant to Galactic evolution and cosmology to be inferred. This paper is a review of the results of recent studies undertaken in the context of the Hipparcos mission, taking benefit of the high-quality astrometric data it has provided. Successes are discussed, as well as the problems that have arisen and suggestions proposed to solve them. Future observational and theoretical developments expected and required in the field are also presented.
Interventional and Intraoperative Magnetic Resonance Imaging
Authors: Kettenbach J. , Kacher D. F. , Koskinen S. K. , Silverman Stuart G. , Nabavi A. , Gering Dave , Tempany Clare M. C. , Schwartz R. B. , Kikinis R. , Black P. M. , Jolesz F. A.
Published: July 2002

▪ Abstract  The goal of the Image Guided Therapy Program, as the name implies, is to develop the use of imaging to guide minimally invasive therapy. The program combines interventional and intraoperative magnetic resonance imaging (MRI) with high-performance computing and novel therapeutic devices. In clinical practice the multidisciplinary program provides for the investigation of a wide range of interventional and surgical procedures. The Signa SP 0.5 T superconducting MRI system (GE Medical Systems, Milwaukee, WI) has a 56-cm-wide vertical gap, allowing access to the patient and permitting the execution of interactive MRI-guided procedures. This system is integrated with an optical tracking system and utilizes flexible surface coils and MRI-compatible displays to facilitate procedures. Images are obtained with routine pulse sequences. Nearly real-time imaging, with fast gradient-recalled echo sequences, may be acquired at a rate of one image every 1.5 s with interactive image plane selection. Since 1994, more than 800 of these procedures, including various percutaneous procedures and open surgeries, have been successfully performed at Brigham and Women's Hospital (Boston, MA).
Electrostatic Mechanisms of DNA Deformation
Authors: Williams Loren Dean , Maher III L. James
Published: July 2002

▪ Abstract  The genomes of higher cells consist of double-helical DNA, a densely charged polyelectrolyte of immense length. The intrinsic physical properties of DNA, as well as the properties of its complexes with proteins and ions, are therefore of fundamental interest in understanding the functions of DNA as an informational macromolecule. Because individual DNA molecules often exceed 1 cm in length, it is clear that DNA bending, folding, and interaction with nuclear proteins are necessary for packaging genomes in small volumes and for integrating the nucleotide sequence information that guides genetic readout. This review first focuses on recent experiments exploring how the shape of the densely charged DNA polymer and asymmetries in its surrounding counterion distribution mutually influence one another. Attention is then turned to experiments seeking to discover the degree to which asymmetric phosphate neutralization can lead to DNA bending in protein-DNA complexes. It is argued that electrostatic effects play crucial roles in the intrinsic, sequence-dependent shape of DNA and in DNA shapes induced by protein binding.
Rheological Properties of Water Ice—Applications to Satellites of the Outer Planets
Authors: Durham WB , Stern LA
Published: July 2002

▪ Abstract  The icy moons of the outer solar system have not been quiescent bodies, in part because many have a substantial water component and have experienced significant internal heating. We can begin to understand the thermal evolution of the moons and the rate of viscous relaxation of surface topography because we now have good constraints on how ice (in several of its polymorphic forms) flows under deviatoric stress at planetary conditions. Details of laboratory-derived flow laws for pure, polycrystalline ice are reviewed in detail. One of the more important questions at hand is the role of ice grain size. Grain size may be a dynamic quantity within the icy moons, and it may (or may not) significantly affect rheology. One recent beneficiary of revelations about grain-size-sensitive flow is the calculation of the rheological structure of Europa's outer ice shell, which may be no thicker than 20 km.