bluuebunny/crossref_metadata_2025 huggingface dataset:
A Lamarckian Genetic Algorithm Applied to the Travelling Salesman Problem
Authors: Tesfaldet Bereket T. , Hermosilla Augusto Y.
Published: July 2002

Genetic Algorithms (GAs) comprise a class of adaptive heuristic search methods analogous to genetic inheritance and Darwinian strife for survivial of individuals within a population. Today, GAs are widely used to solve complex optimization problems, including ill-conditioned and NP-complete types arising in business, commerce, engineering, large-scale industries, and many other areas. To address these wide areas of applications and to improve upon their drawbacks, many variations and modifications of GAs have been proposed.

The GA variation proposed in this paper has four basic operators: reproduction, recombination and two mutation operators, particularly applied to the famous and extensively studied Traveling Salesman Problem (TSP) in large-scale combinatorial optimization. Three of the operators use diversity information (standard deviation of costs) from the current population to adjust the diversity of the next population. The fourth one is an introduced new mutation operator called p-displacement that simulates the Lamarckian evolutionary learning and training concepts of gene improvement to bring chromosomes to their local optimum. We call the proposed GA: Lamarckian Genetic Algorithm-Traveling Salesman Problem (LGA-TSP). Emprical results show performance improvements compared to the classic and other modified GAs, as well as simulated annealing.
Second-order surface analysis using hybrid symbolic and numeric operators
Authors: Elber Gershon , Cohen Elaine
Published: July 2002

Results from analyzing the curvature of a surface can be used to improve the implementation, efficiency, and effectiveness of manufacturing and visualization of sculptured surfaces.

We develop a robust method using hybrid symbolic and numeric operators to create trimmed surfaces, each of which is solely convex, concave, or saddle and partitions the original surface. The same method is also used to identify regions whose curvature lies within prespecified bounds.
Applying series expansion to the inverse beta distribution to find percentiles of the
F
-distribution
Authors: Abernathy Roger W. , Smith Robert P.
Published: July 2002

Let
0 ≤
1 and
F
be the cumulative distribution function (cdf) of the
F
-Distribution. We wish to find

x
p

such that

F(x
p
|n
1
, n
2
) = p

, where

n
1

and

n
2

are the degrees of freedom. Traditionally,

x
p

is found using a numerical root-finding method, such as Newton's method. In this paper, a procedure based on a series expansion for finding

x
p

is given. The series expansion method has been applied to the normal, chi-square, and
t
distributions, but because of computational difficulties, it has not been applied to the
F
-Distribution. These problems have been overcome by making the standard transformation to the beta distribution.

The procedure is explained in Sections 3 and 4. Empirical results of a comparison of CPU times are given in Section 5. The series expansion is compared to some of the standard root-finding methods. A table is given for
p
= .90.
Algorithm 724; Program to calculate
F
-Percentiles
Authors: Abernathy Roger W. , Smith Robert P.
Published: July 2002

Let
0← p ←1
be given and let F be the cumulative distribution function of the
F
-Distribution with (
M, N,
) degrees of freedom. This FORTRAN 77 routine is a complement to [1] where a method was presented to find the inverse of the
F
-Distribution function, FINV(
M, N, P
), using a series expansion technique to find the inverse for the Beta Distribution function.
A review and taxonomy of distortion-oriented presentation techniques
Authors: Leung Y. K. , Apperley M. D.
Published: July 2002

One of the common problems associated with large computer-based information systems is the relatively small window through which an information space can be viewed. Increasing interest in recent years has been focused on the development of distortion-oriented presentation techniques to address this problem. However, the growing number of new terminologies and techniques developed have caused considerable confusion to the graphical user interface designer, consequently making the comparison of these presentation techniques and generalization of empirical results of experiments with them very difficult, if not impossible. This article provides a taxonomy of distortion-oriented techniques which demonstrates clearly their underlying relationships. A unified theory is presented to reveal their roots and origins. Issues relating to the implementation and performance of these techniques are also discussed.
Parallel algorithms for evaluating sequences of set-manipulation operations
Authors: Atallah Mikhail J. , Goodrich Michael T. , Kosaraju S. Rao
Published: July 2002

Given an off-line sequence
S
of
n
set-manipulation operations, we investigate the parallel complexity of evaluating
S
(i.e., finding the response to every operation in
S
and returning the resulting set). We show that the problem of evaluating
S
is in
NC
for various combinations of common set-manipulation operations. Once we establish membership in
NC
(or, if membership in
NC
is obvious), we develop techniques for improving the time and/or processor complexity.
Information systems strategy and implementation
Authors: Walsham G. , Waema T.
Published: July 2002

The formation and implementation of strategy with respect to computer-based information systems (IS) are important issues in many contemporary organizations, including those in the financial services sector. This paper describes and analyzes an in-depth case study of the strategy formation and implementation process in one such organization, a medium-sized UK building society, and relates the process to its organizational and broader contexts; the organization is examined over a period of several years and under the contrasting leadership of two different chief executives. The case study is used to develop some general implications on IS strategy and implementation, which can be taken as themes for debate in any new situation. The paper provides an example of a more detailed perspective on processes in IS strategy and implementation than typically available in the literature. In addition, a new framework for further research in this area is developed, which directs the researcher toward exploring the dynamic interplay of strategic content, multilevel contexts, and cultural and political perspectives on the process of change.
Reasoning about temporal relations
Authors: Nebel Bernhard , Bürckert Hans-Jürgen
Published: July 2002

We introduce a new subclass of Allen's interval algebra we call “ORD-Horn subclass,” which is a strict superset of the “pointisable subclass.” We prove that reasoning in the ORD-Horn subclass is a polynomial-time problem and show that the path-consistency method is sufficient for deciding satisfiability. Further, using an extensive machine-generated case analysis, we show that the ORD-Horn subclass is a maximal tractable subclass of the full algebra (assuming P ≠ NP). In fact, it is the unique greatest tractable subclass amongst the subclasses that contain all basic relations.
Nearly optimal algorithms and bounds for multilayer channel routing
Authors: Berger Bonnie , Brady Martin , Brown Donna , Leighton Tom
Published: July 2002

This paper presents algorithms for routing channels with
L
≥2 layers. For the unit vertical overlap model, we describe a two-layer channel routing algorithm that uses at most
d + O(√d)
tracks to route two-terminal net problems and
2d + O(√d)
tracks to route multiterminal nets. We also show that
d + Ω(log d)
tracks are required to route two-terminal net problems in the worst case even if arbitrary vertical overlap is allowed. We generalize the algorithm to unrestricted multilayer routing and use only
d/(L -1) + O(√d/L + 1)>
tracks for two-terminal net problems (within
O(√d/L + 1)
tracks of optimal) and
d/(L-2) +O(√d/L + 1)
tracks for multiterminal net problems (within a factor of(L-1)/(L-2) times optimal). We demonstrate the generality of our routing strategy by showing that it can be used to duplicate some of the best previous upper bounds for other models (two-layer Manhattan routing and two and three-layer knock-knee routing of two-terminal, two-sided nets), and gives a new upper bound for rotuing with 45-degree diagonal wires.
Lessons learned from the OS/400 OO project
Authors: Berg William , Cline Marshall , Girou Mike
Published: July 2002

This article describes some of the lessons learned when a team of 150 developers with a minimal prior exposure to object-oriented (OO) technology undertook a large development project. Team members became proficient in OO design, using C++ as an OO language rather than just using C++ as a better C, and developed IBM's RISC version of the AS/400 and System/36 operating systems from 1992 to 1994 in Rochester, Minnesota. The project contains 14,000 thousand classes, 90,000 thousand methods, and 2 million lines of C++ integrated into 20 million lines of total code. The result of their efforts was the development of a product that is being used daily by a substantial international customer base.
Semantics and verification of action diagrams with linear timing
Authors: Khordoc K. , Cerny E.
Published: July 2002

Specifications containing linear timing constraints, such as found in action diagrams (timing diagrams) defining interface behaviors, are often used in practice. Although efficient

O(n
3
)

shortest path algorithms exist for computing the minimum and maximum time distances between actions, subject to the timing constraints, there is so far no accurate method that can decide (a) whether a specification of this kind is realizable (i.e., can be simulated by a causal system), and (b) given the action diagrams of the interfaces of two or more communicating systems, whether the systems implementing such independent specifications will correctly interoperate (i.e., satisfy the respective protocols and timing assumptions). First we illustrate the weakness of existing action diagram verification techniques:
the causality issue is not addressed, and the proposed methods to answer the compatibility (interoperability) question yield false negative answers in many practical situations. We then define the meaning of causality in an action diagram specification and state a set of sufficient conditions for causality to hold. This development then leads to an exact procedure for the verification of the interface compatibility of communicating action diagrams. the results are illustrated on a practical example.
Property testing and its connection to learning and approximation
Authors: Goldreich Oded , Goldwasser Shari , Ron Dana
Published: July 2002

In this paper, we consider the question of determining whether a function
f
has property P or is ε-far from any function with property P. A
property testing
algorithm is given a sample of the value of
f
on instances drawn according to some distribution. In some cases, it is also allowed to query
f
on instances of its choice. We study this question for different properties and establish some connections to problems in learning theory and approximation.

In particular, we focus our attention on testing graph properties. Given access to a graph G in the form of being able to query whether an edge exists or not between a pair of vertices, we devise algorithms to test whether the underlying graph has properties such as being bipartite,
k
-Colorable, or having a
p
-Clique (clique of density
p
with respect to the vertex set). Our graph property testing algorithms are probabilistic and make assertions that are correct with high probability, while making a number of queries that is
independent
of the size of the graph. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph that correspond to the property being tested, if it holds for the input graph.
A denotational semantics for a process-based simulation language
Authors: Tofts Chris , Birtwistle Graham
Published: July 2002

In this article, we present semantic translations for the actions of μDemos, a proocess-based, discrete event simulation language. Our formal translation schema permits the automatic construction of a process algebraic representatioon of the underlying simulation model which can then be checked for freedom from deadlock and livelock, as well as system-specific safety and liveness properties. As simulation methodologies are increasingly being used to design and implement complex systems of interaction objects, the ability to perform such verifications in of increasing methodological importance. We also present a normal form for the syntactic construction of μDemos programs that allows for the direct comparison of such programs (two programs with the same normal form must execute in identical fashion), reduces model proof obligations by minimizing the number of language constructs, and permits an implementer to concentrate on the basic features of the language (since any program implementation that efficiently evaluates normal forms will be an efficient evaluator for the complete language).
On measuring the effectiveness of various design validation approaches for PowerPC microprocessor embedded arrays
Authors: Wang Li-C. , Abadir Magdy S. , Zeng Jing
Published: July 2002

Design validation for embedded arrays remains as a challenging problem in today's microprocessor design environment. At Somerset, validation of array designs relies on both formal verification and vector simulation. Although several methods for array design validation have been proposed and had great success [Ganguly et al. 1996; Pandey et al. 1996, 1997; Wang and Abadir 1997], little evidence has been reported for the effectiveness of these methods with respect to the detection of design errors. In this paper, we measure the effectiveness of different validation approaches based on automatic design error injection and simulation. The technique provides a systematic way to evaluate various validation approaches at both logic and transistor levels. Experimental results on recent PowerPC microprocessor arrays will be discussed and reported.
Interface and data architecture for query preview in networked information systems
Authors: Plaisant Catherine , Shneiderman Ben , Doan Khoa , Bruns Tom
Published: July 2002

There are numerous problems associated with formulating queries on networked information systems. These include increased data volume and complexity, accompanied by slow network access. This article proposes a new approach to a network query user interfaces that consists of two phases: query preview and query refinement. This new approach is based on the concepts of dynamic queries and query previews, which guides users in rapidly and dynamically eliminating undesired records, reducing the data volume to a manageable size, and refining queries locally before submission over a network. Examples of two applications are given: a Restaurant Finder and a prototype for NASA's Earth Observing Systems Data Information Systems (EOSDIS). Data architecture is discussed, and user feedback is presented.
Integration of a primal simplex network algorithm with a large-scale mathematical programming system
Authors: Tomlin J. A. , Welch J. S.
Published: July 2002

In this paper we discuss the implementation of a primal simplex algorithm for network problems in the MPSIII mathematical programming system. Because of the need to interface with the rest of the MPS this implementation is unorthodox, but computationally effective, and has a number of advantages over “stand alone” network optimizers. It is argued that a similar approach is appropriate for other general-purpose mathematical programming systems, and has applications beyond pure network optimization.
Compromising statistical databases responding to queries about means
Authors: de Jonge Wiebren
Published: July 2002

This paper describes how to compromise a statistical database which
only
answers queries about arithmetic means for query sets whose cardinality falls in the range [
k, N
-
k
], for some
k
> 0, where
N
≥ 2
k
is the number of records in the database. The compromise is shown to be easy and to require only a little preknowledge; knowing the cardinality of just one nonempty query set is usually sufficient.

This means that not only count and sum queries, but also queries for arithmetic means can be extremely dangerous for the security of a statistical database, and that this threat must be taken into account explicitly by protective measures. This seems quite important from a practical standpoint: while arithmetic means were known for some time to be not altogether harmless, the (perhaps surprising) extent of the threat is now shown.
Hashing and trie algorithms for partial match retrieval
Authors: Burkhard W. A.
Published: July 2002

File designs suitable for retrieval from a file of
k
-letter words when queries may be only partially specified are examined. A new class of partial match file designs (called PMF designs) based upon hash coding and trie search algorithms which provide good worst-case performance is introduced. Upper bounds on the worst-case performance of these designs are given along with examples of files achieving the bound. Other instances of PMF designs are known to have better worst-case performances. The implementation of the file designs with associated retrieval algorithms is considered. The amount of storage required is essentially that required of the records themselves.
The Immortality Problem for Post Normal Systems
Authors: Hooper Philip K.
Published: July 2002

A natural problem, related to the (known unsolvable) halting problem for Post normal systems, arises when one considers, for a given Post normal system, whether the system halts (eventually) on
every
word over its alphabet. For polygenic systems, this problem is shown to be recursively unsolvable by constructing a reduction from the “Domino Problem.”
An Adaptation of the Fast Fourier Transform for Parallel Processing
Authors: Pease Marshall C.
Published: July 2002

A modified version of the Fast Fourier Transform is developed and described. This version is well adapted for use in a special-purpose computer designed for the purpose. It is shown that only three operators are needed. One operator replaces successive pairs of data points by their sums and differences. The second operator performs a fixed permutation which is an ideal shuffle of the data. The third operator permits the multiplication of a selected subset of the data by a common complex multiplier.

If, as seems reasonable, the slowest operation is the complex multiplications required, then, for reasonably sized date sets—e.g. 512 complex numbers—parallelization by the method developed should allow an increase of speed over the serial use of the Fast Fourier Transform by about two orders of magnitude.

It is suggested that a machine to realize the speed improvement indicated is quite feasible.

The analysis is based on the use of the Kronecker product of matrices. It is suggested that this form is of general use in the development and classification of various modifications and extensions of the algorithm.
Accumulation of Round-Off Error in Fast Fourier Transforms
Authors: Kaneko Toyohisa , Liu Bede
Published: July 2002

The fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier coefficients with a substantial time saving over conventional methods. The finite word length used in the computer causes an error in computing the Fourier coefficients. This paper derives explicit expressions for the mean square error in the FFT when floating-point arithmetics are used. Upper and lower bounds for the total relative mean square error are given. The theoretical results are in good agreement with the actual error observed by taking the FFT of data sequences.
Efficient Exercising of Switching Elements in Combinatorial Nets
Authors: Richards Donald L.
Published: July 2002

The work described in a previous paper, “Efficient Exercising of Switching Elements in Nets of Identical Gates,” is continued. Sections 1, 3, and 4 of the previous paper are prerequisites to the current work.

Exercising, or “testing,” the gates of a net is equivalent to performing fault diagnosis in the case in which each fault is detectable. Where
F
is any set of switching functions, this paper establishes a necessary and sufficient condition on an arbitrary function set
G
such that all trees composed only of functions from
F
will accept
G
; choosing
G
as the “testing” functions
P
(
T, r
) of the previous paper, this is the condition under which all such trees can be tested by
r
(or fewer) patterns.

The case of “stuck-at” faults is then investigated at length. It is shown that: (a) all trees can be tested for stuck-at faults by three patterns, and nearly all by two patterns; (b) for some interesting classes of functions, all
nets
can be tested by two patterns—in general, many nets can; (c) for any set of functions which are functionally complete and suitably closed under constant inputs, there are nets which require arbitrarily many patterns. The latter result suggests that nets requiring arbitrarily many patterns exist for nearly all interesting choices of functions and of faults.

For “input dependence” tests, a result is cited to show that economical testing of nets of nand (nor) gates of mixed sizes is possible.

Finally, for the case of exhaustive testing, experience suggests that economical tests exist for most nets composed from functions of
F
wherever
F
is a
bounded
set—i.e. a set of functions for which there is a fixed upper bound on the number of patterns required to test any tree. The (individually) bounded functions are completely characterized; then the bounded sets of symmetric functions are completely characterized. The latter prove to be those sets for which: (a) each function is individually bounded (i.e. not “and,” “or,” or constant); and (b)
F
contains at most one of the following: (1) “not,” (2) a “nand” function, (3) a “nor” function. Thus bounded sets of functions are the rule, not the exception, and economical testing appears to be generally possible.
Automated Theorem-Proving for Theories with Simplifiers Commutativity, and Associativity
Authors: Slagle James R.
Published: July 2002

To prove really difficult theorems, resolution principle programs need to make better inferences and to make them faster. An approach is presented for taking advantage of the structure of some special theories. These are theories with simplifiers, commutativity, and associativity, which are valuable concepts to build in, since they so frequently occur in important theories, for example, number theory (plus and times) and set theory (union and intersection). The object of the approach is to build in such concepts in a (refutation) complete, valid, efficient (in time) manner by means of a “natural” notation and/or new inference rules. Some of the many simplifiers that can be built in are axioms for (left and right) identities, inverses, and multiplication by zero.

As for results, commutativity is built in by a straightforward modification to the unification (matching) algorithm. The results for simplifiers and associativity are more complicated. These theoretical results can be combined with one another and/or extended to either
C
-linear refutation completeness or theories with partial ordering, total ordering, or sets. How these results can serve as the basis of practical computer programs is discussed.
A comparison of numerical techniques in Markov modeling
Authors: Stewart William J.
Published: July 2002

This paper presents several numerical methods which may be used to obtain the stationary probability vectors of Markovian models. An example of a nearly decomposable system is considered, and the results obtained by the different methods examined. A post mortem reveals why standard techniques often fail to yield the correct results. Finally, a means of estimating the error inherent in the decomposition of certain models is presented.
Optimal conversion of extended-entry decision tables with general cost criteria
Authors: Lew Art
Published: July 2002

A general dynamic programming algorithm for converting limited, extended, or mixed entry decision tables to optimal decision trees is presented which can take into account rule frequencies or probabilities, minimum time and/or space cost criteria, common action sets, compressed rules and ELSE rules, sequencing constraints on condition tests, excludable combinations of conditions, certain ambiguities, and interrupted rule masking.
SITAR
Authors: Schneider Ben Ross , Watts Reid M.
Published: July 2002

SITAR, a low-cost interactive text handling and text analysis system for nontechnical users, is in many ways comparable to interactive bibliographical search and retrieval systems, but has several additional features. It is implemented on a PDP/11 time-sharing computer invoked by a CRT with microprogrammed editing functions. It uses a simple command language designating a function, a file, and a search template consisting of the textual string desired and strings delimiting the context in which the hit is to be delivered. Extensive experience with SITAR shows that the combined powers of simple commands, string orientation, circular file structure, a CRT with local memory, and conversational computing produce a system much more powerful than the sum of its parts.
On self-organizing sequential search heuristics
Authors: Rivest Ronald
Published: July 2002

This paper examines a class of heuristics for maintaining a sequential list in approximately optimal order with respect to the average time required to search for a specified element, assuming that each element is searched for with a fixed probability independent of previous searches performed. The “move to front” and “transposition” heuristics are shown to be optimal to within a constant factor, and the transposition rule is shown to be the more efficient of the two. Empirical evidence suggests that transposition is in fact optimal for any distribution of search probabilities.
The development of decision tables via parsing of complex decision situations
Authors: Strunz Horst
Published: July 2002

A new parsing technique is proposed which allows parsing based only on syntactical characteristics of the decision problem. It requires a description of the problem in decision grid chart format and allows the development of decision tables within defined limits by avoiding, or at least minimizing, repetition of conditions and actions in the resulting tables.
On simulating networks of parallel processes in which simultaneous events may occur
Authors: Parnas David L.
Published: July 2002

The following resolutions were passed at the ASA X3.4 Common Programming Languages Subcommittee during the thirty-third meeting held February 20, 1964 at CEIR, Beverly Hills, California.
Application of IBM 1620 EDP methods to the calculation of the formulation constants of complex ions
Authors: Andrews A. C. , Hassler John , DeCou Frank
Published: July 2002

In the course of our work on the physical chemistry of histamine and related compounds, we have done extensive work involving potentiometric titration of systems of chelates of these ligands with various metallic ions, negative ions, and small molecules. The resulting data is used to calculate the stability constants in solution (1, 2, 3, 4). The mathematical calculations for a single titration require two to four hours when done on a desk calculator, even when the operator is experienced. This is a serious disadvantage of the technique. The more accurate methods of successive approximations and of simultaneous equations [2] are so time consuming that their routine use is impractical without the aid of a high speed computer.
Data and memory optimization techniques for embedded systems
Authors: Panda P. R. , Catthoor F. , Dutt N. D. , Danckaert K. , Brockmeyer E. , Kulkarni C. , Vandercappelle A. , Kjeldsberg P. G.
Published: July 2002

We present a survey of the state-of-the-art techniques used in performing data and memory-related optimizations in embedded systems. The optimizations are targeted directly or indirectly at the memory subsystem, and impact one or more out of three important cost metrics: area, performance, and power dissipation of the resulting implementation.

We first examine architecture-independent optimizations in the form of code transoformations. We next cover a broad spectrum of optimization techniques that address memory architectures at varying levels of granularity, ranging from register files to on-chip memory, data caches, and dynamic memory (DRAM). We end with memory addressing related issues.
Course and exercise sequencing using metadata in adaptive hypermedia learning systems
Authors: Fischer Stephan
Published: July 2002

In the last few years the (semi-) automatic sequencing of course material has become an important research issue, particularly the standardization of metadata for educational resources. Sequencing can help to generate hypermedia documents which, at their best match the learner's needs. To perform (semi-) automatic course sequencing, a knowledge library as well as modular resources can be used. Both must be described by metadata.

First, metadata standards (IEEE Learning Objects Metadata, Instructional Management Systems Global Learning Consortium, Dublin Core) are analyzed with regard to course sequencing. As an application example, Multibook, an adaptive hypermedia system used to teach multimedia technology, is described. Multibook uses metadata to create course se- quences semi-automatically. In this article we explain how a knowledge library can be used to create exercises automatically. We give an example of how courses can be sequenced in general by analyzing the creation of exercises. An evaluation of our system shows the advantages and drawbacks of the automatic course sequencing approach.
Data-flow algorithms for parallel matrix computation
Authors: O'Leary Dianne P. , Stewart G. W.
Published: July 2002

In this article we develop some algorithms and tools for solving matrix problems on parallel processing computers. Operations are synchronized through data-flow alone, which makes global synchronization unnecessary and enables the algorithms to be implemented on machines with very simple operating systems and communication protocols. As examples, we present algorithms that form the main modules for solving Liapounov matrix equations. We compare this approach to wave front array processors and systolic arrays, and note its advantages in handling missized problems, in evaluating variations of algorithms or architectures, in moving algorithms from system to system, and in debugging parallel algorithms on sequential machines.
Optimal directory placement on disk storage devices
Authors: Calderbank A. R. , Coffman E. G. , Flatto Leopold
Published: July 2002

Two mathematical models dealing with optimal placement of directories on disk devices are analyzed. Storage addresses on the disk are approximated by points in the interval [0, 1]. Requests for information on the disk are represented by a sequence of file names. To process a request, a read-write head is first moved to a directory kept on the disk that specifies the address of the file, and then a head is moved to the specified address. The addresses are assumed to be independent and uniform on [0,1].

In the first model we consider a system of two heads separated by a fixed distance
d
and a directory situated at 0 ≤
x
≤ 1. In the second model we consider a system consisting of one head and
n
≥ 2 directories at 0 ≤
x
1
<
x
2
< … <
x

n

≤ 1. For both models we study the problem of finding those values of the parameters that minimize the expected head motion to process a request in statistical equilibrium.
Semantic database modeling: survey, applications, and research issues
Authors: Hull Richard , King Roger
Published: July 2002

Most common database management systems represent information in a simple record-based format. Semantic modeling provides richer data structuring capabilities for database applications. In particular, research in this area has articulated a number of constructs that provide mechanisms for representing structurally complex interrelations among data typically arising in commercial applications. In general terms, semantic modeling complements work on knowledge representation (in artificial intelligence) and on the new generation of database models based on the object-oriented paradigm of programming languages.

This paper presents an in-depth discussion of semantic data modeling. It reviews the philosophical motivations of semantic models, including the need for high-level modeling abstractions and the reduction of semantic overloading of data type constructors. It then provides a tutorial introduction to the primary components of semantic models, which are the explicit representation of objects, attributes of and relationships among objects, type constructors for building complex types, ISA relationships, and derived schema components. Next, a survey of the prominent semantic models in the literature is presented. Further, since a broad area of research has developed around semantic modeling, a number of related topics based on these models are discussed, including data languages, graphical interfaces, theoretical investigations, and physical implementation strategies.
A practical approach for implementing e-commerce programs in business schools
Authors: Bartholome Lloyd W. , Olsen David H.
Published: July 2002

Ignoring the `e' component in business education does a great disservice to students preparing for a career in business.
Alloy
Authors: Jackson Daniel
Published: July 2002

Alloy is a little language for describing structural properties. It offers a declaration syntax compatible with graphical object models, and a set-based formula syntax powerful enough to express complex constraints and yet amenable to a fully automatic semantic analysis. Its meaning is given by translation to an even smaller (formally defined) kernel. This paper presents the language in its entirety, and explains its motivation, contributions and deficiencies.
Integrating communication and information through ContactMap
Authors: Nardi Bonnie A. , Whittaker Steve , Isaacs Ellen , Creech Mike , Johnson Jeff , Hainsworth John
Published: July 2002

Visualizing personal social networks, the system allows users to model and arrange their own in maps of individual contacts and groups, along with the relationships among them.
Selected papers from the sixth international conference on information systems
Authors: Davis Gordon B.
Published: July 2002

There are a number of alternative tools and methods for building and designing information systems for organizational use. Each tool or design alternative has its advocates. Benefits and advantages are proposed or claimed; little empirical evidence is presented.

The two selected papers from the 1985 International Conference on Information Systems (Indianapolis, December 15-18) present empirical laboratory experiments to provide evidence as to tools and design alternatives. The first paper by Dickson, DeSanctis, and McBride describes three experiments to compare traditional tabular presentation with graphic presentation. The experiments are designed to build cumulative research results around the issue of the task the reader of the information is to perform upon receiving the information. The second paper by Vessey and Weber provides experimental evidence comparing methods for documenting a problem: decision tree, decision table, and structured English. The three methods are frequently presented as alternatives; the experiments compare them.

Two studies do not settle an issue as complex as comparison of alternative tools and methods: they begin to provide the evidence needed. They also illustrate one well-established research approach—the laboratory experiment. The advantage of laboratory experiments is the control that can be obtained; field studies and experience of practitioners can be understood more fully in the context of such laboratory results.
Fragmentation: a technique for efficient query processing
Authors: Sacco Giovanni Maria
Published: July 2002

A “divide and conquer” strategy to compute natural joins by sequential scans on unordered relations is described. This strategy is shown to always he better than merging SCBIIS when both relations must he sorted before joining, and generally better in practical cases when only the largest relation mutt be sorted.
NFQL: the natural forms query language
Authors: Embley David W.
Published: July 2002

A means by which ordinary forms can be exploited to provide a basis for nonprocedural specification of information processing is discussed. The Natural Forms Query Language (NFQL) is defined. In NFQL data retrieval requests and computation specifications are formulated by sketching ordinary forms to show what data are desired and update operations are specified by altering data on filled-in forms. The meaning of a form depends on a store of knowledge that includes extended abstract data types for defining elementary data items, a database scheme defined by an entity-relationship model, and a conceptual model of an ordinary form. Based on this store of knowledge, several issues are addressed and resolved in the context of NFQL. These issues include automatic generation of query expressions from weak specifications, the view update problem, power and completeness, and a heuristic approach to resolving computational relationships. A brief status report of an implementation of NFQL is also given.
The distributed deadlock detection algorithm
Authors: Badal D. Z.
Published: July 2002

We propose a distributed deadlock detection algorithm for distributed computer systems. We consider two types of resources, depending on whether the remote resource lock granularity and mode can or cannot be determined without access to the remote resource site. We present the algorithm, its performance analysis, and an informal argument about its correctness. The proposed algorithm has a hierarchical design intended to detect the most frequent deadlocks with maximum efficiency.
On the Optimal Solution of Large Linear Systems
Authors: Traub J. F. , Woźniakowski H.
Published: July 2002

The information-based study of the optimal solution of large
linear systems is initiated by studying the case of Krylov
information. Among the algorithms that use Krylov information are
minimal residual, conjugate gradient, Chebyshev, and successive
approximation algorithms. A "sharp" lower bound on the number of
matrix-vector multiplications required to compute an
å-approximation is obtained for any orthogonally invariant
class of matrices. Examples of such classes include many of
practical interest such as symmetric matrices, symmetric positive
definite matrices, and matrices with bounded condition number. It
is shown that the minimal residual algorithm is within at most one
matrix-vector multiplication of the lower bound. A similar result
is obtained for the generalized minimal residual algorithm. The
lower bound is computed for certain classes of orthogonally
invariant matrices. How the lack of certam properties (symmetry,
positive definiteness) increases the lower bound is shown. A
conjecture and a number of open problems are stated.
HORMONE-INDUCED SIGNALING DURING MOSS DEVELOPMENT
Authors: Schumaker Karen S. , Dietrich Margaret A.
Published: July 2002

▪ Abstract  Understanding how a cell responds to hormonal signals with a new program of cellular differentiation and organization is an important focus of research in developmental biology. In Funaria hygrometrica and Physcomitrella patens, two related species of moss, cytokinin induces the development of a bud during the transition from filamentous to meristematic growth. Within hours of cytokinin perception, a single-celled initial responds with changes in patterns of cell expansion, elongation, and division to begin the process of bud assembly. Bud assembly in moss provides an excellent model for the study of hormone-induced organogenesis because it is a relatively simple, well-defined process. Since buds form in a nonrandom pattern on cells that are not embedded in other tissues, it is possible to predict which cells will respond and where the ensuing changes will take place. In addition, bud assembly is amenable to biochemical, cellular, and molecular biological analyses. This review examines our current understanding of cytokinin-induced bud assembly and the potential underlying mechanisms, reviews the state of genetic analyses in moss, and sets goals for future research with this organism.
A Fortunate Life in Astronomy
Authors: Osterbrock Donald E.
Published: July 2002

▪ Abstract  I have had a very fortunate career in astronomy, benefiting greatly from numerous accidents of fate. I grew up in Cincinnati, Ohio, served in the US Army Air Force in World War II, and had all my further education at the University of Chicago, from PhB in the College to PhD in astronomy and astrophysics. There, as a postdoc at Princeton University, and as a young faculty member at Caltech and Mount Wilson and Palomar Observatories, I had excellent teachers and mentors. I have done research primarily on gaseous nebulae and active galactic nuclei, but also made a few early contributions on stellar interiors and the heating in the outer layers of the Sun. The major part of my scientific career was at the University of Wisconsin and Lick Observatory, but I also had three productive years at the Institute for Advanced Study.
CLATHRIN-COATED VESICLE FORMATION AND PROTEIN SORTING: An Integrated Process
Authors: Schmid Sandra L.
Published: July 2002

Clathrin-coated vesicles were the first discovered and remain the most extensively characterized transport vesicles. They mediate endocytosis of transmembrane receptors and transport of newly synthesized lysosomal hydrolases from the trans-Golgi network to the lysosome. Cell-free assays for coat assembly, membrane binding, and coated vesicle budding have provided detailed functional and structural information about how the major coat constituents, clathrin and the adaptor protein complexes, interact with each other, with membranes, and with the sorting signals found on cargo molecules. Coat constituents not only serve to shape the budding vesicle, but also play a direct role in the packaging of cargo, suggesting that protein sorting and vesicle budding are functionally integrated. The functional interplay between the coated vesicle machinery and its cargo could ensure sorting fidelity and packaging efficiency and might enable modulation of vesicular trafficking in response to demand.
THE ATP SYNTHASE—A SPLENDID MOLECULAR MACHINE
Authors: Boyer Paul D.
Published: July 2002

An X-ray structure of the F1 portion of the mitochondrial ATP synthase shows asymmetry and differences in nucleotide binding of the catalytic β subunits that support the binding change mechanism with an internal rotation of the γ subunit. Other structural and mutational probes of the F1 and F0 portions of the ATP synthase are reviewed, together with kinetic and other evaluations of catalytic site occupancy and behavior during hydrolysis or synthesis of ATP. Subunit function as related to proton translocation and rotational catalysis is considered. Physical demonstrations of the γ subunit rotation have been achieved. The findings have implications for other enzymatic catalyses.
Fluid Motions in the Presence of Strong Stable Stratification
Authors: Riley James J. , Lelong Marie-Pascale
Published: July 2002

▪ Abstract  We review the dynamics of stably stratified flows in the regime in which the Froude number is considered small and the Rossby number is of order one or greater. In particular we emphasize the nonpropagating component of the flow field, as opposed to the internal wave component. Examples of such flows range from the later stages of decay of turbulent flows to mesoscale meteorological flows. Results from theoretical analyses, laboratory experiments, and numerical simulations are presented. The limiting form of the equations of motion appears to describe the laboratory experiments and numerical simulations rather well. There are similarities with the dynamics of two-dimensional flows, but three-dimensional effects are clearly important. A number of remaining open issues are discussed.
EARLY WORK ON FLUID MECHANICS IN THE IC ENGINE
Authors: Lumley John L
Published: July 2002

▪ Abstract  Early work of Ricardo is described, in which squish is used in flat-head engines to generate turbulence levels comparable to those in overhead-valve engines, leading to rapid flame propagation, and suppressing knock. Work by NACA before World War II is described, in which turbulence levels were measured in overhead-valve engines, indicating indirectly that surprisingly high levels were achieved just before ignition, possibly due to a tumble instability. Finally, work of Obukhov of 30 years ago is described, in which instabilities of tumbling flow are investigated in ellipsoids crudely modeling the engine cylinder as the piston rises; this suggests that there is an instability leading to intense small-scale motion just before ignition. Suggestions for further work are given.
PARENTAL IMPRINTING AND HUMAN DISEASE
Authors: Lalande M.
Published: July 2002

▪ Abstract  Parental imprinting is a process that results in allele-specific differences in transcription, DNA methylation, and DNA replication timing. Imprinting plays an important role in development, and its deregulation can cause certain defined disease states. Absence of a paternal contribution to chromosome 15q11–q13, due to hemizygous deletion or uniparental disomy, results in the Prader-Willi syndrome. The absence of a normal maternal copy of the same region causes Angelman syndrome. The Beckwith-Wiedemann syndrome is associated with the failure of normal biparental inheritance of chromosome 11p15, and loss of imprinting is observed in several cancers including Wilms' tumor. The study of the molecular basis of abnormal imprinting in these disorders will facilitate the identification and characterization of other imprinted human disease loci.
HOST-PATHOGEN INTERACTIONS DURING ENTRY AND ACTIN-BASED MOVEMENT OFLISTERIA MONOCYTOGENES
Authors: Ireton Keith , Cossart Pascale
Published: July 2002

▪ Abstract  Listeria monocytogenes is a pathogenic bacterium that induces its own uptake into mammalian cells, and spreads from one cell to another by an actin-based motility process. Entry into host cells involves the bacterial surface proteins InlA (internalin) and InlB. The receptor for InlA is the cell adhesion molecule E-cadherin. InlB-mediated entry requires activation of the host protein phosphoinositide (PI) 3-kinase, probably in response to engagement of a receptor. Actin-based movement of L. monocytogenes is mediated by the bacterial surface protein ActA. The N-terminal region of this protein is necessary and sufficient for polymerization of host cell actin. Other host proteins involved in bacterial motility include profilin, Vasodilator-Stimulated Phosphoprotein (VASP), the Arp2/Arp3 complex, and cofilin. Studies of entry and intracellular movement of L. monocytogenes could lead to a better understanding of receptor-ligand signaling and dynamics of actin polymerization in mammalian cells.
Advances in In Situ Ultra-High Vacuum Electron Microscopy: Growth of SiGe on Si
Authors: Tromp Ruud M. , Ross Frances M.
Published: July 2002

▪ Abstract  In situ Ultra-High Vacuum (UHV) electron microscopy, including Transmission Electron Microscopy (TEM) at 300 keV electron energy and Low-Energy Electron Microscopy (LEEM) at 0-30 eV electron energy, has advanced enormously over the last decade. Growth of thin films such as epitaxial Si1−xGex alloy thin films on Si substrates has become routine, allowing high-resolution video-rate studies of processes such as misfit dislocation injection and interaction, surface roughening and faceting, self-assembly of quantum dots, and shape transitions in such quantum dots. We review results obtained in the SiGe/Si system in the last five years. In addition we discuss new directions in in situ electron microscopy as they apply to thin film formation in a range of materials and environments.

[ Erratum ]