bluuebunny/crossref_metadata_2025 huggingface dataset:
On design principles for a molecular computer
Authors: Conrad Michael
Published: July 2002

If the unique information-processing capabilities of protein enzymes could be adapted for computers, then evolvable, more efficient systems for such applications as pattern recognition and process control are in principle possible.
The click modular router
Authors: Kohler Eddie , Morris Robert , Chen Benjie , Jannotti John , Kaashoek M. Frans
Published: July 2002

Clicks is a new software architecture for building flexible and configurable routers. A Click router is assembled from packet processing modules calledelements. Individual elements implement simple router functions like packet classification, queuing, scheduling, and interfacing with network devices. A router configurable is a directed graph with elements at the vertices; packets flow along the edges of the graph. Several features make individual elements more powerful and complex configurations easier to write, includingpull connections,which model packet flow drivn by transmitting hardware devices, andflow-based router context,which helps an element locate other interesting elements. Click configurations are modular and easy to extend. A standards-compliant Click IP router has 16 elements on its forwarding path; some of its elements are also useful in Ethernet switches and IP tunnelling configurations. Extending the IP router to support dropping policies, fairness among flows, or Differentiated Services simply requires adding a couple of element at the right place. On conventional PC hardware, the Click IP router achieves a maximum loss-free forwarding rate of 333,000 64-byte packets per second, demonstrating that Click's modular and flexible architecture is compatible with good performance.
Laser optical disk
Authors: Fujitani Larry
Published: July 2002

Commercially available only recently, the optical disk drive uses a laser beam to burn impressions onto a plastic disk. Employing a highly focused beam rather than a diffuse magnetic field to write, the laser optical disk drive yields storage densities up to 10 times those of magnetic disks.
Introduction to the fifth generation
Authors: McCorduck Pamela
Published: July 2002

In October 1981, Japan's Ministry of International Trade and Industry (MITI) sponsored a conference to announce a new national project. Alongside national projects in supercomputing and robotics, there would be an effort to develop a new generation (the fifth, by their reckoning) of computers.
Reflections on software research
Authors: Ritchie Dennis M.
Published: July 2002

Can the circumstances that existed in Bell Labs that nurtured the UNIX project be produced again
?
Analysis of pointer “rotation”
Authors: Suzuki Norihisa
Published: July 2002

Two high-level pointer operations, rotation and slide, reduce conceptual difficulties when writing pointer programs and increase the reliability of programs. We analyze theoretically as well as empirically why these operations are more convenient and introduce a mechanically checkable notion of the
safety
of rotations. Several examples show that safety is a good indication of program correctness. Examples of list marking and list copying programs demonstrate the utility of these operations.
Algorithms for computing the volume and other integral properties of solids. I. known methods and open issues
Authors: Lee Yong Tsui , Requicha Aristides A. G.
Published: July 2002

The volume, moments of inertia, and similar properties of solids are defined by triple (volumetric) integrals over subsets of three-dimensional Euclidean space. The automatic computation of such integral properties for geometrically complex solids is important in CAD/CAM, robotics, and other fields and raises interesting mathematical and computational problems that have received little attention from numerical analysts and computer scientists. This paper summarizes the known methods for calculating integral properties of solids that may be geometrically complex and identifies some significant gaps in our current knowledge.
Partial-match retrieval using indexed descriptor files
Authors: Pfaltz John L. , Berman William J. , Cagley Edgar M.
Published: July 2002

In this paper we describe a practical method of partial-match retrieval in very large data files. A binary code word, called a descriptor, is associated with each record of the file. These record descriptors are then used to form a derived descriptor for a block of several records, which will serve as an index for the block as a whole; hence, the name “indexed descriptor files.”

First the structure of these files is described and a simple, efficient retrieval algorithm is presented. Then its expected behavior, in terms of storage accesses, is analyzed in detail. Two different file creation procedures are sketched, and a number of ways in which the file organization can be “tuned” to a particular application are suggested.
Assembling code for machines with span-dependent instructions
Authors: Szymanski Thomas G.
Published: July 2002

Many modern computers contain instructions whose lengths depend on the distance from a given instance of such an instruction to the operand of that instruction. This paper considers the problem of minimizing the lengths of programs for such machines. An efficient solution is presented for the case in which the operand of every such “span-dependent” instruction is either a label or an assembly-time expression of a certain restricted form. If this restriction is relaxed by allowing these operands to be more general assembly-time expressions, then the problem is shown to be NP-complete.
Event manipulation for discrete simulations requiring large numbers of events
Authors: Ulrich Ernst G.
Published: July 2002

The event-manipulation system presented here consists of two major parts. The first part addresses the familiar problem of event scheduling efficiency when the number of scheduled events grows large. The second part deals with the less apparent problem of providing efficiency and flexibility as scheduled events are accessed to be executed. Additional features and problems dealt with include the proper handling of simultaneous events; that certain events must be created, scheduled, and executed at the same points in simulated time; that infinite loops caused by the concatenation of such “zero-time” events are possible and must be diagnosed; that maintaining various event counts is practical and economical; and that a capability for handling “time-displaceable” events is desirable and possible.
An example of hierarchical design and proof
Authors: Spitzen Jay M. , Levitt Karl N. , Robinson Lawrence
Published: July 2002

Hierarchical programming is being increasingly recognized as helpful in the construction of large programs. Users of hierarchical techniques claim or predict substantial increases in productivity and in the reliability of the programs produced. In this paper we describe a formal method for hierarchical program specification, implementation, and proof. We apply this method to a significant list processing problem and also discuss a number of extensions to current programming languages that ease hierarchical program design and proof.
More on algorithms that reveal properties of floating point arithmetic units
Authors: Gentleman W. Morven , Marovich Scott B.
Published: July 2002

In the interests of producing portable mathematical software, it is highly desirable for a program to be able directly to obtain fundamental properties of the environment in which it is to run. The installer would then not be obliged to change appropriate magic constants in the source code, and the user would not have to provide information he may very well not understand. Until the standard definitions of programming languages are changed to require builtin functions that provide this information [1, 3], we will have to resort to writing routines that discover it.
Programming languages, natural languages, and mathematics
Authors: Naur Peter
Published: July 2002

Some social aspects of pro gramming are illuminated through analogies with similar aspects of mathematics and natural languages. The split between pure and applied mathematics is found similarly in programming. The development of natural languages toward flexionless, word-order based language types speaks for programming language design based on general, abstract constructs. By analogy with incidents of the history of artificial, auxiliary languages it is suggested that Fortran and Cobol will remain dominant for a long time to come. The most promising avenues for further work of wide influence are seen to be high quality program literature (i.e. programs) of general utility and studies of questions related to program style.
Automatic segmentation of cyclic program structures based on connectivity and processor timing
Authors: Lowe Thomas C.
Published: July 2002

Time-shared, multiprogrammed, and overlayed batch systems frequently require segmentation of computer programs into discrete portions. These program portions are transferred between executable and peripheral storage whenever necessary; segmentation of programs in a manner that reduces the frequency of such transfers is the subject of this paper. Segmentation techniques proposed by C. V. Ramamoorthy are subject to limitations that arise when the preferred segment size is not compatible with the physical restrictions imposed by the available computing equipment. A generalization of Ramamoorthy's suggestions is made in order to allow their application when circumstances are other than ideal.
Java consistency
Authors: Gontmakher Alex , Schuster Assaf
Published: July 2002

The Java Language Specification (JLS) [Gosling et al. 1996] provides an operational definition for the consistency of shared variables. The definition remains unchanged in the JLS 2nd edition, currently under peer review, which relies on a specific abstract machine as its underlying model, is very complicated. Several subsequent works have tried to simplify and formalize it. However, these revised definitions are also operational, and thus have failed to highlight the intuition behind the original specification. In this work we provide a complete nonoperational specification for Java and for the JVM, excluding synchronized operations. We provide a simpler definition, in which we clearly distinguish the consistency model that is promised to the programmer from that which should be implemented in the JVM. This distinction, which was implicit in the original definition, is crucial for building the JVM. We find that the programmer model is strictly weaker than that of the JVM, and precisely define their discrepancy. Moreover, our definition is independent of any specific (or even abstract) machine, and can thus be used to verify JVM implementations and compiler optimizations on any platform. Finally, we show the precise range of consistency relaxations obtainable for the Java memory model when a certain compiler optimization— called
prescient stores
in JLS—is applicable.
Sorting in a paging environment
Authors: Brawn Barbara S. , Gustavson Frances G. , Mankin Efrem S.
Published: July 2002

This sorting study was part of an extensive measurement project undertaken on the M44/44X, an experimental paging system which was conceived and implemented at IBM Research in order to explore the virtual machine concept. The study was concerned with the implementation of sorting procedures in the context of the dynamic paging environment characteristic of virtual memory machines. Descriptions of the experimental sort programs and analysis of the performance measurement results obtained for them are presented. The insight gained from the experimental effort is used to arrive at a set of broad guidelines for writing sort programs for a paging environment.
Display procedures
Authors: Newman William M.
Published: July 2002

Although the use of structured display files is widespread in interactive computer graphics, these structures present a number of problems which tend to restrict their generality and usefulness. This paper discusses some of these problems, and suggests an alternative approach to display system design which avoids the use of structured display files.

This technique employs display procedures to generate information for display. By including transformations within calls to these procedures it is possible both to simplify the specification of pictures and to speed up their generation. Display procedures permit picture elements to be defined conditionally and also facilitate the processing of inputs from pointing devices. The paper is illustrated by examples from a version of the EULER language in which display procedures were implemented.
Automation of etching-pattern layout
Authors: Aramaki Itaru , Kawabata Tomokazu , Arimoto Kazuhiko
Published: July 2002

HELP (Heuristic Etching-Pattern Layout Program) is an application program developed to computerize the tedious and error-prone although vitally important wiring design of printed circuit boards. HELP helps automate a design stage one step closer to production than logical design. It can be used to design wiring patterns of two-layer circuit boards on which ICs in dual-in-line packages as well as discrete components such as transistors and resistors have been placed.

HELP employs two methods of wiring. One is the heuristic method, which simulates human approaches to wiring design, and the other is the theoretically interesting but time-consuming method of maze-running, based on the Lee's algorithm.

HELP performs more than 90 percent of required wiring by the heuristic method. The maze-running method finds an optimal path with respect to a performance function for each point-to-point, and point-to-line connection. It can bring the number of successful wiring connections very close to 100 percent.
A base for a mobile programming system
Authors: Orgass Richard J. , Waite William M.
Published: July 2002

An algorithm for a macro processor which has been used as the base of an implementation, by bootstrapping, of processors for programming languages is described. This algorithm can be easily implemented on contemporary computing machines. Experience with programming languages whose implementation is based on this algorithm indicates that such a language can be transferred to a new machine in less than one man-week without using the old machine.
A modular computer sharing systems
Authors: Baskin Herbert B. , Horowitz Elsa B. , Tennison Robert D. , Rittenhouse Larry E.
Published: July 2002

An alternative approach to the design and organization of a general purpose interactive multiterminal computing system is presented. The system organization described is a conceptually simple arrangement of a bank of interchangeable computers, each of which is a memory/proputor pair, that are assigned to process terminal jobs as they arrive. One of the computers serves as the master or control computer and supervises the collection and distribution of messages from and to the remote terminals. In the simplest form there is a disk drive for each connected terminal. A crosspoint switching network allows any such disk drive to be connected to any computer in the bank, under control of the control computer. Thus, while each active terminal user “occupies” a dedicated disk drive, he may share the computer with many other terminal users in a simple manner. The ratio of users to computers is dependent on both the size and power of the machines used and the computation requirements of the particular mix of users.

This system organization is inherently a simpler and therefore more reliable approach to time-sharing computers and has the potential of a highly available system at relatively low cost. Economic configurations are possible for a range of systems sizes that span at least one order of magnitude. Finally, problem programs developed by remote terminal users can be run on a dedicated batch system if compatible computers are used.
Description of basic algorithm DETAB/65 preprocessor
Authors: Callahan Michael D. , Chapman Anson E.
Published: July 2002

The basic algorithm for the conversion of decision tables into COBOL code is contained in the generator portion of the DETAB/65 preprocessor. The generator analyzes a decision table and produces simple COBOL conditional statements. Core storage is saved by using queueing techniques and extensive indexing and also by outputting the code as it is generated, a line at a time. The only optimization attempted is the elimination of obviously unnecessary tests on certain conditions in the decision table.

Since the preprocessor and this language associated with it were developed for COBOL users, the preprocessor was written in a modular form in required COBOL-61.
Operating Systems: On overcoming high-priority paralysis in multiprogramming systems
Authors: Stevens David F.
Published: July 2002

High-priority paralysis is the degradation that can occur in multiprogramming systems when scheduling is based primarily on preassigned priorities. It can be alleviated by modifying the scheduling algorithm to maximize the number of programs active at one time. The case history given in this paper indicates two general methods by which simultaneity can be increased. Possible refinements in the scheduling algorithm for future improvements are considered briefly.
GIT—a heuristic program for testing pairs of directed line graphs for isomorphism
Authors: Unger Stephen H.
Published: July 2002

Given a pair of directed line graphs, the problem of ascertaining whether or not they are isomorphic is one for which no
efficient
algorithmic solution is known. Since a straightforward enumerative algorithm might require 40 years of running time on a very high speed computer in order to compare two 15-node graphs, a more sophisticated approach seems called for. The situation is similar to that prevailing in areas such as game-playing and theorem-proving, where practical algorithms are unknown (for the interesting cases), but where various practical though only
partially
successful techniques are available. GIT—Graph Isomorphism Tester—incorporates a variety of processes that attempt to narrow down the search for an isomorphism, or to demonstrate that none exists. No one scheme is relied upon exclusively for a solution, and the program is designed to avoid excessive computation along fruitless lines. GIT has been written in the COMIT language and successfully tested on the IBM 7090.
Theory of dependence values
Authors: Meo Rosa
Published: July 2002

A new model to evaluate dependencies in data mining problems is presented and discussed. The well-known concept of the association rule is replaced by the new definition of dependence value, which is a single real number uniquely associated with a given itemset. Knowledge of dependence values is sufficient to describe all the dependencies characterizing a given data mining problem. The dependence value of an itemset is the difference between the occurrence probability of the itemset and a corresponding “maximum independence estimate.” This can be determined as a function of joint probabilities of the subsets of the itemset being considered by maximizing a suitable entropy function. So it is possible to separate in an itemset of cardinaltiy k the dependence inherited from its subsets of cardinality (k - 1) and the specific inherent dependence of that itemset. The absolute value of the difference between the probability p(
i
) of the event
i
that indicates the prescence of the itemset {a,b,... } and its maximum independence estimate is constant for any combination of values of 〈a,b,...〉. In addition, the Boolean function specifying the combination of values for which the dependence is positive is a parity function. So the determination of such combinations is immediate. The model appears to be simple and powerful.
Syntax macros and extended translation
Authors: Leavenworth B. M.
Published: July 2002

A translation approach is described which allows one to extend the syntax and semantics of a given high-level base language by the use of a new formalism called a syntax-macro. Syntax-macros define string transformations based on syntactic elements of the base language. Two types of macros are discussed, and examples are given of their use. The conditional generation of macros based on options and alternatives recognized by the scan are also described.
A short method for measuring error in a least-squares power series
Authors: Robinson S. M. , Struble G. W.
Published: July 2002

When fitting a curve to a set of points by means of a least-squares powers series, it is frequently desirable to obtain also a measure of the total error of the curve. Such error is most often measured by the size of the residual sum of squares and, while it is not infrequent for computer programs to provide this error sum along with the coefficients of the power series, in every case we have so far found this sum has been obtained by evaluating the series at every data point. This procedure requires that either the data be read through the machine a second time after the determination of the coefficients or that every data point be stored in the memory of the computer.
Computation's development critical to our society
Authors: Perlis Alan J.
Published: July 2002

The ACM's growth continues: we are now at 13,000 members; expenses also grow. Our professional membership does not spring from a uniformly trained group as in mathematics or physics or even economics. Instead, our increasing membership comes from what I might call intellectual adventures—pioneers in an over-organized society—who see great futures in computing at all levels of aspiration.
Specifying and using a partitionable group communication service
Authors: Fekete Alan , Lynch Nancy , Shvartsman Alex
Published: July 2002

Group communication services are becoming accepted as effective building blocks for the construction of fault-tolerant distributed applications. Many specifications for group communication services have been proposed. However, there is still no agreement about what these specifications should say, especially in cases where the services are
partitionable
, i.e., where communication failures may lead to simultaneous creation of groups with disjoint memberships, such that each group is unware of the existence of any other group. In this paper, we present a new, succinct specification for a view-oriented partitionable group communication service. The service associates each message with a particular
view
of the group membership. All send and receive events for a message occur within the associated view. The service provides a total order on the messages within each view, and each processor receives a prefix of this order. Our specification separates safety requirements from performance and fault-tolerance requirements. The safety requirements are expressed by an abstract, global
state machine
. To present the performance and fault-tolerance requirements, we include
failure-status input actions
in the specification; we then give properties saying that consensus on the view and timely message delivery are guaranteed in an execution provided that the execution
stabilizes
to a situation in which the failure-status stops changing and corresponds to consistently partioned system. Because consensus is not required in every execution, the specification is not subject to the existing impossibility results for partionable systems. Our specification has a simple implementation, based on the membership algorithm of Christian and Schmuck. We show the utility of the specification by constructing an ordered-broadcast application, using an algorithm (based on algorithms of Amir, Dolev, Keidar, and others) that reconciles information derived from different instantiations of the group. The application manages the view-change activity to build a shared sequence of messages, i.e., the per-view total orders of the group service are combined to give a universal total order. We prove the correctness and analyze the performance and fault-tolerance of the resulting application.
Testing Intrusion detection systems
Authors: McHugh John
Published: July 2002

In 1998 and again in 1999, the Lincoln Laboratory of MIT conducted a comparative evaluation of intrusion detection systems (IDSs) developed under DARPA funding. While this evaluation represents a significant and monumental undertaking, there are a number of issues associated with its design and execution that remain unsettled. Some methodologies used in the evaluation are questionable and may have biased its results. One problem is that the evaluators have published relatively little concerning some of the more critical aspects of their work, such as validation of their test data. The appropriateness of the evaluation techniques used needs further investigation. The purpose of this article is to attempt to identify the shortcomings of the Lincoln Lab effort in the hope that future efforts of this kind will be placed on a sounder footing. Some of the problems that the article points out might well be resolved if the evaluators were to publish a detailed description of their procedures and the rationale that led to their adoption, but other problems would clearly remain./par>
Query optimization on local area networks
Authors: Hevner Alan R. , Wu O. Q. , Yao S. B.
Published: July 2002

Local area networks
are becoming widely used as the database communication framework for sophisticated information systems. Databases can be distributed among stations on a network to achieve the advantages of performance, reliability, availability, and modularity. Efficient distributed query optimization algorithms are presented here for two types of local area networks:
address ring networks
and
broadcast networks
. Optimal algorithms are designed for
simple queries
. Optimization principles from these algorithms guide the development of effective heuristic algorithms for general queries on both types of networks. Several examples illustrate distributed query processing on local area networks.
Portability of syntax and semantics in DATALOG
Authors: Hafner Carole D. , Godden Kurt
Published: July 2002

This paper presents a discussion of the techniques developed and problems encountered during the design, implementation, and experimental use of a portable natural language processor. Datalog (for “database dialogue") is an experimental natural language query system, which was designed to achieve a maximum degree of portability and extendibility. Datalog uses a three-level architecture to provide both portability of syntax to new and extended tasks and portability of semantics to new database applications. The implementation of each of the three levels, the structures and conventions that control the interactions among them, and the way in which different aspects of the design contribute to portability are described. Finally, two specific, implemented examples are presented, showing how it was possible to transport or extend Datalog by changing only one “layer” of the system's knowledge and achieve correct processing of the extended input by the entire system.
The art and science of visualizing data
Authors: Frenkel Karen A.
Published: July 2002

"I manipulate the laser," the artist said, having exploited laboratory equipment. "This is a parallel pipeline systolic SIMD engine we call the 'Jell-O Engine,'" the animator/straight man announced, but not until he had decimated the practice of ray tracing. And officials from supercomputer centers declared the visualization of scientific data would define a new field, a revolutionary way of doing science.
Formal specification of a small example based on GKS
Authors: Duce D. A. , Fielding E. V. C. , Marshall L. S.
Published: July 2002

Implicit regeneration is a fundamental concept of the Graphical Kernel System (GKS), an IS0 International Standard, but it is difficult to understand as presented in the English language specification of GKS. Consequently, it is a good example to use in determining whether formal specification techniques can be used effectively to describe and clarify graphics concepts of this kind. The problem is first motivated informally with a description of GKS concepts and terminology. A formal specification of implicit regeneration using a simplified model is then presented, and the notation that is used for its formalization (VDM) is described. Finally, properties of implicit regeneration are formulated and the specification is proved to conform to these properties. This demonstrates the applicability of formal specification to graphics software, because a sufficiently precise description of a complicated concept is provided that enables its consistency to be checked against an intuitive understanding of the concept as derived from the GKS document.
Reading text from computer screens
Authors: Mills Carol Bergfeld , Weldon Linda J.
Published: July 2002

This paper reviews empirical studies concerning the readability of text from computer screens. The review focuses on the form and physical attributes of complex, realistic displays of text material. Most studies comparing paper and computer screen readability show that screens are less readable than paper. There are many factors that could affect the readability of computer screens. The factors explored in this review are the features of characters, the formatting of the screen, the contrast and color of the characters and background, and dynamic aspects of the screen. Numerous areas for future research are pinpointed.
A speech-act-based office modeling approach
Authors: Auramäki Esa , Lehtinen Erkki , Lyytinen Kalle
Published: July 2002

In this paper methods and principles that help to analyze offices as systems of communicative action are explored. In communicative action, office agents create commitments through symbolic means. A SAMPO (Speech-Act-based office Modeling aPprOach), which studies office activities as a series of speech acts creating, maintaining, modifying, reporting, and terminating commitments, is presented. The main steps and methods in the office system specification are outlined and their application illustrated through a simple example. In the final section advantages and disadvantages in the SAMPO are noted and some research directions for the future are suggested.
Eliminating go to's while preserving program structure
Authors: Ramshaw Lyle
Published: July 2002

Suppose we want to eliminate the local go to statements of a Pascal program by replacing them with multilevel loop exit statements. The standard ground rules for eliminating go to's require that we preserve the flow graph of the program, but they allow us to completely rewrite the control structures that glue together the program's atomic tests and actions. The go to's can be eliminated from a program under those ground rules if and only if the flow graph of that program has the graph-theoretic property named reducibility.

This paper considers a stricter set of ground rules, introduced by Peterson, Kasami, and Tokura, which demand that we preserve the program's original control structures, as well as its flow graph, while we eliminate its go to's. In particular, we are allowed to delete the go to statements and the labels that they jump to and to insert various exit statements and labeled repeat-endloop pairs for them to jump out of. But we are forbidden to change the rest of the program text in any way. The critical issue that determines whether go to's can be eliminated under these stricter rules turns out to be the static order of the atomic tests and actions in the program text. This static order can be encoded in the program's flow graph by augmenting it with extra edges. It can then be shown that the reducibility of a program's augmented flow graph, augmenting edges and all, is a necessary and sufficient condition for the eliminability of go to's from that program under the stricter rules.
Quantum lower bounds by polynomials
Authors: Beals Robert , Buhrman Harry , Cleve Richard , Mosca Michele , de Wolf Ronald
Published: July 2002

We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1}

N

in the
black-box
model. We show that the exponential quantum speed-up obtained for
partial
functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any
total
function: if a quantum algorithm computes some total Boolean function
f
with small error probability using
T
black-box queries, then there is a classical deterministic algorithm that computes
f
exactly with
O
(

Ts
6

) queries. We also give asymptotically tight characterizations of
T
for all symmetric
f
in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
Voice over IP
Authors: Varshney Upkar , Snow Andy , McGivern Matt , Howard Christi
Published: July 2002

How can voice over the Internet claim a greater share of the worldwide phone market from the voice infrastructure dominated for more than 100 years by the public-switched telephone network?
Meeting the virtual work imperative
Authors: Townsend Anthony M. , Hendrickson Anthony R. , DeMarie Samuel M.
Published: July 2002

How collaborative technologies can facilitate face-to-face meetings without the need to even be in the same room.
Visual search and mouse-pointing in labeled versus unlabeled two-dimensional visual hierarchies
Authors: Hornof Anthony J.
Published: July 2002

An experiment investigates (1) how the physical structure of a computer screen layout affects visual search and (2) how people select a found target object with a mouse. Two structures are examined---labeled visual hierarchies (groups of objects with one label per group) and unlabeled visual hierarchies (groups without labels). Search and selection times were separated by imposing a point-completion deadline that discouraged participants from moving the mouse until they found the target. The observed search times indicate that labeled visual hierarchies can be searched much more efficiently than unlabeled visual hierarchies, and suggest that people use a fundamentally different strategy for each of the two structures. The results have implications for screen layout design and cognitive modeling of visual search. The observed mouse-pointing times suggest that people use a slower and more accurate speed-accuracy operating characteristic to select a target with a mouse when visual distractors are present, which suggests that Fitts' law coefficients derived from standard mouse-pointing experiments may under-predict mouse-pointing times for typical human-computer interactions. The observed mouse-pointing times also demonstrate that mouse movement times for a two-dimensional pointing task can be most-accurately predicted by setting the
w
in Fitts' law to the width of the target along the line of approach.
Coming together to explore the intersections of HCI, experience design, and information architecture
Authors: Anderson Richard
Published: July 2002

SIGCHI's value has grown in recent years as it has reached out to and supported the development of HCI communities around the world [2]. SIGCHI's value is growing even more as it increasingly reaches out to communities that overlap with HCI and that approach HCI in diverse ways.
How not to lie with statistics: the correct way to summarize benchmark results
Authors: Fleming Philip J. , Wallace John J.
Published: July 2002

Using the arithmetic mean to summarize normalized benchmark results leads to mistaken conclusions that can be avoided by using the preferred method: the geometric mean.
Intelligence in scientific computing
Authors: Abelson Harold , Eisenberg Michael , Halfant Matthew , Katzenelson Jacob , Sacks Elisha , Sussman Gerald J. , Wisdom Jack , Yip Ken
Published: July 2002

The authors discuss the development of intelligent techniques appropriate for the automatic preparation, execution, and control of numerical experiments.
Polynomial-time algorithm for the orbit problem
Authors: Kannan R. , Lipton R. J.
Published: July 2002

The accessibility problem for linear sequential machines [12] is the problem of deciding whether there is an input
x
such that on
x
the machine starting in a given state
q
1
goes to a given state
q
2
. Harrison shows that this problem is reducible to the following simply stated linear algebra problem, which we call the "orbit problem":

Given (
n, A, x, y
), where
n
is a natural number and
A, x,
and
y
are
n
x
n
,
n
x
1, and
n
x
1 matrices of rationals, respectively, decide whether there is a natural number
I
such that

A
i
x

=
y
.

He conjectured that the orbit problem is decidable. No progress was made on the conjecture for ten years until Shank [22] showed that if
n
is fixed at 2, then the problem is decidable. This paper shows that the orbit problem for general
n
is decidable and indeed decidable in polynomial time. The orbit problem arises in several contexts; two of these, linear recurrences and the discrete logarithm problem for polynomials, are discussed, and we apply our algorithm for the orbit problem in these contexts.
How to share memory in a distributed system
Authors: Upfal Eli , Wigderson Avi
Published: July 2002

The power of shared-memory in models of parallel computation is studied, and a novel distributed data structure that eliminates the need for shared memory without significantly increasing the run time of the parallel computation is described. More specifically, it is shown how a complete network of processors can deterministically simulate one PRAM step in
O
(log
n
/(log log
n
)
2
) time when both models use
n
processors and the size of the PRAM's shared memory is polynomial in
n
. (The best previously known upper bound was the trivial
O
(
n
)). It is established that this upper bound is nearly optimal, and it is proved that an on-line simulation of
T
PRAM steps by a complete network of processors requires Ω(
T
(log
n/
log log
n
)) time.

A simple consequence of the upper bound is that an Ultracomputer (the currently feasible general-purpose parallel machine) can simulate one step of a PRAM (the most convenient parallel model to program) in
O
((log
n
)
2
log log
n
) steps.
Blending parametric surfaces
Authors: Filip Daniel J.
Published: July 2002

A blending surface is a surface that smoothly connects two given surfaces along two arbitrary curves, one on each surface. This is particularly useful in the modeling operations of filleting a sharp edge between joining surfaces or connecting disjoint surfaces. In this paper we derive a new surface formulation for representing surfaces which are blends of parametric surfaces. The formulation has the advantage over the traditional rational polynomial approach in that point and normal values have no gaps between the blending surface and the base surfaces. Shape control parameters that control the cross-sectional shape of the blending surface are also available. In addition, the base surfaces are not restricted to any particular type of surface representation as long as they are parametrically defined and have a well-defined and continuous normal vector at each point. The scheme is extensible to higher orders of geometric continuity, although we concentrate on
G
1
.
A round trip to B-splines via de Casteljau
Authors: Prautzsch Hartmut
Published: July 2002

B-splines are constructed from Bézier curves solely using de Casteljau's construction. Divided differences are not being used, nor is Mansfield's recurrence formula presupposed. Yet, it is shown how to differentiate, subdivide, and evaluate a B-spline. These results are derived from the corresponding techniques of Bézier curves.
A set of level 3 basic linear algebra subprograms
Authors: Dongarra J. J. , Du Croz Jeremy , Hammarling Sven , Duff I. S.
Published: July 2002

This paper describes an extension to the set of Basic Linear Algebra Subprograms. The extensions are targeted at matrix-vector operations that should provide for efficient and portable implementations of algorithms for high-performance computers
Beyond the chalkboard: computer support for collaboration and problem solving in meetings
Authors: Stefik Mark , Foster Gregg , Bobrow Daniel G. , Kahn Kenneth , Lanning Stan , Suchman Lucy
Published: July 2002

Although individual use of computers is fairly widespread, in meetings we tend to leave them behind. At Xerox PARC, an experimental meeting room called the Colab has been created to study computer support of collaborative problem solving in face-to-face meetings. The long-term goal is to understand how to build computer tools to make meetings more effective.
Agenda: a personal information manager
Authors: Kaplan S. Jerrold , Kapor Mitchell D. , Belove Edward J. , Landsman Richard A. , Drake Todd R.
Published: July 2002

The free-form, evolving, personal information that people deal with in the course of their daily activities requires more flexible data structures and data management systems than tabular data structures provide. A tool for managing personal information must conveniently handle freetextual data; allow for structure to evolve gracefully as the database grows; represent unnormalized data; and support data entry through database
views
. We have designed a new type of database that serves these needs—“item/category” database—and realized this design in a commercial personal computer software product named “Agenda.”
Multiple-access protocols and time-constrained communication
Authors: Kurose James F. , Schwartz Mischa , Yemini Yechiam
Published: July 2002

During the past ten years, the field of multiple-access
communication has developed into a major area of both practical and
theoretical interest within the field of computer communications.
The multiple-access problem arises from the necessity of sharing a
single communication channel among a community of distributed
users. The distributed algorithm used by the stations to share the
channel is known as the multiple-access protocol. In this paper we
examine the multiple-access problem and various approaches to its
resolution.

In this survey we first define the multiple-access problem and
then present the underlying issues and difficulties in achieving
multiple-access communication. A taxonomy for multiple-access
protocols is then developed in order to characterize common
approaches and to provide a framework within which these protocols
can be compared and contrasted. Different proposed protocols are
then described and discussed, and aspects of their performance are
examined. The use of multiple-access protocols for "real- time" or
"time-constrained" communication applications, such as voice
transmission, is examined next. Issues in time-constrained
communication are identified, and recent work in the design of
time-constrained multiple-access protocols is surveyed.
Necessary and sufficient conditions to linearize doubly recursive programs in logic databases
Authors: Zhang Weining , Yu Clement T. , Troy Daniel
Published: July 2002

Linearization of nonlinear recursive programs is an important issue in logic databases for both practical and theoretical reasons. If a nonlinear recursive program can be transformed into an equivalent linear recursive program, then it may be computed more efficiently than when the tranformation is not possible. We provide a set of necessary and sufficient conditions for a simple doubly recursive program to be equivalent to a simple linear recursive program. The necessary and sufficient conditions can be verified effectively.
MOLECULAR-GENETIC ANALYSIS OF PLANT CYTOCHROME P450-DEPENDENT MONOOXYGENASES
Authors: Chapple Clint
Published: July 2002

▪ Abstract  Cytochrome P450-dependent monooxygenases are a large group of heme-containing enzymes, most of which catalyze NADPH- and O2-dependent hydroxylation reactions. The cloning of plant P450s has been hampered because these membrane-localized proteins are typically present in low abundance and are often unstable to purification. Since the cloning of the first plant P450 gene in 1990, there has been an explosion in the rate at which genes encoding plant P450s have been identified. These successes have largely been the result of advances in purification techniques, as well as the application of alternative methods such as mutant- and PCR-based cloning strategies. The availability of these cloned genes has made possible the analysis of P450 gene regulation and may soon reveal aspects of the evolution of P450s in plants. This new knowledge will significantly improve our understanding of many metabolic pathways and may permit their manipulation in the near future.
ASYMMETRIC CELL DIVISION IN PLANTS
Authors: Scheres Ben , Benfey Philip N.
Published: July 2002

▪ Abstract  Asymmetric cell divisions generate cells with different fates. In plants, where cells do not move relative to another cell, the specification and orientation of these divisions is an important mechanism to generate the overall cellular pattern during development. This review summarizes our knowledge of selected cases of asymmetric cell division in plants, in the context of recent insights into mechanisms underlying this process in bacteria, algae, yeast, and animals.
HIV-1: Fifteen Proteins and an RNA
Authors: Frankel Alan D. , Young John A. T.
Published: July 2002

Human immunodeficiency virus type 1 is a complex retrovirus encoding 15 distinct proteins. Substantial progress has been made toward understanding the function of each protein, and three-dimensional structures of many components, including portions of the RNA genome, have been determined. This review describes the function of each component in the context of the viral life cycle: the Gag and Env structural proteins MA (matrix), CA (capsid), NC (nucleocapsid), p6, SU (surface), and TM (transmembrane); the Pol enzymes PR (protease), RT (reverse transcriptase), and IN (integrase); the gene regulatory proteins Tat and Rev; and the accessory proteins Nef, Vif, Vpr, and Vpu. The review highlights recent biochemical and structural studies that help clarify the mechanisms of viral assembly, infection, and replication.
HOW CELLS RESPOND TO INTERFERONS
Authors: Stark George R. , Kerr Ian M. , Williams Bryan R. G. , Silverman Robert H. , Schreiber Robert D.
Published: July 2002

Interferons play key roles in mediating antiviral and antigrowth responses and in modulating immune response. The main signaling pathways are rapid and direct. They involve tyrosine phosphorylation and activation of signal transducers and activators of transcription factors by Janus tyrosine kinases at the cell membrane, followed by release of signal transducers and activators of transcription and their migration to the nucleus, where they induce the expression of the many gene products that determine the responses. Ancillary pathways are also activated by the interferons, but their effects on cell physiology are less clear. The Janus kinases and signal transducers and activators of transcription, and many of the interferon-induced proteins, play important alternative roles in cells, raising interesting questions as to how the responses to the interferons intersect with more general aspects of cellular physiology and how the specificity of cytokine responses is maintained.
Photosystem II: The Solid Structural Era
Authors: Rhee Kyong-Hi
Published: July 2002

▪ Abstract  Understanding the precise role of photosystem II as an element of oxygenic photosynthesis requires knowledge of the molecular structure of this membrane protein complex. The past few years have been particularly exciting because the structural era of the plant photosystem II has begun. Although the atomic structure has yet to be determined, the map obtained at 6 Å resolution by electron crystallography allows assignment of the key reaction center subunits with their associated pigment molecules. In the following, we first review the structural details that have recently emerged and then discuss the primary and secondary photochemical reaction pathways. Finally, in an attempt to establish the evolutionary link between the oxygenic and the anoxygenic photosynthesis, a framework structure common to all photosynthetic reaction centers has been defined, and the implications have been described.