bluuebunny/crossref_metadata_2025 huggingface dataset:
EXPERIMENTAL OBSERVATION OF INTERMITTENCY IN COUPLED CHAOTIC PENDULUMS
Authors: SMITH H. J. T. , BLACKBURN JAMES A. , BAKER GREGORY L.
Published: July 2002

We have experimentally realized on–off intermittency in a pair of mutually coupled damped driven pendula. The pendula interacted bidirectionally via a torque which was proportional to the difference in their angular velocities. Experimental data show that the intervals of synchronized chaotic motion are distributed in agreement with the theory for on–off intermittency: The conditional probability of short laminar times is found to follow a power law whilst the conditional probability of long laminar times follows the expected exponential law. The experimental data also reveal that the intermittent properties vary with the coupling strength, and that the average laminar time inferred from the results depends on the choice of threshold level.
COHERENCE AND SYNCHRONIZATION IN DIODE-LASER ARRAYS WITH DELAYED GLOBAL COUPLING
Authors: GARCÍA-OJALVO JORDI , CASADEMONT JOAN , TORRENT M. C. , MIRASSO CLAUDIO R. , SANCHO J. M.
Published: July 2002

The dynamics of a semiconductor-laser array whose individual elements are coupled in a global way through an external mirror is numerically analyzed. A coherent in-phase solution is seen to be preferred by the system at intermediate values of the feedback-coupling strength. At low values of this parameter, a strong amplification of the spontaneous emission noise is observed. A tendency towards chaos synchronization is also observed at large values of the feedback strength.
RIGIDITY PROPERTIES OF DIAGRAM GROUPS
Authors: GUBA V. S. , SAPIR M. V.
Published: July 2002

In this paper we establish a rigid connection between two classical objects: the R. Thompson group F and the Dunce hat (the topological space obtained from the triangle ABC by gluing AB, BC, and AC). We prove that a diagram group of a directed 2-complex contains a copy of the R. Thompson group if and only if the 2-complex contains a copy of the Dunce hat.
ON THE COLENGTH OF A VARIETY OF LIE ALGEBRAS
Authors: GIAMBRUNO A. , MISHCHENKO S. , ZAICEV M.
Published: July 2002

We study the variety of Lie algebras defined by the identity [Formula: see text] over a field of characteristic zero. We prove that, as in the associative case, in the nth cocharacter χn of this variety, every irreducible Sn-character appears with polynomially bounded multiplicity (not greater than n2). Anyway, surprisingly enough, we also show that the colength of this variety, i.e. the total number of irreducibles appearing in χn is asymptotically equal to [Formula: see text].
STEADY FLOW OF A NON-NEWTONIAN FLUID IN UNBOUNDED CHANNELS AND PIPES
Authors: MARUŠIĆ-PALOKA EDUARD
Published: July 2002

We study the steady flow of a dilatant non-Newtonian fluid obeying the power law in unbounded channels and pipes. The proof of existence and uniqueness of the solution for the Leray's problem for such fluid is given as well as the decay estimate for the solution.
UNDERSTANDING GESTURES IN MULTIMODAL HUMAN COMPUTER INTERACTION
Authors: KETTEBEKOV SANSHZAR , SHARMA RAJEEV
Published: July 2002

In recent years because of the advances in computer vision research, free hand gestures have been explored as a means of human-computer interaction (HCI). Gestures in combination with speech can be an important step toward natural, multimodal HCI. However, interpretation of gestures in a multimodal setting can be a particularly challenging problem. In this paper, we propose an approach for studying multimodal HCI in the context of a computerized map. An implemented testbed allows us to conduct user studies and address issues toward understanding of hand gestures in a multimodal computer interface.

Absence of an adequate gesture classification in HCI makes gesture interpretation difficult. We formalize a method for bootstrapping the interpretation process by a semantic classification of gesture primitives in HCI context. We distinguish two main categories of gesture classes based on their spatio-temporal deixis. Results of user studies revealed that gesture primitives, originally extracted from weather map narration, form patterns of co-occurrence with speech parts in association with their meaning in a visual display control system. The results of these studies indicated two levels of gesture meaning: individual stroke and motion complex. These findings define a direction in approaching interpretation in natural gesture-speech interfaces.
HOMFLY POLYNOMIALS OF ITERATIVE FAMILIES OF LINKS
Authors: CHAN TAT-HUNG
Published: July 2002

We show that if a family of oriented links obey an iterative pattern, their HOMFLY polynomials satisfy a homogeneous linear recurrence relation. The construction embodied in the proof is applied to derive explicit formulas for the HOMFLY polynomials of some iterative families, including the torus links {Tn,3}n≥0.
VACUUM BRANS–DICKE THEORY AND WORMHOLES
Authors: CHAKRABORTY SUBENOY
Published: July 2002

This paper deals with vacuum Brans–Dicke theory in an anisotropic Kantowski–Sachs model and Euclidean wormhole solutions have been obtained. The Wheeler–Dewitt (WD) equation has been solved using separable form of the wave function and these solutions have been examined whether wormhole boundary condition due to Hawking is satisfied or not.
SUPERHEAVY PARTICLES IN FRIEDMANN COSMOLOGY AND THE DARK MATTER PROBLEM
Authors: GRIB A. A. , PAVLOV YU. V.
Published: July 2002

The model of creation of observable particles and particles of the dark matter, considered to be superheavy particles, due to particle creation by the gravitational field of the Friedmann model of the early Universe is given. Estimates on the parameters of the model leading to observable values of the baryon number of the Universe and the dark matter density are made.
STUDIES OF SUPERDENSE HADRONIC MATTER IN A RELATIVISTIC TRANSPORT MODEL
Authors: LI BAO-AN , SUSTICH A. T. , ZHANG BIN , KO C. M.
Published: July 2002

Transport models have been very useful in studying the properties of the hot, dense matter that is created in relativistic heavy-ion collisions. We review here a Relativistic Transport (ART) Model and its applications in heavy ion collisions at beam energies below about 10 AGeV available from the Alternating Gradient Synchrotron at Brookhaven National Laboratory. The model allows one to study not only the reaction dynamics leading to the formation of superdense hadronic matter, but also to explore the effects due to the nuclear equation of state and the deformation/orientation of the colliding nuclei on the size and lifetime of the superdense matter. We also discuss the dependence of the central baryon and energy densities, the degree of thermalization, and the collective radial flow velocity of the superdense matter on the beam energy. We further review how the properties of the superdense hadronic matter can be determined from studying the collective flow of nucleons, pions and kaons in these collisions. We finally discuss the mechanisms for kaon production in relativistic heavy-ion collisions and review the progress in extracting the kaon in-medium properties from these collisions.
INFLUENCE OF GEOMETRIC AND ENERGETIC HETEROGENEITY ON ADSORPTION ISOTHERMS
Authors: GIONA MASSIMILIANO , GIUSTINIANI MANUELA , LUDLOW DOUGLAS K.
Published: July 2002

The relationships between geometric roughness and energetic heterogeneity are discussed by considering a thermodynamically consistent model of adsorption isotherms (Keller model) which encompasses fractal scaling and the dependence of the adsorption energies on the coverage. Experimental results validate this model and indicate that it can be used not only to interpolate experimental data but also to predict adsorption equilibria of multicomponent rnixtures. The peculiar non-Henry behaviour of the Keller model at low pressure is discussed by considering a simple model of preferential adsorption on a rough energy landscape and including the effect of surface diffusion.
A FACTORIZED REPRESENTATION OF INDEPENDENCE OF CAUSAL INFLUENCE AND LAZY PROPAGATION
Authors: MADSEN ANDERS L. , D'AMBROSIO BRUCE
Published: July 2002

The efficiency of algorithms for probabilistic inference in Bayesian networks can be improved by exploiting independence of causal influence. The factorized representation of independence of causal influence offers a factorized decomposition of certain independence of causal influence models. We describe how LAZY propagation - a junction tree based inference algorithm - easily can be extended to take advantage of the decomposition offered by the factorized representation. We introduce two extensions to the factorized representation easing the knowledge acquisition task and reducing the space complexity of the representation exponentially in the state space size of the effect variable of an independence of causal influence model. We describe how the factorized representation can be used to solve tasks such as calculating the maximum a posteriori hypotheses, the maximum expected utility, and the most probable configuration. Finally, the results of an empirical evaluation indicate that considerable performance improvements can be obtained using LAZY propagation combined with the factorized representation compared to LAZY propagation performed in junction trees constructed after either parent divorcing or temporal transformation have been applied to the Bayesian network.
PROXIMAL INTERPHALANGEAL JOINT SURFACE REPLACEMENT ARTHROPLASTY
Authors: Johnstone Bruce R.
Published: July 2002

A consecutive series of 20 joints in 13 patients underwent arthroplasty with the RMS PIP joint surface replacement implant. Twelve joints were treated for painful osteoarthritis (all females). Two joints were implanted for rheumatoid arthritis, two for post-traumatic pain and stiffness, two for post-traumatic stiffness and one each for post-traumatic pain and pain-free post-traumatic instability. Excellent, often total long-term pain relief was obtained in 18 joints. The other two patients with (compensible work-related) post-traumatic pain and stiffness reported "50–70% pain reduction". No patients lost movement and 14 out of 20 joints were pain-free with a 73.1° average arc of motion. Six joints from the first half of the series had poor motion (average arc of 19.6°), even after open extensor tenolysis or manipulation under anaesthesia. As experience was gained, reliably better results were achieved with a more intensive regimen of hand therapy, particularly within the first post-operative week.
A BRIEF REVIEW AND A PROPOSAL FOR THE CLASSIFICATION OF THE CONGENITAL ANOMALIES OF THE UPPER LIMB: My Proposal for the Classification of Congenital Upper Limb Anomalies
Authors: Tajima Tatsuya
Published: July 2002

The evaluation of the international classification of congenital anomalies of the upper limb in the past 25 years is described. Syndactyly, cleft hand, and central polydactyly have the same embryological defect. Triphalangeal thumb and five fingered hand are unclassifiable, while camplodactyly, clinodactyly and haemangioma should not be grouped under “failure of differentiation of parts”. A new approach in classification is suggested.
SQUARES, SCALES AND STATIONARY REFLECTION
Authors: CUMMINGS JAMES , FOREMAN MATTHEW , MAGIDOR MENACHEM
Published: July 2002

Since the work of Gödel and Cohen, which showed that Hilbert's First Problem (the Continuum Hypothesis) was independent of the usual assumptions of mathematics (axiomatized by Zermelo–Fraenkel Set Theory with the Axiom of Choice, ZFC), there have been a myriad of independence results in many areas of mathematics.

These results have led to the systematic study of several combinatorial principles that have proven effective at settling many of the important independent statements. Among the most prominent of these are the principles diamond(♢) and square(□) discovered by Jensen. Simultaneously, attempts have been made to find suitable natural strengthenings of ZFC, primarily by Large Cardinal or Reflection Axioms. These two directions have tension between them in that Jensen's principles, which tend to suggest a rather rigid mathematical universe, are at odds with reflection properties. A third development was the discovery by Shelah of "PCF Theory", a generalization of cardinal arithmetic that is largely determined inside ZFC.

In this paper we consider interactions between these three theories in the context of singular cardinals, focusing on the various implications between square and scales (a fundamental notion in PCF theory), and on consistency results between relatively strong forms of square and stationary set reflection.
KNOT AND LINK INVARIANTS AND MODULI SPACE OF PARABOLIC BUNDLES
Authors: LI WEIPING
Published: July 2002

In this paper, we show that the representation variety of the fundamental group of a 2n-punctured S2 with different conjugacy classes in SU(2) along punctures is a symplectic stratified variety from the group cohomology point of view. The representation variety can be identified with the moduli space of s-equivalence classes of stable parabolic bundles over the 2n-punctured S2 with corresponding weights along punctures, and also can be identified with the moduli space of gauge equivalence classes of SU(2)-flat connections with prescribed holonomies along punctures. We obtain an invariant of links (knots) from intersection theory on such a moduli space (a generalization of the signature of the link). We also study a SL2(C)-character variety of a knot K in S3 with fixed holonomy μ + μ-1 along the meridian of π1(S3\ K) (μ ∈ C*). The fixed-trace condition rules out the possibility of reducible representations with non-abelian image and the ideal point of irreducible representations via a generic perturbation. For knots without closed incompressible surfaces in S3 \ K, we show that there is a well-defined SL2(C)-knot invariant which is also related to them A-polynomial for special values μ ∈ U(1)\ {± 1}.
AN EFFICIENT QUADTREE DATASTRUCTURE FOR NEIGHBOR FINDING ALGORITHM
Authors: KUMAR B. PRAVEEN , GUPTA PHALGUNI , HWANG C. J.
Published: July 2002

In this paper, we have studied the problem of finding the neighbors of a node in a quadtree. We have proposed a variation in the quadtree representation which has helped in finding the neighbors efficiently. We have presented algorithms for construction and maintenance of our quadtree.
REFLEXIVE POLYTOPES IN DIMENSION 2 AND CERTAIN RELATIONS IN SL2(ℤ)
Authors: HILLE LUTZ , SKARKE HARALD
Published: July 2002

It is well known that there are 16 two-dimensional reflexive polytopes up to lattice isomorphism. One can check directly from the list that the number of lattice points on the boundary of such a polytope plus the number of lattice points on the boundary of the dual polytope is always 12. It turns out that two-dimensional reflexive polytopes correspond to certain relations of two generators A and B of SL 2(ℤ) of length 12. We generalize this correspondence to reflexive configurations with winding number w and relations of length 12w.
AUTOMATIC FROG CALLS MONITORING SYSTEM: A MACHINE LEARNING APPROACH
Authors: YEN GARY G. , FU QIANG
Published: July 2002

Automatic recognition of frog vocalization is considered a valuable tool for a variety of biological research and environmental monitoring applications. In this research an automatic monitoring system, which can recognize the vocalizations of four species of frogs and can identify different individuals within the species of interest, is proposed. For the desired monitoring system, species identification is performed first with the proposed filtering and grouping algorithm. Individual identification, which can estimate frog population within the specific species, is performed in the second stage. Digital signal pre-processing, feature extraction, dimensionality reduction, and neural network pattern classification are performed step by step in this stage. Wavelet Packet feature extraction together with two different dimension reduction algorithms are synergistically integrated to produce final feature vectors, which are to be fed into a neural network classifier. The simulation results show the promising future of deploying an array of continuous, on-line environmental monitoring systems based upon nonintrusive analysis of animal calls.
Queries and query processing in object-oriented database systems
Authors: Straube David D. , Özsu M. Tamer
Published: July 2002

Object-oriented database mangement systems (OODBMS) combine the data abstraction and computational models of object-oriented programming languages with the query and performance capabilities of database management systems. A concise, formal data model for OODBMS has not been universally accepted, preventing detailed investigation of various system issues such as query processing. We define a data model that captures the essence of classification-based object-oriented systems and formalize concepts such as object identity, inheritence, and methods. The main topic of the paper is the presentation of a query processing methodology complete with an object calculus to object algebra translation are discussed in detail. The paper concludes with a discussion of equivalence-preserving transformation rules for object algebra expressions.
A rule-based language with functions and sets
Authors: Abiteboul Serge , Grumbach Stéphane
Published: July 2002

A logic based language for manipulating complex objects constructed using set and tuple constructors is introduced. A key feature of the COL language is the use of base and derived data functions. Under some stratification restrictions, the semantics of programs is given by a minimal and justified model that can be computed using a finite sequence of fixpoints. The language is extended using external functions and predicates. An implementation of COL in a functional language is briefly discussed.
The use of Taylor series to test accuracy of function programs
Authors: Cody W. J. , Stoltz L.
Published: July 2002

This paper discusses the use of local Taylor series expansions for determining the accuracy of computer programs for special functions. The main example is testing of programs for exponential integrals. Additional applicaitons include testing of programs for certain Bessel functions, Dawson's integral, and error functions.
Construction of test problems in quadratic bivalent programming
Authors: Pardalos Panos M.
Published: July 2002

A method of constructing test problems for constrained bivalent quadratic programming is presented. For any feasible integer point for a given domain, the method generates quadratic functions whose minimum over the given domain occurs at the selected point.

Certain properties of unconstrained quadratic zero-one programs that determine the difficulty of the test problems are also discussed. In addition, a standardized random test problem generator for unconstrained quadratic zero-one programming is given.
A methodology for hardware verification based on logic simulation
Authors: Bryant Randal E.
Published: July 2002

A logic simulator can prove the correctness of a digital circuit if it can be shown that only circuits fulfilling the system specification will produce a particular response to a sequence of simulation commands.This style of verification has advantages over the other proof methods in being readily automated and requiring less attention on the part of the user to the low-level details of the design. It has advantages over other approaches to simulation in providing more reliable results, often at a comparable cost.

This paper presents the theoretical foundations of several related approaches to circuit verification based on logic simulation. These approaches exploit the three-valued modeling capability found in most logic simulators, where the third-value
X
indicates a signal with unknown digital value. Although the circuit verification problem is NP-hard as measured in the size of the circuit description, several techniques can reduce the simulation complexity to a manageable level for many practical circuits.
A triangulation algorithm from arbitrary shaped multiple planar contours
Authors: Ekoule A. B. , Peyrin F. C. , Odet C. L.
Published: July 2002

Conventional triangulation algorithms from planar contours suffer from some limitations. For instance, incorrect results can be obtained when the contours are not convex, or when the contours in two successive slices are very different. In the same way, the presence of multiple contours in a slice leads to ambiguities in defining the appropriate links. The purpose of this paper is to define a general triangulation procedure that provides a solution to these problems. We first describe a simple heuristic triangulation algorithm which is extended to nonconvex contours. It uses an original decomposition of an arbitrary contour into elementary convex subcontours. Then the problem of linking one contour in a slice to several contours in an adjacent slice is examined. To this end, a new and unique interpolated contour is generated between the two slices, and the link is created using the previously defined procedure. Next, a solution to the general case of linking multiple contours in each slice is proposed. Finally, the algorithm is applied to the reconstitution of the external surface of a complex shaped object: a human vertebra.
Computation of the multivariate normal integral
Authors: Drezner Zvi
Published: July 2002

This paper presents a direct computation of the multivariate normal integral by the Gauss Quadrature method. An error control method is given. Results are presented for multivariate integrals consisting of up to twelve normal distributions. A computer program in FORTRAN is given.
Solution of the Sylvester matrix equation AXB

T

+ CXD

T

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

A software package has been developed to solve efficiently the Sylvester-type matrix equation

AXB
T

+

CXD
T

=
E
. A transformation method is used which employs the QZ algorithm to structure the equation in such a way that it can be solved columnwise by a back substitution technique. The algorithm is an extension of the Bartels-Stewart method and the Hessenberg-Schur method. The numerical performance of the algorithms and software is demonstrated by application to near-singular systems.
Functional composition algorithms via blossoming
Authors: DeRose Tony D. , Goldman Ronald N. , Hagen Hans , Mann Stephen
Published: July 2002

In view of the fundamental role that functional composition plays in mathematics, it is not surprising that a variety of problems in geometric modeling can be viewed as instances of the following composition problem: given representations for two functions
F
and
G
, compute a representation of the function
H
=
F o G
. We examine this problem in detail for the case when
F
and
G
are given in either Be´zier or B-spline form. Blossoming techniques are used to gain theoretical insight into the structure of the solution which is then used to develop efficient, tightly codable algorithms. From a practical point of view, if the composition algorithms are implemented as library routines, a number of geometric-modeling problems can be solved with a small amount of additional software.
Object-oriented logical specification of time-critical systems
Authors: Morzenti Angelo , San Pietro Pierluigi
Published: July 2002

We define TRIO
+
, an object-oriented logical language for modular system specification. TRIO
+
is based on TRIO, a first-order temporal language that is well suited to the specification of embedded and real-time systems, and that provides an effective support to a variety of validation activities, like specification testing, simulation, and property proof. Unfortunately, TRIO lacks the ability to construct specifications of complex systems in a systematic and modular way. TRIO
+
combines the use of constructs for hierarchical system decomposition and object-oriented concepts like inheritance and genericity with an expressive and intuitive graphic notation, yielding a specification language that is formal and rigorous, yet still flexible, readable, general, and easily adaptable to the user's needs. After introducing and motivating the main features of the language, we illustrate its application to a nontrivial case study extracted from a real-life industrial application.
Twisted GFSR generators II
Authors: Matsumoto Makoto , Kurita Yoshiharu
Published: July 2002

The twisted GFSR generators proposed in a previous article have a defect in
k
-distribution for
k
larger than the order of recurrence. In this follow up article, we introduce and analyze a new TGFSR variant having better
k
-distribution property. We provide an efficient algorithm to obtain the order of equidistribution, together with a tight upper bound on the order. We discuss a method to search for generators attaining this bound, and we list some of these such generators. The upper bound turns out to be (sometimes far) less than the maximum order of equidistribution for a generator of that period length, but far more than that for a GFSR with a working are of the same size.
Algorithm 736: Hyperelliptic integrals and the surface measure of ellipsoids
Authors: Dunkl Charles F. , Ramirez Donald E.
Published: July 2002

The algorithm for computing a class of hyperelliptic integrals and for determining the surface measure of ellipsoids is described in detail by Dunkl and Ramirez [1994]. An efficient implementation of their algorithm is presented here.
A database cache for high performance and fast restart in database systems
Authors: Elhardt Klaus , Bayer Rudolf
Published: July 2002

Performance in database systems is strongly influenced by buffer management and transaction recovery methods. This paper presents the principles of the database cache, which replaces the traditional buffer. In comparison to buffer management, cache management is more carefully coordinated with transaction management, and integrates transaction recovery. High throughput of

small- and medium-sized transactions is achieved by fast commit processing and low database traffic. Very fast handling of transaction failures and short restart time after system failure are guaranteed in such an environment. Very long retrieval and update transactions are also supported.
Computing in Vietnam
Authors: Goodman S. E. , Press L. I.
Published: July 2002

Nguyen Dinh Ngoc and Dang Huu were among the senior technology leaders at the Fourth Informatics Week conference and exhibition held in Ho Chi Minh City (HCMC) in August 1994, an event that swarmed with teenagers, young techies, and businessmen.
LEDA: a platform for combinatorial and geometric computing
Authors: Mehlhorn Kurt , Näher Stefan
Published: July 2002

Combinatorial and geometric computing is a core area of computer science (CS). In fact, most CS curricula contain a course in data structures and algorithms. The area deals with objects such as graphs, sequences, dictionaries, trees, shortest paths, flows, matchings, points, segments, lines, convex hulls, and Voronoi diagrams and forms the basis for application areas such as discrete optimization, scheduling, traffic control, CAD, and graphics. There is no standard library of the data structures and algorithms of combinatorial and geometric computing. This is in sharp contrast to many other areas of computing. There are, for example, packages in statistics (SPSS), numerical analysis (LINPACK, EISPACK), symbolic computation (MAPLE, MATHEMATICA), and linear programming (CPLEX).
World-Wide Web and computer science reports
Authors: Fox Edward A.
Published: July 2002

With the advent of the World-Wide Web, computing professionals have eagerly pursued the idea of moving from a paper-based technical report service to one that employs networked information systems. Many departments keep some version of their reports on an FTP server to help with this process. To facilitate access to CS reports a number of sites have set up lists of these archives (see sidebar).
Dienst: an architecture for distributed document libraries
Authors: Lagoze Carl , Davis James R.
Published: July 2002

As one of the five universities participating in the ARPA-sponsored Computer Science Technical Report project, we at Cornell have developed a digital library architecture called Dienst. Dienst is a protocol and implementation that provides Internet access to a distributed, decentralized multi-format document collection. The collection is managed by a set of interoperating Dienst servers distributed over the Internet. These servers provide three digital library services: repositories of multi-format documents; indexes into the document collection and search engines for these indexes; and user interfaces for browsing, searching, and accessing the collection.
A video retrieval and sequencing system
Authors: Chua Tat-Seng , Ruan Li-Qun
Published: July 2002

Video is an effective medium for capturing the events in the real world around us, and a vast amount of video materials exists, covering a wide range of applications. However, widespread use of video in computer applications is often impeded by the lack of effective tools to manage video information systematically. This article discusses the design and implementation of a frame-based video retrieval and sequencing system (VRSS). The system is designed to support the entire process of video information management: segmenting, indexing, retrieving, and sequencing of video data. A semiautomatic tool is developed to divide video sequences into meaningful shots. Each video shot is logged using text descriptions, audio dialogue, and cinematic attributes. A two-layered, concept-based model is used as the basis for accurately retrieving relevant video shots based on users' free-text queries. A cinematic, rule-based, virtual editing tool is also developed to sequence the video shots retrieved for presentation within a specified time constraint. The system has been tested on a video documentary on the NUS (National University of Singapore) engineering faculty. The results of video retrieval experiments are encouraging.
Distributed process groups in the V Kernel
Authors: Cheriton David R. , Zwaenepoel Willy
Published: July 2002

The V kernel supports an abstraction of processes, with operations for interprocess communication, process management, and memory management. This abstraction is used as a software base for constructing distributed systems. As a distributed kernel, the V kernel makes intermachine boundaries largely transparent.

In this environment of many cooperating processes on different machines, there are many logical
groups
of processes. Examples include the group of tile servers, a group of processes executing a particular job, and a group of processes executing a distributed parallel computation.

In this paper we describe the extension of the V kernel to support process groups. Operations on groups include group interprocess communication, which provides an application-level abstraction of network multicast. Aspects of the implementation and performance, and initial experience with applications are discussed.
Using failure cost information for testing and reliability assessment
Authors: Weyuker Elaine J.
Published: July 2002

A technique for incorporating failure cost information into algorithms designed to automatically generate software-load-testing suites is presented. A previously introduced reliability measure is also modified to incorporate this cost information. examples are presented to show the usefulness of including cost information when testing or assessing software.
Distribution of mathematical software via electronic mail
Authors: Dongarra Jack J , Grosse Eric
Published: July 2002

A large collection of public-domain mathematical software is now available via electronic mail. Messages sent to "netlib@anl-mcs" (on the Arpanet/CSNET) or to "research!netlib" (on the UNIX® network) wake up a server that distributes items from the collection. The one-line message "send index" causes a library catalog to be sent by return mail.
Recognizing planar perfect graphs
Authors: Hsu Wen-Lian
Published: July 2002

An
O
(
n
3
) algorithm for recognizing planar graphs that do not contain induced odd cycles of length greater than 3 (odd holes) is presented. A planar graph with this property satisfies the requirement that its maximum clique size equal the minimum number of colors required for the graph (graphs all of whose induced subgraphs satisfy the latter property are perfect as defined by Berge). The algorithm presented is based on decomposing these graphs into essentially two special classes of inseparable component graphs that are easy to recognize. They are (i) planar comparability graphs and (ii) planar line graphs of those planar bipartite graphs whose maximum degrees are no greater than 3. Composition schemes for generating planar perfect graphs from those basic components are also provided. This decomposition algorithm can also be adapted to solve the corresponding maximum independent set and minimum coloring problems. Finally, the path-parity problem on planar perfect graphs is considered.
High-performance operating system primitives for robotics and real-time control systems
Authors: Schwan Karsten , Bihari Tom , Weide Bruce W. , Taulbee Gregor
Published: July 2002

To increase speed and reliability of operation, multiple computers are replacing uniprocessors and wired-logic controllers in modern robots and industrial control systems. However, performance increases are not attained by such hardware alone. The
operating software
controlling the robots or control systems must exploit the possible parallelism of various control tasks in order to perform the necessary computations within given real-time and reliability constraints. Such software consists of both control programs written by application programmers and operating system software offering means of task scheduling, intertask communication, and device control.

The Generalized Executive for real-time Multiprocessor applications (GEM) is an operating system that addresses several requirements of operating software. First, when using GEM, programmers can select one of two different types of tasks differing in size, called processes and microprocesses. Second, the scheduling calls offered by GEM permit the implementation of several models of task interaction. Third, GEM supports multiple models of communication with a parameterized communication mechanism. Fourth, GEM is closely coupled to prototype real-time programming environments that provide programming support for the models of computation offered by the operating system. GEM is being used on a multiprocessor with robotics application software of substantial size and complexity.
The information structure of distributed mutual exclusion algorithms
Authors: Sanders Beverly A.
Published: July 2002

The concept of an information structure is introduced as a unifying principle behind several of the numerous algorithms that have been proposed for the distributed mutual exclusion problem. This approach allows the development of a generalized mutual exclusion algorithm that accepts a particular information structure at initialization and realizes both known and new algorithms as special cases. Two simple performance metrics of a realized algorithm can be obtained directly from the information structure. A new failure recovery mechanism called local recovery, which requires no coordination between nodes and no additional messages beyond that needed for failure detection, is introduced.
Competitive solutions for online financial problems
Authors: El-Yaniv Ran
Published: July 2002

This article surveys results concerning online algorihtms for solving problems related to the management of money and other assets. In particular, the survey focucus us search, replacement, and portfolio selection problems
Polyhedral subdivision methods for free-form surfaces
Authors: Nasri Ahmad H.
Published: July 2002

One of the central issues in computer-aided geometric design is the representation of free-form surfaces which are needed for many purposes in engineering and science. Several limitations are imposed on most available surface systems: the rectangularity of the network describing a surface and the manipulation of surfaces without regard to the volume enclosed are examples. Polyhedral subdivision methods suggest themselves as a solution to these problems. Their use, however, is not widespread for several reasons such as the lack of boundary control, and interpolation and interrogation capabilities.

In this paper the original work on subdivision methods is extended to overcome these problems. Two methods are described, one for controlling the boundary curves of such surfaces, and another for interpolating points on irregular networks. A general surface/surface intersection algorithm is also provided: seven decisions need to be made in order to specify a particular implementation. The algorithm is also suitable for intersecting other classes of surfaces amongst which are the popular Bézier and B-spline surfaces.
An empirical study of static call graph extractors
Authors: Murphy Gail C. , Notkin David , Griswold William G. , Lan Erica S.
Published: July 2002

Informally, a call graph represents calls between entities in a given program. The call graphs that compilers compute to determine the applicability of an optimization must typically be conservative: a call may be omitted only if it can never occur in any execution of the program. Numerous software engineering tools also extract call graphs with the expectation that they will help software engineers increase their understanding of a program. The requirements placed on software engineering
tools that compute call graphs are typically more relaxed than for compilers. For example, some false negatives—calls that can in fact take place in some execution of the program, but which are omitted from the call graph—may be acceptable, depending on the understanding task at hand. In this article, we empirically show a consequence of this spectrum of requirements by comparing the C call graphs extracted from three software systems (mapmaker, mosaic, and gcc) by nine tools (cflow, cawk, CIA, Field, GCT, Imagix, LSME, Mawk, and Rigiparse). A quantitative analysis of the call graphs extracted for each system shows considerable variation, a result that is counterintuitive to many experienced software engineers. A qualitative analysis of these results reveals a number of reasons for this variation: differing treatments of macros, function pointers, input formats, etc. The fundamental problem is not that variances among the graphs extracted by different tools exist, but that software engineers have little sense of the dimensions of approximation in any particular call graph. In this article, we describe and discuss the study, sketch a design space for static call graph extractors, and discuss the impact of our study on practitioners, tool developers, and researchers. Although this article considers only one kind of information, call graphs, many of the observations also apply to static extractors of other kinds of information, such as inheritance structures, file dependences, and references to global variables.
A new approach combining simulation and randomization for the analysis of large continuous time Markov chains
Authors: Buchholz Peter
Published: July 2002

A new analysis method for continuous time Markov chains is introduced. The method combines, in some sense, simulation and numerical techniques for the analysis of large Markov chains. The basis of the new method is the description of a continuous-time Markov chain as a set of communicating processes. The state of all or some of the processes is described by a state vector, including a probability distribution over the set of locally reachable states. Simulation is used to determine the event times and message types exchanged between processes. Local transitions are realized by vector matrix products describing the next state distribution form the current one. In this way, the state explosion problem of numerical analysis is avoided, but it is still possible to obtain more accurate results that with pure simulation. The approach is therefore especially useful for the analysis of quantities with small probabilities or for the analysis of rare events.
Word division in Spanish
Authors: Mañas José A.
Published: July 2002

Spanish is a language with very precise and regular orthographic rules. A syllabication algorithm strictly based on syntactic analysis, not requiring any semantic knowledge, is presented and further extended to include hyphenation. Algorithms are presented as pattern matching schemata, and efficient implementations are considered.
EXFI
Authors: Benso A. , Prinetto P. , Rebaudengo M. , Reorda M. Sonza
Published: July 2002

Evaluating the faulty behavior of low-cost embedded microprocessor-based boards is an increasingly important issue, due to their adoption in many safety critical systems. The architecture of a complete Fault Injection environment is proposed, integrating a module for generating a collapsed list of faults, and another for performing their injection and gathering the results. To address this issue, the paper describes a software-implemented Fault Injection approach based on the Trace Exception Mode available in most microprocessors. The authors describe EXFI, a prototypical system implementing the approach, and provide data about some sample benchmark applications. The main advantages of EXFI are the low cost, the good portability, and the high efficiency
Beyond two-phase locking
Authors: Buckley G. N. , Silberschatz A.
Published: July 2002

Many database systems maintain the consistency of the data by using a locking protocol to restrict access to data items. It has been previously shown that if no information is known about the method of accessing items in the database, then the two-phase protocol is optimal. However, the use of structural information about the database allows development of non-two-phase protocols, called
graph protocols
, that can potentially increase efficiency. Yannakakis developed a general class of protocols that included many of the graph protocols. Graph protocols either are only usable in certain types of databases or can incur the performance liability of cascading rollback. In this paper, it is demonstrated that if the system has a priori information as to which data items will be locked first by various transactions, a new graph protocol that is outside the previous classes of graph protocols and is applicable to arbitrarily structured databases can be constructed. This new protocol avoids cascading rollback and its accompanying performance degradation, and extends the class of serializable sequences allowed by non-two-phase protocols. This is the first protocol shown to be always as effective as the two-phase protocol, and it can be more effective for certain types of database systems.
Anisotropic diffusion for Monte Carlo noise reduction
Authors: McCool Michael D.
Published: July 2002

Monte Carlo sampling can be used to estimate solutions to global light transport and other rendering problems. However, a large number of observations may be needed to reduce the variance to acceptable levels. Rather than computing more observations within each pixel, if spatial coherence exists in image space it can be used to reduce visual error by averaging estimators in adjacent pixels. Anisotropic diffusion is a space-variant noise reduction technique that can selectively preserve texture, edges, and other details using a map of image coherence. The coherence map can be estimated from depth and normal information as well as interpixel color distance. Incremental estimation of the reduction in variance, in conjunction with statistical normalization of interpixel color distances, yields an energy-preserving algorithm that converges to a spatially nonconstant steady state.
Duplicate record elimination in large data files
Authors: Bitton Dina , DeWitt David J.
Published: July 2002

The issue of duplicate elimination for large data files in which many occurrences of the same record may appear is addressed. A comprehensive cost analysis of the duplicate elimination operation is presented. This analysis is based on a combinatorial model developed for estimating the size of intermediate runs produced by a modified merge-sort procedure. The performance of this modified merge-sort procedure is demonstrated to be significantly superior to the standard duplicate elimination technique of sorting followed by a sequential pass to locate duplicate records. The results can also be used to provide critical input to a query optimizer in a relational database system.
Multilevel atomicity—a new correctness criterion for database concurrency control
Authors: Lynch Nancy A.
Published: July 2002

Multilevel atomicity
, a new correctness criteria for database concurrency control, is defined. It weakens the usual notion of serializability by permitting controlled interleaving among transactions. It appears to be especially suitable for applications in which the set of transactions has a natural hierarchical structure based on the hierarchical structure of an organization. A characterization for multilevel atomicity, in terms of the absence of cycles in a dependency relation among transaction steps, is given. Some remarks are made concerning implementation.
Correctness of query execution strategies in distributed databases
Authors: Ceri S. , Pelagatti G.
Published: July 2002

A major requirement of a Distributed DataBase Management System (DDBMS) is to enable users to write queries as though the database were not distributed (distribution transparency). The DDBMS transforms the user's queries into execution strategies, that is, sequences of operations on the various nodes of the network and of transmissions between them. An execution strategy on a distributed database is correct if it returns the same result as if the query were applied to a nondistributed database.

This paper analyzes the correctness problem for query execution strategies. A formal model, called Multirelational Algebra, is used as a unifying framework for this purpose. The problem of proving the correctness of execution strategies is reduced to the problem of proving the equivalence of two expressions of Multirelational Algebra. A set of theorems on equivalence is given in order to facilitate this task.

The proposed approach can be used also for the generation of correct execution strategies, because it defines the rules which allow the transformation of a correct strategy into an equivalent one. This paper does not deal with the problem of evaluating equivalent strategies, and therefore is not in itself a proposal for a query optimizer for distributed databases. However, it constitutes a theoretical foundation for the design of such optimizers.
A Majority consensus approach to concurrency control for multiple copy databases
Authors: Thomas Robert H.
Published: July 2002

A “majority consensus” algorithm which represents a new solution to the update synchronization problem for multiple copy databases is presented. The algorithm embodies distributed control and can function effectively in the presence of communication and database site outages. The correctness of the algorithm is demonstrated and the cost of using it is analyzed. Several examples that illustrate aspects of the algorithm operation are included in the Appendix.
Introduction to a system for distributed databases (SDD-1)
Authors: Rothnie J. B. , Bernstein P. A. , Fox S. , Goodman N. , Hammer M. , Landers T. A. , Reeve C. , Shipman D. W. , Wong E.
Published: July 2002

The declining cost of computer hardware and the increasing data processing needs of geographically dispersed organizations have led to substantial interest in distributed data management. SDD-1 is a distributed database management system currently being developed by Computer Corporation of America. Users interact with SDD-1 precisely as if it were a nondistributed database system because SDD-1 handles all issues arising from the distribution of data. These issues include distributed concurrency control, distributed query processing, resiliency to component failure, and distributed directory management. This paper presents an overview of the SDD-1 design and its solutions to the above problems.

This paper is the first of a series of companion papers on SDD-1 (Bernstein and Shipman [2], Bernstein et al. [4], and Hammer and Shipman [14]).