bluuebunny/crossref_metadata_2025 huggingface dataset:
GENETIC ALGORITHMS AND THE ANDREWS–CURTIS CONJECTURE
Authors: MIASNIKOV ALEXEI D.
Published: July 2002

The Andrews–Curtis conjecture claims that every balanced presentation of the trivial group can be transformed into the trivial presentation by a finite sequence of "elementary transformations" which are Nielsen transformations together with an arbitrary conjugation of a relator. It is believed that the Andrews–Curtis conjecture is false; however, not so many possible counterexamples are known. It is not a trivial matter to verify whether the conjecture holds for a given balanced presentation or not. The purpose of this paper is to describe some nondeterministic methods, called Genetic Algorithms, designed to test the validity of the Andrews–Curtis conjecture. Using such algorithm we have been able to prove that all known (to us) balanced presentations of the trivial group where the total length of the relators is at most 12 satisfy the conjecture. In particular, the Andrews–Curtis conjecture holds for the presentation [Formula: see text] which was one of the well known potential counterexamples.
THE GLOBAL WEAK SOLUTION AND RELAXATION LIMITS OF THE INITIAL–BOUNDARY VALUE PROBLEM TO THE BIPOLAR HYDRODYNAMIC MODEL FOR SEMICONDUCTORS
Authors: HSIAO LING , ZHANG KAIJUN
Published: July 2002

The convergence and consistency of approximate solutions derived by the modified Godunov scheme for the initial–boundary value problem to a bipolar hydrodynamic model for semiconductors are proved using the compensated compactness framework. The information of weak solutions to satisfy the boundary conditions is also displayed. The zero relaxation limit of the bipolar hydrodynamic model towards the drift-diffusion model is carried out when the current relaxation time tends to zero.
THE QUASI-CLASSICAL MODEL OF THE SPHERICAL CONFIGURATION IN GENERAL RELATIVITY
Authors: GLADUSH VALENTIN D.
Published: July 2002

We consider the quasi-classical model of the spin-free configuration on the basis of the self-gravitating spherical dust shell in general relativity. For determination of the energy spectrum of the stationary states on the basis of quasi-classical quantization rules it is required to carry out some regularization of the system. It is realized by an embedding of the initial system in the extended system with rotation. Then, the stationary states of the spherical shells are S-states of the system with the intrinsic momentum. The quasi-classical treatment of a stability of the configuration is associated with the Langer modification of a square of the quantum mechanical intrinsic momentum. It gives value of critical bare mass of the shell determining threshold of stability. For the shell with the bare mass smaller or equal to the Planck's mass, the energy spectra of bound states are found. We obtain the expression for tunneling probability of the shell and construct the quasi-classical model of the pair creation and annihilation of the shells.
DYNAMIC WORMHOLES
Authors: HAYWARD SEAN A.
Published: July 2002

A new framework is proposed for general dynamic wormholes, unifying them with black holes. Both are generically defined locally by outer trapping horizons, temporal for wormholes and spatial or null for black and white holes. Thus wormhole horizons are two-way traversible, while blackhole and whitehole horizons are only one-way traversible. It follows from the Einstein equation that the null energy condition is violated everywhere on a generic wormhole horizon. It is suggested that quantum inequalities constraining negative energy break down at such horizons. Wormhole dynamics can be developed as for blackhole dynamics, including a reversed second law and a first law involving a definition of wormhole surface gravity. Since the causal nature of a horizon can change, being spatial under positive energy and temporal under sufficient negative energy, blackholes and wormholes are interconvertible. In particular, if a wormhole's negative-energy source fails, it may collapse into a blackhole. Conversely, irradiating a blackhole horizon with negative energy could convert it into a wormhole horizon. This also suggests a possible final state of blackhole evaporation: a stationary wormhole. The new framework allows a fully dynamical description of the operation of a wormhole for practical transport, including the back-reaction of the transported matter on the wormhole. As an example of a matter model, a Klein–Gordon field with negative gravitational coupling is a source for a static wormhole of Morris and Thorne.
EXACT STATIC SOLUTIONS IN FOUR-DIMENSIONAL EINSTEIN–MAXWELL-DILATON GRAVITY
Authors: YAZADJIEV S.
Published: July 2002

Classes of exact static solutions in four-dimensional Einstein–Maxwell-dilaton gravity are found. Besides the well-known solutions previously found in the literature, new solutions are presented. It is shown that spherically symmetric solutions, except for the case of a charged dilaton black hole, represent globally naked strong curvature singularities.
ATOMIC LAYER DEPOSITION OF SiO2 USING CATALYZED AND UNCATALYZED SELF-LIMITING SURFACE REACTIONS
Authors: KLAUS J. W. , SNEH O. , OTT A. W. , GEORGE S. M.
Published: July 2002

SiO 2 thin films were deposited with atomic layer control using self-limiting surface reactions. The SiO 2 growth was achieved by separating the binary reaction SiCl 4+ 2H 2 O → SiO 2+ 4HCl into two half-reactions. Successive application of the half-reactions in an ABAB… sequence produced atomic-layer-controlled SiO 2 deposition. SiO 2 films were grown at temperatures of 600–800 K, with SiCl 4 and H 2 O reactant exposures of ~109 L ( 1 L = 10-6 Torr s). Employing pyridine ( C 5 H 5 N ) as a catalyst, the SiO 2 films could be deposited at much lower temperatures and reactant exposures. The pyridine catalyst lowered the required SiO 2 deposition temperature from 600 K to 300 K and reduced the reactant exposure required for complete reactions from ~109 L to ~ 104 L. In addition, the SiO 2 growth rates increased from 0.75 Å per AB cycle at 800 K to 2.1 Aring; per AB cycle at 300 K. The deposited films were stoichiometric SiO 2 and were extremely flat, with a roughness nearly identical to the initial substrate surface. The films also displayed dielectric breakdown strengths similar to thermally deposited SiO 2 films. The ability to deposit conformal SiO 2 thin films with atomic layer control over a wide range of temperatures should find numerous applications in thin film device fabrication.
UNCOMMON HAND TUMOURS
Authors: Wong C. H. , Chow L. , Yen C. H. , Ho P. C. , Yip R. , Hung L. K.
Published: July 2002

This paper presented clinical examples of some rare or uncommon presentations of tumours of the hand, including glomus tumour, intraosseous dermoid, fibrolipoma of the radial nerve, blastomycotic cyst and synovial sarcoma. Each lesion is illustrated by review of case histories, radiological and pathological features.
SURGICAL TREATMENT OF POSTERIOR INTEROSSEOUS NERVE SYNDROME
Authors: Hou Sheng-Mou , Wang Jyh-Horng , Sun Jui-Sheng
Published: July 2002

Sixteen patients were operated on consecutively for palsy of the posterior interosseous nerve. The aetiologies were traumatic in 12 patients and non-traumatic in four. Operative neurolysis was done in six cases. Neurorrhaphy with sural nerve grafting was performed in two cases. Tendon transfer was done in eight cases. Relief of compression has the best result followed by nerve repair. Iatrogenic nerve injury after radial plating carried the worst prognosis. Although motor power was not normal after surgery, tendon transfer still provided a useful hand with residual extension lag of the fingers. The prognosis of operative treatment of posterior interosseous nerve syndrome depends mainly on its aetiology.
COMBINING DOCUMENT REPRESENTATIONS
Authors: LALMAS MOUNIA
Published: July 2002

This paper presents a formal framework for the combination of document representations based on evidential reasoning. Each indexing method is modelled by an agent referred to as an indexer. Indexing elements re modelled as sentences which are used to describe the content of a document. The modelling of the indexing and its uncertainty provides the document representation. The combination of document representations is expressed as the combination of the indexing and uncertainty as provided by two or more indexers. The resulting indexer is referred to as the combined indexer. The proposed framework allows the capture of the semantics of the indexing vocabularies associated with the indexers and the aggregation of the uncertainty associated with the indexing.
PORTFOLIO THEORY FOR "FAT TAILS"
Authors: SORNETTE D. , ANDERSEN J. V. , SIMONETTI P.
Published: July 2002

We introduce a faithful representation of the heavy tail multivariate distribution of asset returns, as parsimonious as the Gaussian framework. Using calculation techniques of functional integration and Feynman diagrams borrowed from particle physics, we characterize precisely, through its cumulants of high order, the distribution of wealth variations of a portfolio composed of an arbitrary mixture of assets. This approach makes quantitative and rigorous the well-known fact that minimizing the variance, i.e. the relatively "small" risks, often increases larger risks as measured by higher normalized cumulants and the Value-at-Risk.
LEARNING SHORT-OPTION VALUATION IN THE PRESENCE OF RARE EVENTS
Authors: RABERTO M. , CUNIBERTI G. , RIANI M. , SCALES E. , MAINARDI F. , SERVIZI G.
Published: July 2002

We extend the neural-network approach for the valution of financial derivatives developed by Hutchinson et al. [1] to the case of fat-tailed distributions of the underlying asset returns. We use a two-layer perceptron with three inputs, four hidden neurons, and one output. The input parameters of the network are: the simulated price of the underlying asset F divided by the strike price E, the time-to-maturity T, and the ratio |F-E|/T. The latter takes into account the volatility smile, whereas the price F is generated by the method of Gorenflo et al. [2] based on fractional calculus. The output parameter is the call price C over E. The learning-set option price C is computed by means of a formula given by Bouchaud and Potters [3, 4]. Option prices obtained by means of this learning scheme are compared with LIFFE option prices on German treasury bond (BUND) futures.
SPLITTING OF POISSON NOISE AND LÉVY PROCESSES ON REAL LIE ALGEBRAS
Authors: PRIVAULT NICOLAS
Published: July 2002

The compensated Poisson noise is expressed as a composite sum (splitting) of creation and annihilation operators, whose probabilistic interpretation relies on time changes. We construct an Itô table for this decomposition and obtain continuous and discrete time realizations of Lévy processes on the finite difference algebra [Formula: see text] and on [Formula: see text], e.g. the space–time dual of the Poisson process (compensated gamma process), and the continuous binomial process.
COLLECTING INFORMATION TO IMPROVE DECISION-MAKING
Authors: BRÂNZEI RODICA , TIJS STEF , TIMMER JUDITH
Published: July 2002

In this paper, we consider information collecting (IC) situations where an action taker in an uncertain situation can improve his action choices by gathering information from some players who are more informed about the situation. Then the problem of sharing the gains when cooperating with informants is tackled by constructing an appropriate game, the IC-game corresponding to the IC-situation. It turns out that the cone of IC-games, given a fixed set of players, coincides with the cone of 0-normalized monotonic games with a veto player. Also special classes of convex IC-games and big boss IC-games are considered, for which more is known about the solution concepts.
NONLINEAR SCHRÖDINGER EQUATIONS WITH STEEP POTENTIAL WELL
Authors: BARTSCH THOMAS , PANKOV ALEXANDER , WANG ZHI-QIANG
Published: July 2002

We investigate nonlinear Schrödinger equations like the model equation [Formula: see text] where the potential Vλ has a potential well with bottom independent of the parameter λ > 0. If λ → ∞ the infimum of the essential spectrum of -Δ + Vλ in L2(ℝN) converges towards ∞ and more and more eigenvalues appear below the essential spectrum. We show that as λ→∞ more and more solutions of the nonlinear Schrödinger equation exist. The solutions lie in H1(ℝN) and are localized near the bottom of the potential well, but not near local minima of the potential. We also investigate the decay rate of the solutions as |x|→∞ as well as their behaviour as λ→∞.
WHEN SELF-INJECTIVE RINGS ARE QF: A REPORT ON A PROBLEM
Authors: FAITH CARL , VAN HUYNH DINH
Published: July 2002

Theorems of Osofsky and Kato imply that a right and left self-injective one-sided perfect ring is quasi-Frobenius (= QF). The corresponding question for one-sided self-injective one or two-sided perfect rings remains open, even assuming that the ring is semiprimary. The latter version of the problem is known as Faith's Conjecture (FC). We survey results on QF rings, especially those obtained in connection with FC. We also review various results that provide partial answers to another problem of Faith: Is a right FGF ring necessarily QF? On this topic, we provide a new result, namely that if all factor rings of R are right FGF, then R is QF (Theorem 6.1). In Sec. 7 we review results concerning the question of when a D-ring is QF. Sections 8 and 9 are devoted respectively to IF rings, and to Σ-injective rings and Σ-CS rings.
Upper and lower bounds on switching energy in VLSI
Authors: Kissin Gloria
Published: July 2002

A technology-independent framework is established for measuring the
switching energy
consumed by very large scale integrated (VLSI) circuits. Techniques are developed for analyzing functional energy consumption, and for designing energy-efficient VLSI circuits. A wire (or gate) in a circuit uses switching energy when it changes state from 1 to 0 or vice versa. This paper develops the
Uniswitch Model (USM)
of energy consumption, which measures the differences between pairs of states of an embedded circuit.…—
From the Author's Abstract
Implementing a random number package with splitting facilities
Authors: L'Ecuyer Pierre , Côté Serge
Published: July 2002

A portable set of software tools is described for uniform random variates generation. It provides for multiple generators running simultaneously, and each generator has its sequence of numbers partitioned into many long (disjoint) substreams. Simple procedure calls allow the user to make any generator “jump” ahead to the beginning of its next substream, back to the beginning of its current substream, or back to the beginning of its first substream.… Implementation issues are discussed.…A Pascal implementation for 32-bit computers is described. —
From the Authors' Abstract
Dynamic adaptation of real-time software
Authors: Bihari Thomas E. , Schwan Karsten
Published: July 2002

In large, dynamic, real-time computer systems, it is frequently most cost effective to employ different software performance and reliability techniques at different levels of granularity, at different times, or within different subsystems. These techniques may include regulation of redundancy and resource allocation, multiversion and multipath execution, adjustments of program attributes such as time-out periods and others.

The management of software in such systems is a difficult task. Software that may be adapted to meet varying performance and reliability requirements offers a solution. A REal-time Software Adaptation System (RESAS) includes a uniform model of adaptable software and provides the tool necessary for programmers to implement algorithms that choose and enact adaptations in real time.

RESAS has been implemented on a testbed consisting of a multiprocessor and an attached workstation, and adaptation algorithms have been developed that address the problem of adapting software to achieve two goals: software execution within specified time constraints and software resiliency with respect to computer hardware failures.
Exploiting parallelism in pattern matching
Authors: Mak Victor Wing-Kit , Lee Kuo Chu , Frieder Ophir
Published: July 2002

We propose a document-searching architecture based on high-speed hardware pattern matching to increase the throughput of an information retrieval system. We also propose a new parallel VLSI pattern-matching algorithm called the Data Parallel Pattern Matching (DPPM) algorithm, which serially broadcasts and compares the pattern to a block of data in parallel. The DPPM algorithm utilizes the high degree of integration of VLSI technology to attain very high-speed processing through parallelism. Performance of the DPPM has been evaluated both analytically and by simulation. Based on the simulation statistics and timing analysis on the hardware design, a search rate of multiple gigabytes per second is achievable using 2-μm CMOS technology. The potential performance of the proposed document-searching architecture is also analyzed using the simulation statistics of the DPPM algorithm.
ARIES
Authors: Mohan C. , Haderle Don , Lindsay Bruce , Pirahesh Hamid , Schwarz Peter
Published: July 2002

DB2
TM
, IMS, and Tandem
TM
systems. ARIES is applicable not only to database management systems but also to persistent object-oriented languages, recoverable file systems and transaction-based operating systems. ARIES has been implemented, to varying degrees, in IBM's OS/2
TM
Extended Edition Database Manager, DB2, Workstation Data Save Facility/VM, Starburst and QuickSilver, and in the University of Wisconsin's EXODUS and Gamma database machine.
Estimating subdivision depths for rational curves and surfaces
Authors: Cheng Fuhua
Published: July 2002

An algorithm to estimate subdivision depths for rational curves and surfaces is presented. The subdivision depth is not estimated for the given curve/surface directly. The algorithm computes a subdivision depth for the polynomial curve/surface of which the given rational curve/surface is the image under the standard perspective projection. This subdivision depth, however, guarantees the required flatness of the given curve/surface after the subdivision. This work has applications in surface rendering, surface/surface intersection, and mesh generation.
Algorithm 705; a FORTRAN-77 software package for solving the Sylvester matrix equation AXB

T

+ CXD

T

= E
Authors: Gardiner Judith D. , Wette Matthew R. , Laub Alan J. , Amato James J. , Moler Cleve B.
Published: July 2002

This paper documents a software package for solving the Sylvester matrix equation (1)

AXB
T

+

CXD
T

=
e

All quantities are real matrices;
A
and
C
are
m
x
n
;
B
and
D
are
m
x
n
; and
X
and
E
are
m
x
n
. The unknown is
X
. Two symmetric forms of Eq. (1) are treated separately for efficiency. They are the continuous-time symmetric Sylvester equation (2)

AXE
T

+

EXA
T

+
C
= 0 and the discrete time equation (3)

AXA
T

+
C
= 0, for which
A
,
E
, and
C
is symmetric. The software also provides a means for estimating the condition number of these three equations. The algorithms employed are more fully described in an accompanying paper [3].
Coordinating rule-based software processes with ESP
Authors: Ciancarini Paolo
Published: July 2002

ESP is a language for modeling rule-based software processes that take place in a distributed software development environment. It is based on PoliS, an abstract coordination model that relies on Multiple Tuple Spaces, i.e., collections of tuples a la Linda. PoliS extends Linda aiming at the specification and coordination of logically distributed systems. ESP (Extended Shared Prolog) combines the PoliS mechanisms to deal with concurrency and distribution, with the logic-programming language Prolog, to deal with rules and deduction. Such a combination of a coordination model and a logic language provides a powerful framework in which experiments about rule-based software process programming can be performed and evaluated.
Preference-based decision making for cooperative knowledge-based systems
Authors: Wong Stephen T. C.
Published: July 2002

Recent advances in cooperative knowledge-based systems (CKBS) offer significant promise for intelligent interaction between multiple AI systems for solving larger, more complex problems. In this paper, we propose a logical, qualitative problem-solving scheme for CKBS that uses social choice theory as a formal basis for making joint decisions and promoting conflict resolution. This scheme consists of three steps: (1) the selection of decision criteria and competing alternatives, (2) the formation of preference profiles and collective choices, and (3) the negotiation among agents as conflicts arise in group decision making. In this paper, we focus on the computational mechanisms developed to support steps (2) and (3) of the scheme. In addition, the practicality of the scheme is illustrated with examples taken from a working prototype dealing with collaborative structural design of buildings.
Inverse kinematics positioning using nonlinear programming for highly articulated figures
Authors: Zhao Jianmin , Badler Norman I.
Published: July 2002

An articulated figure is often modeled as a set of rigid segments connected with joints. Its configuration can be altered by varying the joint angles. Although it is straight forward to compute figure configurations given joint angles (forward kinematics), it is more difficult to find the joint angles for a desired configuration (inverse kinematics). Since the inverse kinematics problem is of special importance to an animator wishing to set a figure to a posture satisfying a set of positioning constraints, researchers have proposed several different approaches. However, when we try to follow these approaches in an interactive animation system where the object on which to operate is as highly articulated as a realistic human figure, they fail in either generality or performance. So, we approach this problem through nonlinear programming techniques. It has been successfully used since 1988 in the spatial constraint system within
Jack
, a human figure simulation system developed at the University of Pennsylvania, and proves to be satisfactorily efficient, controllable, and robust. A spatial constraint in our system involves two parts: one constraint on the figure, the
end-effector
, and one on the spatial environment, the
goal
. These two parts are dealt with separately, so that we can achieve a neat modular implementation. Constraints can be added one at a time with appropriate weights designating the importance of this constraint relative to the others and are always solved as a group. If physical limits prevent satisfaction of all the constraints, the system stops with the (possibly local) optimal solution for the given weights. Also, the rigidity of each joint angle can be controlled, which is useful for redundant degrees of freedom.
Compiler transformations for high-performance computing
Authors: Bacon David F. , Graham Susan L. , Sharp Oliver J.
Published: July 2002

In the last three decades a large number of compiler transformations for optimizing programs have been implemented. Most optimizations for uniprocessors reduce the number of instructions executed by the program using transformations based on the analysis of scalar quantities and data-flow techniques. In contrast, optimizations for high-performance superscalar, vector, and parallel processors maximize parallelism and memory locality with transformations that rely on tracking the properties of arrays using loop dependence analysis.

This survey is a comprehensive overview of the important high-level program restructuring techniques for imperative languages, such as C and Fortran. Transformations for both sequential and various types of parallel architectures are covered in depth. We describe the purpose of each transformation, explain how to determine if it is legal, and give an example of its application.

Programmers wishing to enhance the performance of their code can use this survey to improve their understanding of the optimizations that compilers can perform, or as a reference for techniques to be applied manually. Students can obtain an overview of optimizing compiler technology. Compiler writers can use this survey as a reference for most of the important optimizations developed to date, and as bibliographic reference for the details of each optimization. Readers are expected to be familiar with modern computer architecture and basic program compilation techniques.
Succeeding as a clandestine change agent
Authors: Allen C. Dennis
Published: July 2002

Changing the attitudes and work habits of a large organization is daunting at best. The task is more challenging when the organization perceives itself as eminently successful, dominating the market in its category. During the past 5 years I've seen the evolution of the product design processes as I moved from user-interface (UI) designer, to manager of a large UI design group, to my current position as a product design strategist.
UC Berkeley's Digital Library project
Authors: Wilensky Robert
Published: July 2002

For digital libraries to succeed, we must abandon the traditional notion of “library” altogether. The reason is as follows: The digital “library” will be a collection of distributed information services; producers of material will make it available, and consumers will find it and use it, perhaps through the help of automated agents. Libraries in the traditional sense are nowhere to be found in this model (i. e., the notion of a limited intermediary containing some small fraction of preselected material available only to local patrons is replaced by a system providing to users everywhere direct access to the full contents of all available material).
Library of Congress Digital Library effort
Authors: Becker Herbert S.
Published: July 2002

The Library of Congress has been actively seeking gift funds to continue the digitization efforts begun five years ago by its American Memory pilot project, which has successfully digitized more than 210,000 items. Many of these items have been made available to 44 test sites around the United States, and selected items from this project are also available via the Library of Congress's World-Wide Web server (http://www.loc.gov). Last October, the library received a total of $13 million in grant and gift funds to digitize its American historical collections, many of which are unique, and to help it identify instructional uses of digitized library materials.
Translating default logic into standard autoepistemic logic
Authors: Gottlob Georg
Published: July 2002

Since Konolige's translation of default logic into strongly grounded autoepistemic logic, several other variants of Moore's original autoepistemic logic that embody default logic have been studied. All these logics differ significantly from Moore's autoepistemic logic (standard AEL) in that expansions are subject to additional groundedness-conditions. Hence, the question naturally arises whether default logic can be translated into standard AEL at all. We show that a modular translation is not possible. However, we are able to construct a faithful polynomial-time translation from default logic into standard AEL, which is nonmodular. Our translation exploits the self-referentiality of AEL. It uses as an important intermediate step an embedding of Marek's and Truszczyn´ski's nonmonotonic logic
N
into standard AEL. It follows from our results that the expressive power of standard AEL is strictly greater than that of default logic.
A constant-time optimal parallel string-matching algorithm
Authors: Galil Zvi
Published: July 2002

Given a pattern string, we describe a way to preprocess it. We design a CRCW-PRAM constant time optimal parallel algorithm for finding all occurrences of the (preprocessed) pattern in any given text.
Embedded video in hypermedia documents
Authors: Bulterman Dick C. A.
Published: July 2002

As the availability of digital video becomes commonplace, a shift in application focus will occur from merely
accessing
video as an independent data stream to
embedding
video with other multimedia data types into coordinated hypermedia presentations. The migration to embedded video will present new demands on application and support environments: processing of any one piece of video data will depend on how that data relates to other data streams active within the same presentation. This article describes presentation, synchronization, and interaction control issues for manipulating embedded video. First we describe the requirements for embedded video, contrasted against other forms of video use. Next we consider mechanisms for describing and implementing the behavior of embedded-video segments relative to other data items in a document; these relationships form the basis of implementing cooperative control among the events in a presentation. Finally we consider extending the possibilities for tailoring embedded video to the characteristics of the local runtime environment; this forms the basis for adaptive, application-level quality-of-service control of a presentation. In all cases, we describe a mechanism to externalize the behavior of hypermedia presentations containing resource-intensive data requirements so that effective control can be implemented by low-level system facilities based on application-specific requirements. We present our results in terms of the CMIFed authoring/presentation system.
Properly rounded variable precision square root
Authors: Hull T. E. , Abrham A.
Published: July 2002

The square root function presented here returns a properly rounded approximation to the square root of its argument, or it raises an error condition if the argument is negative.
Properly rounded
means rounded to the nearest, or to nearest even in case of a tie. It is
variable precision
in that it is designed to return a
p
-digit approximation to a
p
-digit argument, for any
p
> 0. (Precision
p
means
p
decimal digits.) The program and the analysis are valid for all
p
> 0, but current implementations place some restrictions on
p
.
Distributed snapshots
Authors: Chandy K. Mani , Lamport Leslie
Published: July 2002

This paper presents an algorithm by which a process in a distributed system determines a global state of the system during a computation. Many problems in distributed systems can be cast in terms of the problem of detecting global states. For instance, the global state detection algorithm helps to solve an important class of problems: stable property detection. A stable property is one that persists: once a stable property becomes true it remains true thereafter. Examples of stable properties are “computation has terminated,” “ the system is deadlocked” and “all tokens in a token ring have disappeared.” The stable property detection problem is that of devising algorithms to detect a given stable property. Global state detection can also be used for checkpointing.
When an advantage is not an advantage
Authors: Zurk Lisa M. , Simons Barbara , Parsons Rebecca , Cohen Dawn
Published: July 2002

Discussion of the merits and shortcomings of affirmative action (AA) has raged at all levels and in many forums and has been the concern of many policymakers, including President Clinton. Notably absent from the discussion is the perception of AA, and the effect of the angry backlash on women and minorities. Recently, the question of whether women enjoy an “unfair advantage” was posted electronically on Systers, a private organization of over 1,800 professional women in the male-dominated field of computing. The 42 responses contained strong personal stories from women at every level of professional growth who had all dealt with the issues of gender bias and AA at each step of the way.
Ethical concepts and information technology
Authors: Laudon Kenneth C.
Published: July 2002

The fundamental aspects of classical and contemporary ethics, particularly as they apply to the use of IT, offer valuable lessons of professional conduct.
Reviewing the risks archives
Authors: Neumann Peter G.
Published: July 2002

Ok, you expect your shrink-wrapped software to work properly, without annoying reliability bugs and security holes. Or maybe you would like the systems
you
develop to work properly, without serious risks to their users. But those systems don't quite work the way they are supposed to. So, what's new? Perusal of the Risks archives [1] suggests that startlingly few real success stories are recorded, and that perhaps we might as well just learn to live with almost every system having bugs—some even colossal in scope [2].
Australian attitudes toward legal intervention into hacking
Authors: Coldwell R. A.
Published: July 2002

The Australian public seems to have a characteristic response to computer crime. It is worth giving some anecdotal evidence to support this statement. During fieldwork [1-5], respondents were quizzed regarding their reasoning for their responses to the criminality of hacking. Some results are given here in response to the social attitudes of Australians towards reporting evidence of the enactment of computer crimes (see Table 1). This is in support of Thompson's [12, 13] and others' claims that relatively few computer crimes are, indeed, reported to the police in Australia (see also [9]).
Computerized performance monitors as multidimensional systems
Authors: Grant Rebecca A. , Higgins Chris A.
Published: July 2002

An increasing number of companies are introducing computer technology into more aspects of work. Effective use of information systems to support office and service work can improve staff productivity, broaden a company's market, or dramatically change its business. It can also increase the extent to which work is computer mediated and thus within the reach of software known as Computerized Performance Monitoring and Control Systems (CPMCSs). Virtually all research has studied CPMCSs as unidimensional systems. Employees are described as “monitored” or “unmonitored” or as subject to “high,” “moderate,” or “low” levels of monitoring. Research that does not clearly distinguish among possible monitor design cannot explain how designs may differ in effect. Nor can it suggest how to design better monitors. A multidimensional view of CPMCSs describes monitor designs in terms of object of measurements, tasks measured, recipient of data, reporting period, and message content. This view is derived from literature in control systems, organizational behavior, and management information systems. The multidimensional view can then be incorporated into causal models to explain contradictory results of earlier CPMCS research.
Why Smalltalk?
Authors: Goldberg Adele
Published: July 2002

Smalltalk is a single paradigm language with very simple semantics and syntax for specifying elements of a system and for describing system dynamics [1]. When the language is used to describe an application system, the developer extends Smalltalk, creating a domain-specific language by adding a new vocabulary of language elements while maintaining the same semantics and syntax. Using most Smalltalk systems, it is easy to invent one's own development environment through inclusion of new system parts in the library and extension of the development tools. Moreover, it is possible to make changes to the environment, and to applications written using the environment, while the system is executing. These system characteristics create a flexible and enjoyable software development experience.
Smalltalk reaches crossroads in the insurance industry
Authors: Adamczyk Jim
Published: July 2002

Information systems are critical to the worldwide insurance business, yet few major insurance companies believe they are well served by their current systems. Increasingly, companies are including Smalltalk as a strategic element of their future systems strategies.
Ubiquitous applications
Authors: Thomas Dave
Published: July 2002

Over the last 10 years, Smalltalk has moved from the “Parc” to Main Street as a standard object-oriented (OO) fifth generation language (5GL) for enterprise computing. To meet the needs of application developers, Smalltalk environments and tools have matured from the original research implementations to full-featured, multiplatform development environments. A recent study of development tools conducted by Software Productivity Research in Massachusetts for a software productivity consortium ranked Smalltalk first in most categories. What is surprising about this study is the application: a demanding telephone switch traditionally dominated by C or proprietary talc languages such as Chill, Protel, and Plex. The fact that Smalltalk ranked so highly is a testimony that Smalltalk is an application 5GL that scales. This article discusses the major technical challenges addressed by Smalltalk implementors and application developers working on a wide spectrum of applications.
Register estimation in unscheduled dataflow graphs
Authors: Moreno R. , Hermida R. , Fernández M.
Published: July 2002

A method for register number estimation in unscheduled or partially scheduled dataflow graphs is presented. The strategy consists of studying the probability that an edge between two nodes crosses the boundary between two control steps, and its is based on a model that associates probabilities with the different scheduling alternatives of each node. These probabilities are computed by means of an analytic method that takes into account the distribution of operations in the dataflow graph and the hardware modules available in the library. The results highlight that the estimation method is very accurate becaused the error between the estimated value and the real value is always within a narrow margin.
Semantics for update rule programs and implementation in a relational database management system
Authors: Raschid Louiqa , Lobo Jorge
Published: July 2002

In this paper, we present our research on defining a correct semantics for a class of update rule (UR) programs, and discuss implemanting these programs in a DBMS environment. Update rules execute by updating relations in a database which may cause the further execution of rules. A correct semantics must guarantee that the execution of the rules will terminate and that it will produce a minimal updated database. The class of UR programs is syntactically identified, based upon a concept that is similar to stratification. We extend that strict definition of stratification and allow a relaxed criterion for partitioning of the rules in the UR program. This relaxation allows a limited degree of nondeterminism in rule execution. We define an execution semantics based upon a monotonic fixpoint operator T
UR
, resulting in a set of fixpoints for UR. The monotionicity of the operator is maintained nby explicitly representing the effect of asserting and retracting tuples in the database. A declarative semantics for the update rule program is obtained by associating a normal logic program UR to represent the UR program. We use the stable model semantics which characterize a normal logic program by a set of minimal models which are called stable models. We show the equivalence between the set of fixpoints for UR and the set of stable models for UR. We briefly discuss implementing the fixpoint semantics of the UR program in a DBMS environment. Relations that can be updated by the rules are
updatable
relations and they are extended with two flags. An update rule is represented by a database query, which queries the updatable relations as well as database relaions, i.e., those relations which are not update by rules. We describe an algorithm to process the queries and compute a fixpoint in the DBMS environment and obtain a final database.
The Unison algorithm
Authors: Sosič Rok , Gu Jun , Johnson Robert R.
Published: July 2002

We present a Unison algorithm to evaluate arbitrarily complex Boolean expressions. This novel algorithm, based on the total differential of a Boolean function, enables fast evaluation of Boolean expressions in software. Any combination of Boolean operations can be packed into the bits of one computer word and evaluated in parallel by bitwise logical operations. Sample runs of the Unison algorithm show that many Boolean operations can evaluated in one clock cycle. The Unison algorithm is able to evaluate Boolean expressions at an execution speed that is comparable to compiled evaluation while retaining the flexibility of interpreted approaches. The algorithm lends itself well to many practical applications.
Rectilinear Steiner trees on a checkerboard
Authors: Ganley Joseph L. , Cohoon James P.
Published: July 2002

The rectilinear Steiner tree problem is to find a minimum-length set of horizontal and vertical line segments that interconnect a given set of points in the plane. Here we study the
thumbnail rectilinear Steiner tree
problem, where the input points are drawn from a small integer grid. Specifically, we devise a fully-set decomposition algorithm for computing optimal thumbnail rectilinear Steiner trees. We then present experimental results comparing the performance of this algorithm with two existing algorithms for computing optimal rectilinear Steiner trees. The thumbnail rectilinear Steiner tree problem has applications in VLSI placement algorithms, based on geometric partitioning, global routing of field-programmable gate arrays, and routing estimation during floorplanning.
Hyperform
Authors: Wiil Uffe K. , Leggett John J.
Published: July 2002

Development of hypermedia systems is a complex matter. The current trend toward open, extensible, and distributed multiuser hypermedia systems adds additional complexity to the development process. As a means of reducing this complexity, there has been an increasing interest in hyperbase management systems that allow hypermedia system developers to abstract from the intricacies and complexity of the hyperbase layer and fully attend to application and user interface issues. Design, development, and deployment experiences of a dynamic, open, and distributed multiuser hypermedia system development environment called Hyperform is presented. Hyperform is based on the concepts of extensibility, tailorability, and rapid prototyping of hypermedia system services. Open, extensible hyperbase management systems permit hypermedia system developers to tailor hypermedia functionality for specific applications and to serve as a platform for research. The Hyperform development environment is comprised of multiple instances of four component types: (1) a hyperbase management system server, (2) a tool integrator, (3) editors, and (4) participating tools. Hyperform has been deployed in Unix environments, and experiments have shown that Hyperform greatly reduces the effort required to provide customized hyperbase management system support for distributed multiuser hypermedia systems.
Area and performance tradeoffs in floating-point divide and square-root implementations
Authors: Soderquist Peter , Leeser Miriam
Published: July 2002

Floating-point divide and square-root operations are essential to many scientific and engineering applications, and are required in all computer systems that support the IEEE floating-point standard. Yet many current microprocessors provide only weak support for these operations. The latency and throughput of division are typically far inferior to those of floating-point addition and multiplication, and square-root performance is often even lower. This article argues the case for high-performance division and square root. It also explains the algorithms and implementations of the primary techniques, subtractive and multiplicative methods, employed in microprocessor floating-point units with their associated area/performance tradeoffs. Case studies of representative floating-point unit configurations are presented, supported by simulation results using a carefully selected benchmark, Givens rotation, to show the dynamic performance impact of the various implementation alternatives. The topology of the implementation is found to be an important performance factor. Multiplicative algorithms, such as the Newton-Raphson method and Goldschmidt's algorithm, can achieve low latencies. However, these implementations serialize multiply, divide, and square root operations through a single pipeline, which can lead to low throughput. While this hardware sharing yields low size requirements for baseline implementations, lower-latency versions require many times more area. For these reasons, multiplicative implementations are best suited to cases where subtractive methods are precluded by area constraints, and modest performance on divide and square root operations is tolerable. Subtractive algorithms, exemplified by radix-4 SRT and radix-16 SRT, can be made to execute in parallel with other floating-point operations.
Verification techniques for cache coherence protocols
Authors: Pong Fong , Dubois Michel
Published: July 2002

In this article we present a comprehensive survey of various approaches for the verification of cache coherence protocols based on
state enumeration, (symbolic model checking
, and
symbolic state models
. Since these techniques search the state space of the protocol exhaustively, the amount of memory required to manipulate that state information and the verification time grow very fast with the number of processors and the complexity of the protocol mechanisms. To be successful for systems of arbitrary complexity, a verification technique must solve this so-called
state space explosion
problem. The emphasis of our discussion is onthe underlying theory in each method of handling the state space exposion problem, and formulationg and checking the
safety
properties (e.g., data consistency) and the
liveness
properties (absence of deadlock and livelock). We compare the efficiency and discuss the limitations of each technique in terms of memory and computation time. Also, we discuss issues of
generality, applicability, automaticity, and amenity
for existing tools in each class of methods. No method is truly superior because each method has its own strengths and weaknesses. Finally, refinements that can further reduce the verification time and/or the memory requirement are also discussed.
A comparative study of parallel and sequential priority queue algorithms
Authors: Rönngren Robert , Ayani Rassul
Published: July 2002

Priority queues are used in many applications including real-time systems, operating systems, and simulations. Their implementation may have a profound effect on the performance of such applications. In this article, we study the performance of well-known sequential priority queue implementations and the recently proposed parallel access priority queues. To accurately assess the performance of a priority queue, the performance measurement methodology must be appropriate. We use the Classic Hold, the Markov Model, and an Up/Down access pattern to measure performance and look at both the average access time and the worst-case time that are of vital interest to real-tiem applicatons. Our results suggest that the best choice for priority queue algorithms depends heavily on the application. For queue sizes smaller than 1,000 elements, the Splay Tree, the Skew Heap, and Henriksen's algorithm show good average access times. For large queue sized of 5,000 elements or more, the Calendar Queue and the Lazy Queue offer good average access times but have very long worst-case access times. The Skew Heap and the splay Tree exhibit the best worst-case access times. Among the parallel access priority queues tested, the Parallel Access Skew Heap provides the best performance on small shares memory multiprocessors.
Device reservation in audio/video editing systems
Authors: Anderson David P.
Published: July 2002

What fraction of disks and other shared devices must be reserved to play an audio/video document without dropouts? In general, this question cannot be answered precisely. For documents with complex and irregular structure, such as those arising in audio/video editing, it is difficult even to give a good estimate. We describe three approaches to this problem. The first, based on long-term average properties of segments, is fast but imprecise: it underreserves in some cases and overreserves in others. The second approach models individual disk and network operations. It is precise but slow. The third approach, a hybrid, is both precise and fast.