bluuebunny/crossref_metadata_2025 huggingface dataset:
Boundary Value Techniques for the Numerical Solution of Certain Initial Value Problems in Ordinary Differential Equations
Authors: Usmani Riaz A.
Published: July 2002

Linear initial value problems, particularly involving first order differential equations, can be transformed into systems of higher order and treated as boundary value problems. The type of difference equations used to replace the associated second order boundary value problem are

y
n

- 2
y

n
+1

+
y

n
+2

=
h
2
∑

β
i
y″

n
+
i

+
h
3
; ∑

δ
i

y
‴

n
+
i

+ · · ·,
n
= 1, 2, · · ·,
N
- 1 and -

y
N

+
y

N
+1

=
h
(
b
0
y′

N

+
b
1
y′

N
+1

) +
h
2
;(
c
0
y″

N

+
c
1
y″

N
+1

) + · · ·.

Numerical techniques referred to as
M
1,
M
2, and
M
3 have been developed in which error is
O
(
h
4
),
O
(
h
6
) and
O
(
h
8
), respectively. Experimental results have been given to demonstrate the usefulness of method
M
3 over
M
1 or
M
2.
The Unsolvability of the Recognition of Linear Context-Free Languages
Authors: Greibach Sheila A.
Published: July 2002

The problem of whether a given context-free language is linear is shown to be recursively undecidable.
Stack automata and compiling
Authors: Ginsburg Seymour , Greibach Sheila A. , Harrison Michael A.
Published: July 2002

Compilation consists of two parts, recognition and translation. A mathematical model is presented which embodies salient features of many modern compiling techniques. The model, called the stack automaton, has the desirable feature of being deterministic in nature. This deterministic device is generalized to a nondeterministic device (nondeterministic stack automaton) and particular instances of this more general device are noted. Sets accepted by nondeterministic stack automata are recursive. Each set accepted by a deterministic linear bounded automaton is accepted by some nonerasing stack automaton. Each context-sensitive language is accepted by some (deterministic) stack automaton.
One-way stack automata
Authors: Ginsburg Seymour , Greibach Sheila A. , Harrison Michael A.
Published: July 2002

A number of operations which either preserve sets accepted by one-way stack automata or preserve sets accepted by deterministic one-way stack automata are presented. For example, sequential transduction preserves the former; set complementation, the latter. Several solvability questions are also considered.
MERCURY
Authors: Brown W. S. , Traub J. F.
Published: July 2002

MERCURY is a computer-aided system for the selective distribution of Bell Telephone Laboratories technical reports to employees. MERCURY is based on the idea that the job of distribution should be divided between the author and the reader with each performing that part of the job which he does best. The author is asked to describe the interests of the readers to whom his report should be sent. The reader is asked to described the reports that he wishes to receive. The descriptions are made from a small structured vocabulary. The matching of report to reader and the printing of address labels is done by computer.
Sufficient Conditions for the Success of GPS
Authors: Ernst George W.
Published: July 2002

A formal model of a problem is developed and its relationship to the General Problem Solver (GPS) is discussed. Before GPS can work on a problem it must be given differences, a difference-ordering, and a table of connections, in addition to the specifications of a problem. Formal definitions of this additional information are given, and sufficient conditions for the success of GPS are derived. These conditions point out the utility of differences and a difference-ordering that yield a “triangular” table of connections. Several different formulations of the Tower of Hanoi are given to illustrate the formal concepts. The use of subproblems in narrowing search is discussed.
Decidable Properties of Monadic Functional Schemas
Authors: Ashcroft Edward , Manna Zohar , Pnueli Amir
Published: July 2002

A class of (monadic) functional schemas which properly includes “Ianov” flowchart schemas is defined. It is shown that the termination, divergence, and freedom problems for functional schemas are decidable. Although it is possible to translate a large class of non-free functional schemas into equivalent free functional schemas, it is shown that in general this cannot be done. It is also shown that the equivalence problem for free functional schemas is decidable. Most of the results are obtained from well-known results in formal languages and automata theory.
Efficient passage ranking for document databases
Authors: Kaszkiel Marcin , Zobel Justin , Sacks-Davis Ron
Published: July 2002

Queries to text collections are resolved by ranking the documents in the collection and returning the highest-scoring documents to the user. An alternative retrieval method is to rank passages, that is, short fragments of documents, a strategy that can improve effectiveness and identify relevant material in documents that are too large for users to consider as a whole. However, ranking of passages can considerably increase retrieval costs. In this article we explore alternative query evaluation techniques, and develop new tecnhiques for evaluating queries on passages. We show experimentally that, appropriately implemented, effective passage retrieval is practical in limited memory on a desktop machine. Compared to passage ranking with adaptations of current document ranking algorithms, our new “DO-TOS” passage-ranking algorithm requires only a fraction of the resources, at the cost of a small loss of effectiveness.
An extension of conflict-free multivalued dependency sets
Authors: Katsuno Hirofumi
Published: July 2002

Several researchers (Beeri, Bernstein, Chiu, Fagin, Goodman, Maier, Mendelzon, Ullman, and Yannakakis) have introduced a special class of database schemes, called
acyclic
or
tree
schemes. Beeri et al. have shown that an acyclic join dependency, naturally defined by an acyclic database scheme, has several desirable properties, and that an acyclic join dependency is equivalent to a conflict-free set of multivalued dependencies. However, since their results are confined to multivalued and join dependencies, it is not clear whether we can handle functional dependencies independently of other dependencies.

In the present paper we define an extension of a conflict-free set, called an
extended conflict-free set
, including multivalued dependencies and functional dependencies, and show the following two properties of an extended conflict-free set:

There are three equivalent definitions of an extended conflict-free set. One of them is defined as a set including an acyclic joint dependency and a set of functional dependencies such that the left and right sides of each functional dependency are included in one of the attribute sets that construct the acyclic join dependency.

For a relation scheme with an extended conflict-free set, there is a decomposition into third normal form with a lossless join and preservation of dependencies.
Regression-based RTL power modeling
Authors: Bogliolo Alessandro , Benini Luca , De Micheli Giovanni
Published: July 2002

Register-transfer level (RTL) power estimation is a key feature for synthesis-based design flows. The main challenge in establishing a sound RTL power estimation methodology is the construction of accurate, yet efficient, models of the power dissipation of functional macros. Such models should be automatically built, and should produce reliable average power estimates. In this paper we propose a general methodology for building and tuning RTL power models. We address both hard macros (presynthesized functional blocks)and soft macros (functional units for which only a synthesizable HDL description is provided). We exploit linear regression and its nonparametric extensions to express the dependency of power dissipation on input and output activity. Bottom-up off-line characterization of regression-based power macromodels is discussed in detail. Moreover, we introduce a low overhead on-line characterization method for enhancing the accuracy of off-line characterization.
Soft updates
Authors: Ganger Gregory R. , McKusick Marshall Kirk , Soules Craig A. N. , Patt Yale N.
Published: July 2002

Metadata updates, such as file creation and block allocation, have consistently been identified as a source of performance, integrity, security, and availability problems for file systems.
Soft updates
is an implementation technique for low-cost sequencing of fine-grained updates to write-back cache blocks. Using soft updates to track and enforce metadata update dependencies, a file system can safely use delayed writes for almost all file operations. This article describes soft updates, their incorporation into the 4.4BSD fast file system, and the resulting effects on the sytem. We show that a disk-based file system using soft updates achieves memory-based file system performance while providing stronger integrity and security guarantees than most disk-based file systems. For workloads that frequently perform updates on metadata (such as creating and deleting files), this improves performance by more than a factor of two and up to a factor of 20 when compared to the conventional synchronous write approach and by 4-19% when compared to an aggressive write-ahead logging approach. In addition, soft updates can improve file system availablity by relegating crash-recovery assistance (e.g., the
fsck
utility) to an optional and background role, reducing file system recovery time to less than one second.
Multiple shooting method for two-point boundary value problems
Authors: Morrison David D. , Riley James D. , Zancanaro John F.
Published: July 2002

The common techniques for solving two-point boundary value problems can be classified as either "shooting" or "finite difference" methods. Central to a shooting method is the ability to integrate the differential equations as an initial value problem with guesses for the unknown initial values. This ability is not required with a finite difference method, for the unknowns are considered to be the values of the true solution at a number of interior mesh points. Each method has its advantages and disadvantages. One serious shortcoming of shooting becomes apparent when, as happens altogether too often, the differential equations are so unstable that they "blow up" before the initial value problem can be completely integrated. This can occur even in the face of extremely accurate guesses for the initial values. Hence, shooting seems to offer no hope for some problems. A finite difference method does have a chance for it tends to keep a firm hold on the entire solution at once. The purpose of this note is to point out a compromising procedure which endows shooting-type methods with this particular advantage of finite difference methods. For such problems, then, all hope need not be abandoned for shooting methods. This is desirable because shooting methods are generally faster than finite difference methods.

The organization is as follows:

I. The two-point boundary value problem is stated in quite general form.

II. A particular shooting method is described which is designed to solve the problem in this form.

III. The two-point boundary value problem is then restated in such a way that:

(a) the restatement still falls within the general form, and

(b) the shooting method now has a better chance of success when the equations are unstable.
Further comments on Dijkstra's concurrent programming control problem
Authors: Eisenberg Murray A. , McGuire Michael R.
Published: July 2002

E.W. Dijkstra [1] presented an algorithm whereby
N
mainly independent computers, with a common data store as their sole means of communication, could contend for exclusive control of any given resource (storage, I/O, etc.). To use the resource, a computer had to gain access to the “critical section” of the algorithm, within which one and only one computer at a time could be executing.
A generalized control structure and its formal definition
Authors: Parnas David Lorge
Published: July 2002

A new programming language control structure as well as an improved approach to a formal definition of programming languages are presented. The control structure can replace both iteration and conditional structures. Because it is a semantic generalization of those structures, a single statement using the new control structure can implement the functions of loops, conditionals, and also programs that would require several conventional constructs. As a consequence of this increased capability, it is possible to write algorithms that are simpler, more efficient, and more clearly correct than those that can be written with earlier structured-programming control structures. In order to provide a precise definition of the new constructs, a new version of relational semantics, called LD
-
relations is presented. An algebra of these relations is developed and used to define the meaning of the new constructs. A short discussion of program development and the history of control structures is included.
Controlling the complexity of menu networks
Authors: Brown James W.
Published: July 2002

A common approach to the design of user interfaces for computer systems is the menu selection technique. Each menu frame can be considered a node in an information/action network. The set of nodes and the permissible transitions between them (menu selections) form a directed graph which, in a system of substantial size, can be large and enormously complex. The solution to this problem of unmanageable complexity is the same for menu networks as for programs: the disciplined use of a set of well-defined one-in-one-out structures. This paper defines a set of such structures and offers some guidelines for their use.
An on-line algorithm for fitting straight lines between data ranges
Authors: O'Rourke Joseph
Published: July 2002

Applications often require fitting straight lines to data that is input incrementally. The case where a data range [

α
k

,

ω
k

] is received at each

t
k

,

t
1

<

t
2

< …

t
n

, is considered. An algorithm is presented that finds all the straight lines
u
=
mt
+
b
that pierce each data range, i.e., all pairs (
m, b
) such that

α
k

≤

mt
k

+
b
≤

ω
k

for
k
= 1, … ,
n
. It may be that no single line fits all the ranges, and different alternatives for handling this possibility are considered. The algorithm is on-line, producing the correct partial result after processing the first
k
ranges for all
k
<
n
. For each
k
, the set of (
m
,
b
) pairs constitutes a convex polygon in the
m
-
b
parameter space, which can be constructed as the intersection of 2
k
half-planes. It is shown that the
O
(
n
log
n
) half-plane intersection algorithm of Shamos and Hoey can be improved in this special case to
O
(
n
).
List processing in real time on a serial computer
Authors: Baker Henry G.
Published: July 2002

A real-time list processing system is one in which the time required by the elementary list operations (e.g. CONS, CAR, CDR, RPLACA, RPLACD, EQ, and ATOM in LISP) is bounded by a (small) constant. Classical implementations of list processing systems lack this property because allocating a list cell from the heap may cause a garbage collection, which process requires time proportional to the heap size to finish. A real-time list processing system is presented which continuously reclaims garbage, including directed cycles, while linearizing and compacting the accessible cells into contiguous locations to avoid fragmenting the free storage pool. The program is small and requires no time-sharing interrupts, making it suitable for microcode. Finally, the system requires the same average time, and not more than twice the space, of a classical implementation, and those space requirements can be reduced to approximately classical proportions by compact list representation. Arrays of different sizes, a program stack, and hash linking are simple extensions to our system, and reference counting is found to be inferior for many applications.
Performance of height-balanced trees
Authors: Karlton P. L. , Fuller S. H. , Scroggs R. E. , Kaehler E. B.
Published: July 2002

This paper presents the results of simulations that investigate the performance of height-balanced (HB[k]) trees. It is shown that the only statistic of HB[1] trees (AVL trees) that is a function of the size of the tree is the time to search for an item in the tree. For sufficiently large trees, the execution times of all procedures for maintaining HB[1] trees are independent of the size of the tree. In particular, an average of .465 restructures are required per insertion, with an average of 2.78 nodes revisited to restore the HB[1] property; an average of .214 restructures are required per deletion, with an average of 1.91 nodes revisited to restore the HB[1] property. Moreover, the execution times of procedures for maintaining HB[k] trees, for k > 1, are also independent of the size of the tree except for the average number of nodes revisited on a delete operation in order to restore the HB[k] property on traceback. The cost of maintaining HB[k] trees drops sharply as the allowable imbalance (k) increases. Both analytical and experimental results that show the cost of maintaining HB[k] trees as a function of k are discussed.
A comparative analysis of disk scheduling policies
Authors: Teorey Toby J. , Pinkerton Tad B.
Published: July 2002

Five well-known scheduling policies for movable head disks are compared using the performance criteria of expected seek time (system oriented) and expected waiting time (individual I/O request oriented). Both analytical and simulation results are obtained. The variance of waiting time is introduced as another meaningful measure of performance, showing possible discrimination against individual requests. Then the choice of a utility function to measure total performance including system oriented and individual request oriented measures is described. Such a function allows one to differentiate among the scheduling policies over a wide range of input loading conditions. The selection and implementation of a maximum performance two-policy algorithm are discussed.
Adaptive correction of program statements
Authors: James E. B. , Partridge D. P.
Published: July 2002

A method of analyzing statements in a programming language which can tolerate a considerable inaccuracy in their specification is proposed. This method involves principles at present mainly confined to studies in the area of artificial intelligence such as feature extraction, approximate tree matching, and strategy improvement by feedback from the matching process. A pilot program incorporating the principles is described and preliminary operating results are presented. A final section surveys further principles which are currently being investigated.
GEDANKEN—a simple typeless language based on the principle of completeness and the reference concept
Authors: Reynolds John C.
Published: July 2002

GEDANKEN is an experimental programming language with the following characteristics. (1) Any value which is permitted in some context of the language is permissible in any other meaningful context. In particular, functions and labels are permissible results of functions and values of variables. (2) Assignment and indirect addressing are formalized by introducing values, called references, which in turn possess other values. The assignment operation always affects the relation between some reference and its value. (3) All compound data structures are treated as functions. (4) Type declarations are not permitted.

The functional approach to data structures and the use of references insure that any process which accepts some data structure will accept any logically equivalent structure, regardless of its internal representation. More generally, any data structure may be implicit; i.e. it may be specified by giving an arbitrary algorithm for computing or accessing its components. The existence of label variables permits the construction of co-routines, quasi-parallel processes, and other unorthodox control mechanisms.

A variety of programming examples illustrates the generality of the language. Limitations and possible extensions are discussed briefly.
Hint-based cooperative caching
Authors: Sarkar Prasenjit , Hartman John H.
Published: July 2002

This article presents the design, implementation, and measurement of a hint-based cooperative caching file system. Hints allow clients to make decisions based on local state, enabling a loosely coordinated system that is simple to implement. The resulting performance is comparable to that of existing tightly coordinated algorithms that use global state, but with less overhead. Simulations show that the block access times of our system are as good as those of the existing algorithms, while reducing manager load by more than a factor of seven, block lookup traffic by nearly a factor of two-thirds, and replacement traffic a factor of five. To verify our simulation results in a real system with real users, we implemented a prototype and measured its performance for one week. Although the simulation and prototype environments were very different, the prototype system mirrored the simulation results by exhibiting reduced overhead and high hint accuracy. Furthermore, hint-based cooperative caching reduced the average block access time to almost half that of NFS.
The logarithmic error and Newton's method for the square root
Authors: King Richard F. , Phillips David L.
Published: July 2002

The problem of obtaining optimal starting values for the calculation of the square root using Newton's method is considered. It has been pointed out elsewhere that if relative error is used as the measure of goodness of fit, optimal results are not obtained when the inital approximation is a best fit. It is shown here that if, instead, the so-called logarithmic error is used, then a best initial fit is optimal for both types of error. Moreover, use of the logarithmic error appears to simplify the problem of determining the optimal initial approximation.
Images from computers and microfilm plotters
Authors: Schroeder M. R.
Published: July 2002

Digital computers are widely used for the processing of information and data of all kinds, including the pictorial information contained in photographs and other graphical representations. Efficient conversion facilities for putting graphical information into the computer and retrieving it in graphical form are therefore much needed. One of the most commonly employed devices for obtaining permanent graphical output from digital computers is the microfilm plotter. Regrettably, present models have no provision for producing images with a continuous gray scale or “halftones.” In this note several programming techniques are described for obtaining halftone pictures from a microfilm plotter under the control of a digital computer. Illustrative examples of several methods are given.
A framework for symmetric band reduction
Authors: Bischof Christian H. , Lang Bruno , Sun Xiaobai
Published: July 2002

We develop an algorithmic framework for reducing the bandwidth of symmetric matrices via orthogonal similarity transformations. This framework includes the reduction of full matrices to banded or tridiagonal form and the reduction of banded matrices to narrower banded or tridiagonal form, possibly in multiple steps. Our framework leads to algorithms that require fewer floating-point operations than do standard algorithms, if only the eigenvalues are required. In addition, it allows for space-time tradeoffs and enables or increases the use of blocked transformations.
Algorithm 807
Authors: Bischof Christian H. , Lang Bruno , Sun Xiaobai
Published: July 2002

We present a software toolbox for symmetric band reduction via orthogonal transformations, together with a testing and timing program. The toolbox contains drivers and computational routines for the reduction of full symmetric matrices to banded form and the reduction of banded matrices to narrower banded or tridiagonal form, with optional accumulation of the orthogonal transformations, as well as repacking routines for storage rearrangement. The functionality and the calling sequences of the routines are described, with a detailed discussion of the “control” parameters that allow adaptation of the codes to particular machine and matrix characteristics. We also briefly describe the testing and timing program included in the toolbox.
CONVERT
Authors: Guzmán Adolfo , McIntosh Harold V.
Published: July 2002

A programming language is described which is applicable to problems conveniently described by transformation rules. By this is meant that patterns may be prescribed, each being associated with a skeleton, so that a series of such pairs may be searched until a pattern is found which matches an expression to be transformed. The conditions for a match are governed by a code which also allows subexpressions to be identified and eventually substituted into the corresponding skeleton. The primitive patterns and primitive skeletons are described, as well as the principles which allow their elaboration into more complicated patterns and skeletons. The advantages of the language are that it allows one to apply transformation rules to lists and arrays as easily as strings, that both patterns and skeletons may be defined recursively, and that as a consequence programs may be stated quite concisely.
A mean value performance model for locking in databases
Authors: Tay Y. C. , Suri Rajan , Goodman Nathan
Published: July 2002

A new performance model for dynamic locking is proposed. It is based on a flow diagram and uses only the steady state average values of the variables. It is general enough to handle nonuniform access, shared locks, static locking, multiple transaction classes, and transactions of indeterminate length. The analysis is restricted to the case in which all conflicts are resolved by restarts. It has been shown elsewhere that, under certain conditions, this pure restart policy is as good as, if not better than, a policy that uses both blocking and restarts.

The analysis is straightforward, and the computational complexity of the solution, given some nonrestrictive approximations, does not depend on the input parameters. The solution is also well defined and well behaved. The model's predictions agree well with simulation results.

The model shows that data contention can cause the throughput to thrash, and gives a limit on the workload that will prevent this. It also shows that systems with a particular kind of nonuniform access and systems in which transactions share locks are equivalent to systems in which there is uniform access and only exclusive locking. Static locking has higher throughput, but longer response time, than dynamic locking. Replacing updates by queries in a multiprogramming mix may degrade performance if the queries are longer than the updates.
A fast parallel algorithm for the maximal independent set problem
Authors: Karp Richard M. , Wigderson Avi
Published: July 2002

A parallel algorithm is presented that accepts as input a graph
G
and produces a maximal independent set of vertices in
G
. On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in
O
((log
n
)
4
) time and uses
O
((
n
/(log
n
))
3
) processors, where
n
is the number of vertices in
G
. The algorithm has several novel features that may find other applications. These include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a “dynamic pigeonhole principle” that generalizes the conventional pigeonhole principle.
Computing with structured connectionist networks
Authors: Feldman Jerome A. , Fanty Mark A. , Goddard Nigel H. , Lynne Kenton J.
Published: July 2002

The design and applications of massively parallel computational models could lead to dramatic advances in the ability to automate complex tasks such as those found in artificial intelligence.
The role of frame-based representation in reasoning
Authors: Fikes Richard , Kehler Tom
Published: July 2002

A frame-based representation facility contributes to a knowledge system's ability to reason and can assist the system designer in determining strategies for controlling the system's reasoning.
A probability model for overflow sufficiency in small hash tables
Authors: Norton R. M. , Yeager D. P.
Published: July 2002

For hash tables in which a strict physical separation exists between primary storage and storage for overflow records, with bucket capacity at least three, a complete probability model is described. A measure of hash table efficiency is introduced, called the table sufficiency index (TSI), and defined as the probability that the overflow space is sufficient assuming that the set of hashed keys has a uniform distribution. The constructed probability model may be used to compute the TSI for hash tables with parameters chosen from a restricted domain. The TSI is advocated as a tool for making decisions about the parameters of small hash tables.
Performance effects of architectural complexity in the Intel 432
Authors: Colwell Robert P. , Gehringer Edward F. , Jensen E. Douglas
Published: July 2002

The Intel 432 is noteworthy as an architecture incorporating a large amount of functionality that most other systems perform by software. It has, in effect, “migrated” this functionality from the software into the microcode and hardware. The benefits of functional migration have recently been a subject of intense controversy, with critics claiming that a complex architecture is inherently less efficient than a simple architecture with good software support. This paper examines the performance impact of the incorporation of several kinds of functionality into the Intel 432. Among these are the addressing structure, the caches, instruction alignment, the buses, and the way that garbage collection is handled. A set of several benchmarks is used to quantify the performance effect of each of these decisions. The results indicate that the 432 could have been speeded up very significantly if a small number of implementation decisions had been made differently, and if incrementally better technology had been used in its construction. Even with these modifications, however, the 432 would still have only one-fourth to one times the speed of its contemporaries. These figures may represent the real cost of the 432's style of object-based programming environment.
FLAME
Authors: Gunnels John A. , Gustavson Fred G. , Henry Greg M. , van de Geijn Robert A.
Published: July 2002

Since the advent of high-performance distributed-memory parallel computing, the need for intelligible code has become ever greater. The development and maintenance of libraries for these architectures is simply too complex to be amenable to conventional approaches to implementation. Attempts to employ traditional methodology have led, in our opinion, to the production of an abundance of anfractuous code that is difficult to maintain and almost impossible to upgrade.Having struggled with these issues for more than a decade, we have concluded that a solution is to apply a technique from theoretical computer science, formal derivation, to the development of high-performance linear algebra libraries. We think the resulting approach results in aesthetically pleasing, coherent code that greatly facilitates intelligent modularity and high performance while enhancing confidence in its correctness. Since the technique is language-independent, it lends itself equally well to a wide spectrum of programming languages (and paradigms) ranging from C and Fortran to C++ and Java. In this paper, we illustrate our observations by looking at the Formal Linear Algebra Methods Environment (FLAME), a framework that facilitates the derivation and implementation of linear algebra algorithms on sequential architectures. This environment demonstrates that lessons learned in the distributed-memory world can guide us toward better approaches even in the sequential world.We present performance experiments on the Intel (R) Pentium (R) III processor that demonstrate that high performance can be attained by coding at a high level of abstraction.
Remus
Authors: Bernaschi Massimo , Gabrielli Emanuele , Mancini Luigi V.
Published: July 2002

We present a detailed analysis of the UNIX system calls and classify them according to their level of threat with respect to system penetration. Based on these results, an effective mechanism is proposed to control the invocation of critical, from the security viewpoint, system calls. The integration into existing UNIX operating systems is carried out by instrumenting the code of the system calls in such a way that the execution is granted only in the case where the invoking process and the value of the arguments comply with the rules held in an access control database. This method does not require changes in the kernel data structures and algorithms. All kernel modifications are transparent to the application processes that continue to work correctly with no need of source code changes or recompilation. A working prototype has been implemented as a loadable kernel module for the Linux operating system. The prototype is able to detect and block any attacks by which an intruder tries to gain direct access to the system as a privileged user.
A locally adaptive data compression scheme
Authors: Bentley Jon Louis , Sleator Daniel D. , Tarjan Robert E. , Wei Victor K.
Published: July 2002

A data compression scheme that exploits locality of reference, such as occurs when words are used frequently over short intervals and then fall into long periods of disuse, is described. The scheme is based on a simple heuristic for self-organizing sequential search and on variable-length encodings of integers. We prove that it never performs much worse than Huffman coding and can perform substantially better; experiments on real files show that its performance is usually quite close to that of Huffman coding. Our scheme has many implementation advantages: it is simple, allows fast encoding and decoding, and requires only one pass over the data to be compressed (static Huffman coding takes two passes).
An integrated approach to logical design of relational database schemes
Authors: Beeri Catriel , Kifer Michael
Published: July 2002

We propose a new approach to the design of relational database schemes. The main features of the approach are the following:

A combination of the traditional decomposition and synthesis approaches, thus allowing the use of both functional and multivalued dependencies.

Separation of structural dependencies relevant for the design process from integrity constraints, that is, constraints that do not bear any structural information about the data and which should therefore be discarded at the design stage. This separation is supported by a simple syntactic test filtering out nonstructural dependencies.

Automatic correction of schemes which lack certain desirable properties.
File organization using composite perfect hashing
Authors: Ramakrishna M. V. , Larson Per-Åke
Published: July 2002

Perfect hashing refers to hashing with no overflows. We propose and analyze a composite perfect hashing scheme for large external files. The scheme guarantees retrieval of any record in a single disk access. Insertions and deletions are simple, and the file size may vary considerably without adversely affecting the performance. A simple variant of the scheme supports efficient range searches in addition to being a completely dynamic file organization scheme. These advantages are achieved at the cost of a small amount of additional internal storage and increased cost of insertions.
Measurement and modeling of computer reliability as affected by system activity
Authors: Iyer R. K. , Rossetti D. J. , Hsueh M. C.
Published: July 2002

This paper demonstrates a practical approach to the study of the failure behavior of computer systems. Particular attention is devoted to the analysis of permanent failures. A number of important techniques, which may have general applicability in both failure and workload analysis, are brought together in this presentation. These include: smeared averaging of the workload data, clustering of like failures, and joint analysis of workload and failures. Approximately 17 percent of all failures affecting the CPU were estimated to be permanent. The manifestation of a permanent failure was found to be strongly correlated with the level and type of workload prior to the failure. Although, in strict terms, the results only relate to the manifestation of permanent failures and not to their occurrence, there are strong indications that permanent failures are both caused and discovered by increased activity. More measurements and experiments are necessary to determine their respective contributions to the measured workload/failure relationship.
A graphics interface for linear programming
Authors: Ma Pai-Chun , Murphy Frederic H. , Stohr Edward A.
Published: July 2002

We describe the interface to a software system that assists users in the process of formulating linear programming models. The main idea is to introduce a new representation that allows modelers to depict their problems in a graphical rather than mathematical form. This representation is described in detail together with a number of other interface design principles that we believe will aid modelers—including hierarchical decomposition, multiple model representations, alternative formulation approaches, the use of model templates, and database and model management facilities. These features are illustrated using the output of a prototype system formulating a realistic LP problem.
Explanation-based learning: a survey of programs and perspectives
Authors: Ellman Thomas
Published: July 2002

Explanation-based learning (EBL) is a technique by which an intelligent system can learn by observing examples. EBL systems are characterized by the ability to create justified generalizations from single training instances. They are also distinguished by their reliance on background knowledge of the domain under study. Although EBL is usually viewed as a method for performing generalization, it can be viewed in other ways as well. In particular, EBL can be seen as a method that performs four different learning tasks: generalization, chunking, operationalization, and analogy.

This paper provides a general introduction to the field of explanation-based learning. Considerable emphasis is placed on showing how EBL combines the four learning tasks mentioned above. The paper begins with a presentation of an intuitive example of the EBL technique. Subsequently EBL is placed in its historical context and the relation between EBL and other areas of machine learning is described. The major part of this paper is a survey of selected EBL programs, which have been chosen to show how EBL manifests each of the four learning tasks. Attempts to formalize the EBL technique are also briefly discussed. The paper concludes with a discussion of the limitations of EBL and the major open questions in the field.
How to write parallel programs: a guide to the perplexed
Authors: Carriero Nicholas , Gelernter David
Published: July 2002

We present a framework for parallel programming, based on three conceptual classes for understanding parallelism and three programming paradigms for implementing parallel programs. The conceptual classes are result parallelism, which centers on parallel computation of all elements in a data structure; agenda parallelism, which specifies an agenda of tasks for parallel execution; and specialist parallelism, in which specialist agents solve problems cooperatively. The programming paradigms center on live data structures that transform themselves into result data structures; distributed data structures that are accessible to many processes simultaneously; and message passing, in which all data objects are encapsulated within explicitly communicating processes. There is a rough correspondence between the conceptual classes and the programming methods, as we discuss. We begin by outlining the basic conceptual classes and programming paradigms, and by sketching an example solution under each of the three paradigms. The final section develops a simple example in greater detail, presenting and explaining code and discussing its performance on two commercial parallel computers, an 18-node shared-memory multiprocessor, and a 64-node distributed-memory hypercube. The middle section bridges the gap between the abstract and the practical by giving an overview of how the basic paradigms are implemented.

We focus on the paradigms, not on machine architecture or programming languages: The programming methods we discuss are useful on many kinds of parallel machine, and each can be expressed in several different parallel programming languages. Our programming discussion and the examples use the parallel language C-Linda for several reasons: The main paradigms are all simple to express in Linda; efficient Linda implementations exist on a wide variety of parallel machines; and a wide variety of parallel programs have been written in Linda.
An efficient and fast parallel-connected component algorithm
Authors: Han Yujie , Wagner Robert A.
Published: July 2002

A parallel algorithm for computing the connected components of undirected graphs is presented. Shared memory computation models are assumed. For a graph of
e
edges and
n
nodes, the time complexity of the algorithm is Ο(
e/p
+ (
n
log
n
)/
p
+ log
2
n
) with
p
processors. The algorithm can be further refined to yield time complexity Ο(
H
(
e
,
n
,
p
)/
p
+ (
n
log
n
)/(
p
log(
n
/
p
)) + log
2
n
), where
H
(
e, n, p
) is very close to Ο(
e
). These results show that linear speedup can be obtained for up to
p
≤
e
/log
2
n
processors when
e
≥
n
log
n
. Linear speedup can still be achieved with up to
p
≤
n
ε processors, 0 ≤ ε < 1, for graphs satisfying
e
≥
n
log
(*)
n
. Our results can be further improved if a more efficient integer sorting algorithm is available.
A simple method for improved color printing of monitor images
Authors: Lamming Michael G. , Rhodes Warren L.
Published: July 2002

To print image data optimized for display on a color monitor, the red, green, and blue values that drive the display must be transformed into data that control the amounts of cyan, magenta, yellow, and black on the print. The differences in the way display and print images are produced have important consequences for the transformation. Matching the appearance of the monitor and print images may be impossible, and achieving satisfactory results is complex. A method for obtaining pleasing prints from display image data is presented. This method assumes that good results can be achieved by users who do not have extensive knowledge of color reproduction and who have a minimum of color measuring equipment available.
RIBOSOME-INACTIVATINGPROTEINS: A Plant Perspective
Authors: Nielsen Kirsten , Boston Rebecca S
Published: July 2002

▪ Abstract  Ribosome-inactivating proteins (RIPs) are toxic N-glycosidases that depurinate the universally conserved α-sarcin loop of large rRNAs. This depurination inactivates the ribosome, thereby blocking its further participation in protein synthesis. RIPs are widely distributed among different plant genera and within a variety of different tissues. Recent work has shown that enzymatic activity of at least some RIPs is not limited to site-specific action on the large rRNAs of ribosomes but extends to depurination and even nucleic acid scission of other targets. Characterization of the physiological effects of RIPs on mammalian cells has implicated apoptotic pathways. For plants, RIPs have been linked to defense by antiviral, antifungal, and insecticidal properties demonstrated in vitro and in transgenic plants. How these effects are brought about, however, remains unresolved. At the least, these results, together with others summarized here, point to a complex biological role. With genetic, genomic, molecular, and structural tools now available for integrating different experimental approaches, we should further our understanding of these multifunctional proteins and their physiological functions in plants.
Extreme Ultraviolet Astronomy
Authors: Bowyer Stuart , Drake Jeremy J. , Vennes Stéphane
Published: July 2002

▪ Abstract  Astronomical studies in the extreme ultraviolet (EUV) band of the spectrum were dismissed during the early years of space astronomy as impossible, primarily because of the mistaken view that radiation in this band would be absorbed by the interstellar medium. Observations in the 1980s from sounding rockets and limited duration orbital spacecraft began to show the potential of this field and led to the deployment of two spacecraft devoted to EUV astronomy: the UK Wide Field Camera and the Extreme Ultraviolet Explorer. The instrumentation in these missions, although quite limited in comparison with instrumentation in other fields of space astronomy, provided unique and far-reaching results. These included new information on solar system topics, stellar chromospheres and corona, white dwarf astrophysics, cataclysmic variables, the interstellar medium, galaxies, and clusters of galaxies. We summarize these findings herein.
Extragalactic Results from the Infrared Space Observatory
Authors: Genzel Reinhard , Cesarsky Catherine J.
Published: July 2002

▪ Abstract  More than a decade ago the IRAS satellite opened the realm of external galaxies for studies in the 10 to 100 μm band and discovered emission from tens of thousands of normal and active galaxies. With the 1995–1998 mission of the Infrared Space Observatory1, the next major steps in extragalactic infrared astronomy became possible: detailed imaging, spectroscopy, and spectrophotometry of many galaxies detected by IRAS, as well as deep surveys in the mid- and far-IR. The spectroscopic data reveal a wealth of detail about the nature of the energy source(s) and about the physical conditions in galaxies. ISO's surveys for the first time explore the infrared emission of distant, high-redshift galaxies. ISO's main theme in extragalactic astronomy is the role of star formation in the activity and evolution of galaxies.
Spindle Assembly in Animal Cells
Authors: Compton Duane A.
Published: July 2002

▪ Abstract  Chromosome segregation during mitosis and meiosis is driven by a complex superstructure called the spindle. Microtubules are the primary structural component of spindles, and spindle assembly and function are intimately linked to the intrinsic dynamics of microtubules. This review summarizes spindle structure and highlights recent findings regarding the mechanisms and molecules involved in organizing microtubules into spindles. In addition, mechanisms for chromosome movement and segregation are discussed.
THE STEREOCHEMICAL MECHANISM OF THE COOPERATIVE EFFECTS IN HEMOGLOBIN REVISITED
Authors: Perutz M. F. , Wilkinson A. J. , Paoli M. , Dodson G. G.
Published: July 2002

▪ Abstract  In 1970, Perutz tried to put the allosteric mechanism of hemoglobin, proposed by Monod, Wyman and Changeux in 1965, on a stereochemical basis. He interpreted their two-state model in terms of an equilibrium between two alternative structures, a tense one (T) with low oxygen affinity, constrained by salt-bridges between the C-termini of the four subunits, and a relaxed one (R) lacking these bridges. The equilibrium was thought to be governed primarily by the positions of the iron atoms relative to the porphyrin: out-of-plane in five-coordinated, high-spin deoxyhemoglobin, and in-plane in six-coordinated, low-spin oxyhemoglobin. The tension exercised by the salt-bridges in the T-structure was to be transmitted to the heme-linked histidines and to restrain the movement of the iron atoms into the porphyrin plane that is necessary for oxygen binding. At the β-hemes, the distal valine and histidine block the oxygen-combining site in the T-structure; its tension was thought to strengthen that blockage. Finally, Perutz attributed the linearity of proton release with early oxygen uptake to the sequential rupture of salt-bridges in the T-structure and to the accompanying drop in pKa of the weak bases that form part of them. Almost every feature of this mechanism has been disputed, but evidence that has come to light more than 25 years later now shows it to have been substantially correct. That new evidence is reviewed below.