bluuebunny/crossref_metadata_2025 huggingface dataset:
A computer generated aid for cluster analysis
Authors: Ling Robert L.
Published: July 2002

A computer generated graphic method, which can be used in conjunction with any hierarchical scheme of cluster analysis, is described and illustrated. The graphic principle used is the representation of the elements of a data matrix of similarities or dissimilarities by computer printed symbols (of character overstrikes) of various shades of darkness, where a dark symbol corresponds to a small dissimilarity. The plots, applied to a data matrix before clustering and to the rearranged matrix after clustering, show at a glance whether clustering brought forth any distinctive clusters. A well-known set of data consisting of the correlations of 24 psychological tests is used to illustrate the comparison of groupings by four methods of factor analysis and two methods of cluster analysis.
Empirical working set behavior
Authors: Rodriguez-Rosell Juan
Published: July 2002

The working set model for program behavior has been proposed in recent years as a basis for the design of scheduling and paging algorithms. Although the words “working set” are now commonly encountered in the literature dealing with resource allocation, there is a dearth of published data on program working set behavior. It is the purpose of this paper to present empirical data from actual program measurements, in the hope that workers in the field might find experimental evidence upon which to substantiate and base theoretical work.
Computer science
Authors: Amarel Saul
Published: July 2002

Two views of computer science are considered: a global view which attempts to capture broad characteristics of the field and its relationships to other fields, and a local view which focuses on the inner structure of the field. This structure is presented in terms of the kinds of knowledge, problems, and activities that exist within the discipline, as well as the relations between them. An approach to curriculum planning in computer science is presented which is guided by the structure of the field, by the fact that change is an important feature of the situation, and by the expectation that computer science will continue to increase its working contacts with other disciplines.
ACM 71
Authors: Carlson Walter M.
Published: July 2002

This is being written on the day after the close of ACM 71 as I return to Europe for continuation of an interrupted vacation. Therefore, these remarks are going to be short, and they will not, of course, do justice to the results obtained from our annual meeting in Chicago.
Information science in a Ph.D. computer science program
Authors: Salton G.
Published: July 2002

This report contains recommendations on a sample course curriculum in the general area of information organization and information system design in a Ph.D. Computer Science Program. The subject area is first briefly described, followed by a listing of some desirable graduate-level courses. Suitable bibliographies are appended.
WATFOR—The University of Waterloo FORTRAN IV compiler
Authors: Shantz Peter W. , German R. A. , Mitchell J. G. , Shirley R. S. K. , Zarnke C. R.
Published: July 2002

WATFOR is an in-core, load-and-go compiler which has been implemented within the IBM 7040/44 operating system. FORTRAN IV was selected as the source language in order to achieve maximum language compatibility with other available compiling systems, in particular the IBM 7040/44 FORTRAN IV system. The principal advantage of the WATFOR compiler is that it translates FORTRAN IV programs at speeds of up to 100 statements per second. Since the compiler resides in core there is virtually no systems overhead, and hence large batches of “student” programs may be processed very efficiently. The compiler also provides extensive error diagnostics, during both the compilation and the execution phases of a program run. This feature makes the system attractive to both learners and learned users alike.
Polynomial and spline approximation by quadratic programming
Authors: Amos D. E. , Slater M. L.
Published: July 2002

The problem of approximation to a given function, or of fitting a given set of data, where the approximating function is required to have certain of its derivatives of specified sign over the whole range of approximation, is studied. Two approaches are presented, in each of which quadratic programming is used to provide both the constraints on the derivatives and the selection of the function which yields the best fit. The first is a modified Berstein polynomial scheme, and the second is a spline fit.
On the automatic simplification of source-language programs
Authors: Clark Ellen R.
Published: July 2002

Methods of simplification that can be applied automatically to programs written in an ALGOL-like language are discussed. The simplifications are based on the form of the program and the knowledge obtained by a processor, without any understanding of what the program is supposed to do. These methods have been implemented in a processor called SURE that accepts a program written in JOVIAL and outputs an equivalent JOVIAL program that may be shorter and may be executed faster than the original.

SURE is described, some of the problems encountered in automatic improvement at the source-language level are discussed, and further types of automatic program improvement are suggested.
Performance monitoring in a time-sharing system
Authors: Pinkerton Tad B.
Published: July 2002

A software measurement facility which is part of a general purpose time-sharing system is described. The Data Collection Facility (DCF) has been implemented in the Michigan Terminal System (MTS) for the System/360 model 67. It exists for the purpose of monitoring operating system and user program behavior and performance. The overall structure of MTS is outlined in order to explain the implementation of the DCF. Events in the system are identified and recorded from within the supervisor, and dumped to magnetic tape by an auxiliary program for off-line processing. Events in user programs which are unrelated to system actions are recorded with a supervisor call. The time of occurrence of each event is accurately recorded, and data items are further identified by job and type. The overhead associated with data collection and its interference with normal jobs is carefully analyzed, and both are shown to be minimal. Several examples are given of information obtained with the facility and of applications in which it has been useful. Some general guidelines are offered for the construction of future monitoring programs.
A note on the efficiency of a LISP computation in a paged machine
Authors: Bobrow Daniel G. , Murphy Daniel L.
Published: July 2002

The problem of the use of two levels of storage for programs is explored in the context of a LISP system which uses core memory as a buffer for a large virtual memory stored on a drum. Details of timing are given for one particular problem.
Programming Techniques: An algorithm for the probability of the union of a large number of events
Authors: Miller G. D.
Published: July 2002

An algorithm is presented which efficiently evaluates the probability for the union of
n
independent and not mutually exclusive events. The problem is that of evaluating the sums of the products of all possible combinations of
n
variables in minimum time and storage space.
Microprogramming, emulators and programming languages
Authors: Green Julien
Published: July 2002

The problem we have been concerned with is that of converting language to action—or intellectual energy to mechanical energy. The medium that we use for this purpose is language and therefore we are preoccupied with the subject of language. In the areas of language investigation we have concentrated first on formalizing syntax and then on semantics. I believe semantics has received an unfair share of the energy of too many people—mainly misdirected to trying to reduce semantics to an algebraic manipulation of symbols, without enough attention to reality. By reality I mean the devices or mechanisms which are going to use these symbols. We have been overly concerned with what the symbols mean to one class of users, namely, the human or the senders of the symbols, without sufficient concern about the receivers of the symbols, in this case the machines.
A machine program for theorem-proving
Authors: Davis Martin , Logemann George , Loveland Donald
Published: July 2002

The programming of a proof procedure is discussed in connection with trial runs and possible improvements.
Inadequacy of computable loop invariants
Authors: Blass Andreas , Gurevich Yuri
Published: July 2002

Hoare logic is a widely recommended verification tool. There is, however, a problem of finding easily checkable loop invariants; it is known that decidable assertions do not suffice to verify while programs, even when the pre- and postconditions are decidable. We show here a stronger result: decidable invariants do not suffice to verify single-loop programs. We also show that this problem arises even in extremely simple contexts. Let
N
be the structure consisting of the set of natural numbers together with the functions
S(x)
=
x
+1,
D(x)
=2
(x)
=***
x
/2***. There is a single-loop program *** using only three variables
x,y,z
such that the asserted program
x
=
y
=
z
=0 *** false is partially correct on
N
but any loop invariant
I(x,y,z)
for this asserted program is undecidable.
Height-balanced trees of order (β, γ, δ)
Authors: Huang Shou-Hsuan S.
Published: July 2002

We study restricted classes of B-trees, called H(β, γ, δ) trees. A class is defined by three parameters: β, the size of a node; γ, the minimal number of grandsons a node must have; and δ, the minimal number of leaves bottom nodes must have. This generalizes the brother condition of 2-3 brother trees in a uniform way to B-trees of higher order. The class of B-trees of order m is obtained by choosing β = m, γ = (m/2)
2
and δ = m/2. An algorithm to construct H-trees for any given number of keys is given in Section 1. Insertion and deletion algorithms are given in Section 2. The costs of these algorithms increase smoothly as the parameters are increased. Furthermore, it is proved that the insertion can be done in time O(β + log N), where N is the number of nodes in the tree. Deletion can also be accomplished without reconstructing the entire tree. Properties of H-trees are given in Section 3. It is shown that the height of H-trees decreases as γ increases, and the storage utilization increases significantly as δ increases. Finally, comparisons with other restricted classes of B-trees are given in Section 4 to show the attractiveness of H-trees.
A pragmatic view of the system architect
Authors: Mills John A.
Published: July 2002

A whole-system designer, fire fighter, mediator, and jack-of-all-trades, the system architect brings unity and continuity to a development project—offsetting the inevitable compartmentalization of modern modular designs.
Lower bounds for solving linear diophantine equations on random access machines
Authors: Meyer auf der Heide Friedhelm
Published: July 2002

The problem of recognizing the language

L
n

(

L
n, k

) of solvable Diophantine linear equations with
n
variables (and solutions from {O, … ,
k
}

n

) is considered. The languages ∪

nϵN

L
n

, ∪

nϵN

L
n, l

, the knapsack problem, are NP-complete. The Ω(
n
2
lower bound for

L
n

,1 on linear search algorithms due to Dobkin and Lipton is generalized to an Ω(
n
2
log(
k
+ 1)) lower bound for

L
n, k

. The method of Klein and Meyer auf der Heide is further improved to carry over the Ω(
n
2
) lower bound for
L
n,1
to random access machines (RAMS) in such a way that it holds for a large class of problems and for very small input sets. By this method, lower bounds that depend on the input size, as is necessary for

L
n

, are proved. Thereby, an Ω(
n
2
log(
k
+ 1)) lower bound is obtained for RAMS recognizing

L
n

or

L
n, k

, for inputs from {0, … , (
nk
)

0
(
n
2
)

}

n

.
An experimental multimedia mail system
Authors: Postel Jonathan B. , Finn Gregory G. , Katz Alan R. , Reynolds Joyce K.
Published: July 2002

A computer-based experimental multimedia mail system that allows the user to read, create, edit, send, and receive messages containing text, images, and voice is discussed.
Query processing in a multimedia document system
Authors: Bertino Elisa , Rabbiti Fausto , Gibbs Simon
Published: July 2002

Query processing in a multimedia document system is described. Multimedia documents are information objects containing formatted data, text, image, graphics, and voice. The query language is based on a conceptual document model that allows the users to formulate queries on both document content and structure. The architecture of the system is outlined, with focus on the storage organization in which both optical and magnetic devices can coexist. Query processing and the different strategies evaluated by our optimization algorithm are discussed.
Software for an implementation of Weeks' method for the inverse Laplace transform
Authors: Garbow B. S. , Giunta G. , Lyness J. N. , Murli A.
Published: July 2002

A software package based on a modification of the Weeks' method is presented for calculating function values
f
(
t
) of the inverse Laplace transform. This method requires transform values
F
(
z
) at arbitrary points in the complex plane, and is suitable when
f
(
t
) has continuous derivatives of all orders; it is especially attractive when
f
(
t
) is required at a number of different abscissas
t
.
Ensuring court admissibility of computer-generated records
Authors: King Roger , Stanley Carolyn
Published: July 2002

An informal methodology is described for optimizing the likelihood of computer-generated records being admissible in a U.S. court of law. This methodology is intended for individuals who are converting to automated office procedures, as well as for those whose businesses are already highly computerized. However, this paper does not purport to be a formal legal guide; rather, it is intended as an overview of this issue.
Locking performance in centralized databases
Authors: Tay Y. C. , Goodman Nathan , Suri R.
Published: July 2002

An analytic model is used to study the performance of dynamic locking. The analysis uses only the steady-state average values of the variables. The solution to the model is given by a cubic, which has exactly one valid root for the range of parametric values that is of interest. The model's predictions agree well with simulation results for transactions that require up to twenty locks. The model separates data contention from resource contention, thus facilitating an analysis of their separate effects and their interaction. It shows that systems with a particular form of nonuniform access, or with shared locks, are equivalent to systems with uniform access and only exclusive locks.

Blocking due to conflicts is found to impose an upper bound on transaction throughput; this fact leads to a rule of thumb on how much data contention should be permitted in a system. Throughput can exceed this bound if a transaction is restarted whenever it encounters a conflict, provided restart costs and resource contention are low. It can also be exceeded by making transactions predeclare their locks. Raising the multiprogramming level to increase throughput also raises the number of restarts per completion. Transactions should minimize their lock requests, because data contention is proportional to the square of the number of requests. The choice of how much data to lock at a time depends on which part of a general granularity curve the system sees.
The Code Red Worm
Authors: Berghel Hal
Published: July 2002

Malicious software knows no bounds.
Fast simulation of broadband telecommunications networks carrying long-range dependent bursty traffic
Authors: Gallardo José R. , Makrakis Dimitrios , Orozco-Barbosa Luis
Published: July 2002

A technique for the fast simulation of broadband communication systems is proposed, which is based on regenerative Importance Sampling techniques and on large-deviation results. Our algorithm is applicable to estimate the probability of rare events when modeling the offered traffic using Fractional Stable Noise (FSN) processes (including Fractional Gaussian Noise as a particular case), which have been recently proved to be able to capture both the long-range dependence and the burstiness of today's aggregate network traffic. An exact description of FSN processes is given, as well as an approximation that allows for the application of Importance Sampling techniques. The results obtained for a simple example are also included.
An exact solution to the minimum size test pattern problem
Authors: Flores Paulo F. , Neto Horácio C. , Marques-Silva João P.
Published: July 2002

This article addresses the problem of test pattern generation for single stuck-at faults in combinational circuits, under the additional constraint that the number of specified primary input assignments is minimized. This problem has different applications in testing, including the identification of "don't care" conditions to be used in the synthesis of Built-In Self-Test (BIST) logic. The proposed solution is based on an integer linear programming (ILP) formulation which builds on an existing Propositional Satisfiability (SAT) model for test pattern generation. The resulting ILP formulation is linear on the size of the original SAT model for test generation, which is linear on the size of the circuit. Nevertheless, the resulting ILP instances represent complex optimization problems, that require dedicated ILP algorithms. Preliminary results on benchmark circuits validate the practical applicability of the test pattern minimization model and associated ILP algorithm.
Steerable illumination textures
Authors: Ashikhmin Michael , Shirley Peter
Published: July 2002

We introduce a new set of illumination basis functions designed for lighting bumpy surfaces. This lighting includes shadowing and interreflection. To create an image with a new light direction, only a linear combination of precomputed textures is required. This is possible by using a carefully selected set of steerable basis functions. Steerable basis lights have the property that they allow lights to move continuously without jarring visual artifacts. The new basis lights are shown to produce images of high visual quality with as few as 49 basis textures.
Washington State University
Authors: Brown Abbie
Published: July 2002

Washington State University
is in Pullman, on the state's eastern border. It is Washington's land grant (state-operated) university, conducting basic and applied research and providing public service statewide. The university consists of 10 colleges and a graduate school. The Department of Teaching and Learning works primarily with preservice and in-service educators and emergent instructional designers. The program emphasizes the development of instructional media that often includes the design and production of digital instructional media. The Wazzu Widgets project is a project designed for students of instructional media production who have advanced digital production capabilities.
A formal design notation for real-time systems
Authors: Felder Miguel , Pezzè Mauro
Published: July 2002

The development of real-time systems is based on a variety of different methods and notations. Despite the purported benefits of formal methods, informal techniques still play a predominant role in current industrial practice. Formal and informal methods have been combined in various ways to smoothly introduce formal methods in industrial practice. The combination of
real-time structured analysis
(SA-RT) with
Petri nets
is among the most popular approaches, but has been applied only to requirements specifications. This paper extends SA-RT to specifications of the detailed design of embedded real-time systems, and combines the proposed notation with Petri nets.
A functional approach to integrating database and expert systems
Authors: Risch Tore , Reboh René , Hart Peter E. , Duda Richard O.
Published: July 2002

A new system architecture shares certain characteristics with database systems, expert systems, functional programming languages, and spreadsheet systems, but is very different from any of these.
Equality-based binary resolution
Authors: Digricoli Vincent J. , Harrison Malcolm C.
Published: July 2002

A major event in automated reasoning was the introduction by Robinson of resolution as an inference principle that is complete for the first-order predicate calculus. Here the theory of binary resolution, based strictly on unification, is recast to incorporate the axioms of equality. Equality-based binary resolution is complete without making use of paramodulation and leads to refutations that are less than half as long as standard refutations with the equality axioms. A detailed discussion is given of the first major use of a theorem prover based on this new method.
A unified framework for race analysis of asynchronous networks
Authors: Brzozowski J. A. , Seger C.-J.
Published: July 2002

A unified framework is developed for the study of asynchronous circuits of both gate and MOS type. A basic network model consisting of a directed graph and a set of vertex excitation functions is introduced. A race analysis model, using three values (0, 1, and x), is developed for studying state transitions in the network. It is shown that the results obtained using this model are equivalent to those using ternary simulation. It is also proved that the set of state variables can be reduced to a minimum size set of feedback variables, and the analysis still yields both the correct state transitions and output hazard information. Finally, it is shown how the general results above are applicable to both gate and MOS circuits.
Impact of the technological environment on programmer/analyst job outcomes
Authors: Baroudi Jack J. , Ginzberg Michael J.
Published: July 2002

Recent research has shown that key DP/IS personnel job outcomes (e.g., turnover, organizational commitment, job satisfaction) are affected by job design, leadership characteristics, and role variables. This study investigates another class of variables, the technological environment faced by DP/IS personnel, that might impact these job outcomes. The technological environment includes (1) development methodologies employed, (2) project teams and reporting relationships, and (3) work characteristics. Variables from all classes were found to impact DP/IS job outcomes. Over 11 percent of the variance in DP/IS job satisfaction is explained by these variables.
The 1988 snowbird report: a discipline matures
Authors: Gries David , Walker Terry M. , Young Paul
Published: July 2002

With the severe crisis in computing behind us, the field is beginning to shed its preoccupation with its internal affairs. The representation of computing research to the public and to policy makers, was a major issue at Snowbird 88. Since no single entity fills this role, the Computing Research Board plans to fill it.
Graphics and managerial decision making: research-based guidelines
Authors: Jarvenpaa S. L. , Dickson G. W.
Published: July 2002

Graphical charts are generally thought to be a superior reporting technique compared to more traditional tabular representations in organizational decision making. The experimental literature, however, demonstrates only partial support for this hypothesis. To identify the characteristics of the situations that have been shown to benefit from the use of graphics, existing studies are reviewed in terms of the type of task used, the format employed, and the user experience. The examination of the literature reveals a set of empirically based—though preliminary—guidelines as to when and how to use business graphics.
An adaptive dependency source model for data compression
Authors: Abrahamson David M.
Published: July 2002

By dynamically recoding data on the basis of current intercharacter probabilities, the entropy of encoded messages can be significantly reduced.
Caching and other disk access avoidance techniques on personal computers
Authors: Jalics P. J. , McIntyre D. R.
Published: July 2002

CPU processing speed is rapidly increasing on PCs, resulting in a widening gap between disk access and CPU speed. The performance of three common disk caching systems are examined in an effort to determine a technique for reducing the gap.
The vulnerability of vote assignments
Authors: Barbara Daniel , Garcia-Molina Hector
Published: July 2002

In a faulty distributed system, voting is commonly used to achieve mutual exclusion among groups of nodes. Each node is assigned a number of votes, and any group with a majority of votes can perform the critical operations. Vote assignments can have a significant impact on system reliability, and in this paper we study the vote assignment problem. To compare vote assignments we define two deterministic measures, node and edge vulnerability. We present various properties of these measures and discuss how they can be computed. For these measures we discuss the selection of the best assignment and propose heuristics to identify good candidate assignments.
Why Ada is not just another programming language
Authors: Sammet Jean E.
Published: July 2002

Ada's importance goes far beyond its initial limited goals. The worldwide interest in the usage of Ada is one of many reasons for its uniqueness.
A trade-off between space and efficiency for routing tables
Authors: Peleg David , Upfal Eli
Published: July 2002

Two conflicting goals play a crucial role in the design of routing schemes for communication networks. A routing scheme should use paths that are as short as possible for routing messages in the network, while keeping the routing information stored in the processors' local memory as succinct as possible. The efficiency of a routing scheme is measured in terms of its
stretch factor
-the maximum ratio between the length of a route computed by the scheme and that of a shortest path connecting the same pair of vertices.

Most previous work has concentrated on finding good routing schemes (with a small fixed stretch factor) for special classes of network topologies. In this paper the problem for general networks is studied, and the entire range of possible stretch factors is examined. The results exhibit a trade-off between the efficiency of a routing scheme and its space requirements. Almost tight upper and lower bounds for this trade-off are presented. Specifically, it is proved that any routing scheme for general
n
-vertex networks that achieves a stretch factor
k
≥ 1 must use a total of Ω(
n

1+1/(2
k
+4)

) bits of routing information in the networks. This lower bound is complemented by a family
K
(
k
) of
hierarchical
routing schemes (for every k ≥ l) for unit-cost general networks, which guarantee a stretch factor of
O
(
k
), require storing a total of
O
(
k
3
n
1+(1/h)
log
n
)- bits of routing information in the network, name the vertices with
O
(log
2
n
)-bit names and use
O
(log
n
)-bit headers.
Notable computer networks
Authors: Quarterman John S. , Hoskins Josiah C.
Published: July 2002

Computer networks are becoming more numerous and more diverse. Collectively, they constitute a worldwide metanetwork.
Control strategies for two-player games
Authors: Abramson Bruce
Published: July 2002

Computer games have been around for almost as long as computers. Most of these games, however, have been designed in a rather ad hoc manner because many of their basic components have never been adequately defined. In this paper some deficiencies in the standard model of computer games, the minimax model, are pointed out and the issues that a general theory must address are outlined. Most of the discussion is done in the context of control strategies, or sets of criteria for move selection. A survey of control strategies brings together results from two fields: implementations of real games and theoretical predictions derived on simplified game-trees. The interplay between these results suggests a series of open problems that have arisen during the course of both analytic experimentation and practical experience as the basis for a formal theory.
Index scans using a finite LRU buffer: a validated I/O model
Authors: Mackert Lothar F. , Lohman Guy M.
Published: July 2002

Indexes are commonly employed to retrieve a portion of a file or to retrieve its records in a particular order. An accurate performance model of indexes is essential to the design, analysis, and tuning of file management and database systems, and particularly to database query optimization. Many previous studies have addressed the problem of estimating the number of disk page fetches when randomly accessing
k
records out of
N
given records stored on
T
disk pages. This paper generalizes these results, relaxing two assumptions that usually do not hold in practice: unlimited buffer and unique records for each key value. Experiments show that the performance of an index scan is very sensitive to buffer size limitations and multiple records per key value. A model for these more practical situations is presented and a formula derived for estimating the performance of an index scan. We also give a closed-form approximation that is easy to compute. The theoretical results are validated using the
R
*
distributed relational database system. Although we use database terminology throughout the paper, the model is more generally applicable whenever random accesses are made using keys.
UIO: a uniform I/O system interface for distributed systems
Authors: Cheriton David R.
Published: July 2002

A uniform I/O interface allows programs to be written relatively independently of specific I/O services and yet work with a wide variety of the I/O services available in a distributed environment. Ideally, the interface provides this uniform access without excessive complexity in the interface or loss of performance. However, a uniform interface does not arise from careful design of individual system interfaces alone; it requires explicit definition.

In this paper, the UIO (uniform I/O) system interface that has been used for the past five years in the V distributed operating system is described, with the focus on the key design issues. This interface provides several extensions beyond the I/O interface of UNIX™, including support for record I/O, locking, atomic transactions, and replication, as well as attributes that indicate whether optional semantics and operations are available. Experience in using and implementing this interface with a variety of different I/O services is described, along with the performance of both local and network I/O. It is concluded that the UIO interface provides a uniform I/O system interface with significant functionality, wide applicability, and no significant performance penalty.
On the Church-Rosser property for the direct sum of term rewriting systems
Authors: Toyama Yoshihito
Published: July 2002

The direct sum of two term rewriting systems is the union of systems having disjoint sets of function symbols. It is shown that if two term rewriting systems both have the Chruch-Rosser property, then the direct sum of these systems also has this property.
C-TODOS: an automatic tool for office system conceptual design
Authors: Pernici B. , Barbic F. , Maiocchi R. , Fugini M. G. , Rames J. R. , Rolland C.
Published: July 2002

Designers of office information systems, which share various features with information systems and software development, need to carefully consider special issues such as document and communication flows, user roles, user interfaces, and available technology.

The ESPRIT Project, Automatic TOols for Designing Office Information Systems (TODOS), proposes an integrated environment for office design with tools for requirements collection and analysis, conceptual design, rapid prototyping, and architecture selection.

Conceptual design is a central phase of office system design: It provides correct and complete functional requirements from which the office prototype will be developed and the final architecture chosen. C-TODOS, the conceptual design support tool developed within TODOS, is presented in this paper. The purpose of C-TODOS is to give the designer tools for supporting conceptual modeling activities with the goal of obtaining correct, consistent, and good quality office-functional specifications.

This paper presents C-TODOS within the TODOS development environment and describes the basic features of the tool: the TODOS Conceptual Model, the Specification Database, and the Modeling, Query and Consistency Checking Modules. The use of C-TODOS, through illustration of the development of a test case, and possible future research are discussed.
Passes, sweeps, and visits in attribute grammars
Authors: Engelfriet Joost , Filé Gilberto
Published: July 2002

Theoretical results are presented on multi-pass (both left-to-right and alternating), multi-sweep, and multi-visit attribute grammars. For each of these, a pure type and a simple type are distinguished: The pure attribute grammars are defined by nondeterministic attribute evaluators, and the simple ones by the corresponding (usual) deterministic evaluators. The time complexity of deciding membership in these classes of attribute grammars is studied. In general, this is harder for the pure classes than for the simple ones, for which it is either polynomial or NP-complete. The expressive power of the eight classes is compared by studying the translations they can compute. It is shown that sweeps are more powerful than passes, and visits are more powerful than sweeps.
Integrity = validity + completeness
Authors: Motro Amihai
Published: July 2002

Database integrity has two complementary components:
validity
, which guarantees that all false information is excluded from the database, and
completeness
, which guarantees that all true information is included in the database. This article describes a uniform model of integrity for relational databases, that considers both validity and completeness. To a large degree, this model subsumes the prevailing model of integrity (i.e., integrity constraints). One of the features of the new model is the determination of the integrity of answers issued by the database system in response to user queries. To users, answers that are accompanied with such detailed certifications of their integrity are more meaningful. First, the model is defined and discussed. Then, a specific mechanism is described that implements this model. With this mechanism, the determination of the integrity of an answer is a process analogous to the determination of the answer itself.
A very fast substring search algorithm
Authors: Sunday Daniel M.
Published: July 2002

This article describes a substring search algorithm that is faster than the Boyer-Moore algorithm. This algorithm does not depend on scanning the pattern string in any particular order. Three variations of the algorithm are given that use three different pattern scan orders. These include: (1) a “Quick Search” algorithm; (2) a “Maximal Shift” and (3) an “Optimal Mismatch” algorithm.
An object-oriented relational database
Authors: Premerlani William J. , Rumbaugh James E. , Blaha Michael R. , Varwig Thomas A.
Published: July 2002

A relational DBMS and an object-oriented programming language can be combined to yield a surprisingly effective OO-DBMS for many applications.
BASIC MECHANISMS OF TRANSCRIPT ELONGATION AND ITS REGULATION
Authors: Uptain S. M. , Kane C. M. , Chamberlin M. J.
Published: July 2002

Ternary complexes of DNA-dependent RNA polymerase with its DNA template and nascent transcript are central intermediates in transcription. In recent years, several unusual biochemical reactions have been discovered that affect the progression of RNA polymerase in ternary complexes through various transcription units. These reactions can be signaled intrinsically, by nucleic acid sequences and the RNA polymerase, or extrinsically, by protein or other regulatory factors. These factors can affect any of these processes, including promoter proximal and promoter distal pausing in both prokaryotes and eukaryotes, and therefore play a central role in regulation of gene expression. In eukaryotic systems, at least two of these factors appear to be related to cellular transformation and human cancers. New models for the structure of ternary complexes, and for the mechanism by which they move along DNA, provide plausible explanations for novel biochemical reactions that have been observed. These models predict that RNA polymerase moves along DNA without the constant possibility of dissociation and consequent termination. A further prediction of these models is that the polymerase can move in a discontinuous or inchworm-like manner. Many direct predictions of these models have been confirmed. However, one feature of RNA chain elongation not predicted by the model is that the DNA sequence can determine whether the enzyme moves discontinuously or monotonically. In at least two cases, the encounter between the RNA polymerase and a DNA block to elongation appears to specifically induce a discontinuous mode of synthesis. These findings provide important new insights into the RNA chain elongation process and offer the prospect of understanding many significant biological regulatory systems at the molecular level.
Mutagenesis of Glycosidases
Authors: Ly Hoa D. , Withers Stephen G.
Published: July 2002

▪ Abstract  Enzymatic hydrolysis of glycosides can occur by one of two elementary mechanisms identified by the stereochemical outcome of the reaction, inversion or retention. The key active-site residues involved are a pair of carboxylic acids in each case, and strategies for their identification and for probing the details of their roles in catalysis have been developed through detailed kinetic analysis of mutants. Similarly the roles of other active-site residues have also been probed this way, and mutants have been developed that trap intermediates in catalysis, allowing the determination of the three-dimensional structures of several such key species. By manipulating the locations or even the presence of these carboxyl side chains in the active site, the mechanisms of several glycosidases have been completely changed, and this has allowed the development of “glycosynthases,” mutant glycosidases that are capable of synthesizing oligosaccharides but unable to degrade them. Surprisingly little progress has been made on altering specificities through mutagenesis, although recent results suggest that gene shuffling coupled with effective screens will provide the most effective approach.
Coupling of Open Reading Frames by Translational Bypassing
Authors: Herr Alan J. , Atkins John F. , Gesteland Raymond F.
Published: July 2002

▪ Abstract  Translational bypassing joins the information found within two disparate open reading frames into a single polypeptide chain. The underlying mechanism centers on the decoding properties of peptidyl-transfer RNA (tRNA) and involves three stages: take-off, scanning, and landing. In take-off, the peptidyl-tRNA/messenger RNA (mRNA) complex in the P site of the ribosome dissociates, and the mRNA begins to move through the ribosome. In scanning, the peptidyl-tRNA probes the mRNA sliding through the decoding center. In landing, the peptidyl-tRNA re-pairs with a codon with which it can form a stable interaction. Although few examples of genes are known that rely on translational bypassing to couple open reading frames, ribosomes appear to have an innate capacity for bypassing. This suggests that the strategy of translational bypassing may be more common than presently appreciated. The best characterized example of this phenomenon is T4 gene 60, in which a complex set of signals stimulates bypassing of 50 nucleotides between the two open reading frames. In this review, we focus on the bypassing mechanism of gene 60 in terms of take-off, scanning, and landing.
A Structural View of Cre-loxP Site-Specific Recombination
Authors: Van Duyne Gregory D.
Published: July 2002

▪ Abstract  Structural models of site-specific recombinases from the lambda integrase family of enzymes have in the last four years provided an important new perspective on the three-dimensional nature of the recombination pathway. Members of this family, which include the bacteriophage P1 Cre recombinase, bacteriophage lambda integrase, the yeast Flp recombinase, and the bacterial XerCD recombinases, exchange strands between DNA substrates in a stepwise process. One pair of strands is exchanged to form a Holliday junction intermediate, and the second pair of strands is exchanged during resolution of the junction to products. Crystal structures of reaction intermediates in the Cre-loxP site-specific recombination system, together with recent biochemical studies in the field, support a “strand swapping” model for recombination that does not require branch migration of the Holliday junction intermediate in order to test homology between recombining sites.
Polarized Cell Growth in Higher Plants
Authors: Hepler Peter K. , Vidali Luis , Cheung Alice Y.
Published: July 2002

▪ Abstract  Pollen tubes and root hairs are highly elongated, cylindrically shaped cells whose polarized growth permits them to explore the environment for the benefit of the entire plant. Root hairs create an enormous surface area for the uptake of water and nutrients, whereas pollen tubes deliver the sperm cells to the ovule for fertilization. These cells grow exclusively at the apex and at prodigious rates (in excess of 200 nm/s for pollen tubes). Underlying this rapid growth are polarized ion gradients and fluxes, turnover of cytoskeletal elements (actin microfilaments), and exocytosis and endocytosis of membrane vesicles. Intracellular gradients of calcium and protons are spatially localized at the growing apex; inward fluxes of these ions are apically directed. These gradients and fluxes oscillate with the same frequency as the oscillations in growth rate but not with the same phase. Actin microfilaments, which together with myosin generate reverse fountain streaming, undergo rapid turnover in the apical domain, possibly being regulated by key actin-binding proteins, e.g., profilin, villin, and ADF/cofilin, in concert with the ion gradients. Exocytosis of vesicles at the apex, also dependent on the ion gradients, provides precursor material for the continuously expanding cell wall of the growing cell. Elucidation of the interactions and of the dynamics of these different components is providing unique insight into the mechanisms of polarized growth.
VOLCANISM AND TECTONICS ON VENUS
Authors: Nimmo F. , McKenzie D.
Published: July 2002

▪ Abstract  We review recent developments in the study of volcanism and tectonics on Venus. Venus's crust is basaltic, dry, and probably about 30 km thick. The mantle convects, giving rise to plumes, and has a similar composition and mean temperature (∼1300°C), but a higher viscosity (∼1020 Pa s), than that of the Earth. Inferred melt generation rates constrain the lithospheric thickness to between 80 and 200 km. The elastic thickness of the lithosphere is about 30 km on average. The present-day lack of plate tectonics may be due to strong faults and the high viscosity of the mantle. Most of the differences between Earth and Venus processes can be explained by the absence of water.

Venus underwent a global resurfacing event 300–600 Ma ago, the cause and nature of which remains uncertain. The present-day surface heat flux on Venus is about half the likely radiogenic heat generation rate, which suggests that Venus has been heating up since the resurfacing event.
PHYLOGENY OF TRICHOPTERA
Authors: Morse J. C.
Published: July 2002

▪ Abstract  The vitality of the phylogenetic dialogue in trichopterology, especially since 1967, is evidenced by the high quality and large number of published phylogenetic inferences concerning caddisflies and the continuing spirited exchange of opinions about some differences among those ideas. Monophyly for Trichoptera seems well argued. Monophyly for suborder Annulipalpia sensu stricto also is widely acknowledged, as is monophyly for suborder Integripalpia sensu stricto. Various postulated relationships of Hydrobiosidae, Rhyacophilidae, Glossosomatidae, and Hydroptilidae (= “Spicipalpia”) are less convincing. Phylogenies for several groups of families within Annulipalpia and Integripalpia have been proposed and relationships within at least 126 infrafamilial taxa also have been inferred.
Control and Biochemical Nature of the Ecdysteroidogenic Pathway
Authors: Gilbert Lawrence I. , Rybczynski Robert , Warren James T.
Published: July 2002

▪ Abstract  Molting is elicited by a critical titer of ecdysteroids that includes the principal molting hormone, 20-hydroxyecdysone (20E), and ecdysone (E), which is the precursor of 20E but also has morphogenetic roles of its own. The prothoracic glands are the predominate source of ecdysteroids, and the rate of synthesis of these polyhydroxylated sterols is critical for molting and metamorphosis. This review concerns three aspects of ecdysteroidogenesis: (a) how the brain neuropeptide prothoracicotropic hormone (PTTH) initiates a transductory cascade in cells of the prothoracic gland, which results in an increased rate of ecdysteroid biosynthesis (upregulation); (b) how the concentrations of 20E in the hemolymph feed back on the prothoracic gland to decrease rates of ecdysteroidogenesis (downregulation); and (c) how the prothoracic gland cells convert cholesterol to the precursor of E and then 20E, a series of reactions only now being understood because of the use of a combination of classical biochemistry and molecular genetics.
THE CYTOSKELETON AND DISEASE: Genetic Disorders of Intermediate Filaments
Authors: Fuchs Elaine
Published: July 2002

▪ Abstract  Specialized cytoskeletons play many fascinating roles, including mechanical integrity and wound-healing in epidermal cells, cell polarity in simple epithelia, contraction in muscle cells, hearing and balance in the inner ear cells, axonal transport in neurons, and neuromuscular junction formation between muscle cells and motor neurons. These varied functions are dependent upon cytoplasmic networks of actin microfilaments (6 nm), intermediate filaments (10 nm) and microtubules (23 nm), and their many associated proteins. In this chapter, I review what is known about the cytoskeletons of intermediate filaments and their associated proteins. I focus largely on epidermal cells, which devote most of their protein-synthesizing machinery to producing an extensive intermediate filament network composed of keratin. Recent studies have shown that many of the devastating human disorders that arise from degeneration of this cell type have as their underlying basis either defects in the genes encoding keratins or abnormalities in keratin IF networks. I discuss what we know about the functions of IFs, and how the link to genetic disease has enhanced this understanding.
ANTISENSE RNA-REGULATED PROGRAMMED CELL DEATH
Authors: Gerdes Kenn , Gultyaev Alexander P. , Franch Thomas , Pedersen Kim , Mikkelsen Nikolaj D.
Published: July 2002

▪ Abstract  Eubacterial plasmids and chromosomes encode multiple killer genes belonging to the hok gene family. The plasmid-encoded killer genes mediate plasmid stabilization by killing plasmid-free cells. This review describes the genetics, molecular biology, and evolution of the hok gene family. The complicated antisense RNA-regulated control-loop that regulates posttranscriptional and postsegregational activation of killer mRNA translation in plasmid-free cells is described in detail. Nucleotide covariations in the mRNAs reveal metastable stem-loop structures that are formed at the mRNA 5′ ends in the nascent transcripts. The metastable structures prevent translation and antisense RNA binding during transcription. Coupled nucleotide covariations provide evidence for a phylogenetically conserved mRNA folding pathway that involves sequential dynamic RNA rearrangements. Our analyses have elucidated an intricate mechanism by which translation of an antisense RNA-regulated mRNA can be conditionally activated. The complex phylogenetic relationships of the plasmid- and chromosome-encoded systems are also presented and discussed.