bluuebunny/crossref_metadata_2025 huggingface dataset:
EXACT NUMBER OF MOSAIC PATTERNS IN CELLULAR NEURAL NETWORKS
Authors: BAN JUNG-CHAO , LIN SONG-SUN , SHIH CHIH-WEN
Published: July 2002

This work investigates mosaic patterns for the one-dimensional cellular neural networks with various boundary conditions. These patterns can be formed by combining the basic patterns. The parameter space is partitioned so that the existence of basic patterns can be determined for each parameter region. The mosaic patterns can then be completely characterized through formulating suitable transition matrices and boundary-pattern matrices. These matrices generate the patterns for the interior cells from the basic patterns and indicate the feasible patterns for the boundary cells. As an illustration, we elaborate on the cellular neural networks with a general 1 × 3 template. The exact number of mosaic patterns will be computed for the system with the Dirichlet, Neumann and periodic boundary conditions respectively. The idea in this study can be extended to other one-dimensional lattice systems with finite-range interaction.
THE RESPONSE SPECTRUM MAP, A FREQUENCY DOMAIN EQUIVALENT TO THE BIFURCATION DIAGRAM
Authors: BILLINGS S. A. , BOAGHE O. M.
Published: July 2002

The Response Spectrum Map (RSM) is introduced as a frequency domain equivalent to the Bifurcation Diagram. The RSM is a map of the energy distribution of a system in the frequency domain, where subharmonics, superharmonics and chaos generation can be revealed. The RSM is used in this paper to qualitatively analyze and detect various dynamical states exhibited by a nonlinear system.
EXTERIOR ALGEBRA-BASED ALGORITHMS TO ESTIMATE LIAPUNOV SPECTRA AND STRETCHING STATISTICS IN HIGH-DIMENSIONAL AND DISTRIBUTED SYSTEMS
Authors: ADROVER ALESSANDRA , CERBELLI STEFANO , GIONA MASSIMILIANO
Published: July 2002

This article introduces a direct method for the numerical estimation of the spectra of Liapunov exponents based on the exterior algebra of measure elements. This approach is computationally more robust than the classical approach based on the evolution of n vectors initially possessing linear independence. Several applications of the method proposed are discussed in connection with finite-dimensional systems exhibiting hyperchaos as well as distributed parameter systems associated with reaction/diffusion kinetics.
A CHEMICAL MODEL FOR CHUA'S EQUATION
Authors: LI QIAN SHU , XU WEIGUO
Published: July 2002

The mathematical transformation between chemical dynamical systems and Chua's system is investigated. A chemical kinetic scheme is first presented that gives the Chua's equation. The strange attractor that emerges from numerical integration of our model is all in positive space and the pattern is analogous to that of the Chua's system.
EXISTENCE OF A CUSP POINT ON A FOLD BIFURCATION CURVE AND STABILITY OF THE ASSOCIATED FIXED POINT: CASE OF AN n-DIMENSIONAL MAP
Authors: CARCASSÈS J. P. , KAWAKAMI H.
Published: July 2002

Considering an n–dimensional map T, a necessary and sufficient condition for the existence of a cusp point on a fold bifurcation curve in a parameter plane of T is proposed. In the case of a nondegenerated cusp point, a necessary and sufficient condition for the stability of the associated nonhyperbolic fixed point is established. These conditions, obtained using the classical methods (center manifold, normal form), are expressed in an explicit algebraic well adapted for numerical computing.
PARAMETER-INSENSITIVE AND NARROW-BAND SYNCHRONIZATION OF CHAOTIC CIRCUITS
Authors: CARROLL T. L. , JOHNSON G. A. , PECORA L. M. , MAR D. J.
Published: July 2002

There have been many proposals to use chaotic signals for communications. There are many practical problems with transmitting chaotic signals, however: transmitter and receiver must match, and chaotic signals are affected by phase or amplitude distortion and additive noise. We describe ways to reduce the parameter sensitivity of chaotic synchronization and reduce the bandwidth of chaotic signals.
INTERSECTING FREE SUBGROUPS IN FREE PRODUCTS OF GROUPS
Authors: IVANOV S. V.
Published: July 2002

A subgroup H of a free product [Formula: see text] of groups Gα, α∈ I, is termed factor free if for every [Formula: see text] and β∈I one has SHS-1∩Gβ= {1} (by Kurosh theorem on subgroups of free products, factor free subgroups are free). If K is a finitely generated free group, denote [Formula: see text], where r(K) is the rank of K. It has earlier been proved by the author that if H, K are finitely generated factor free subgroups of [Formula: see text] then [Formula: see text]. It is proved in the article that this estimate is sharp and cannot be improved, that is, there are factor free subgroups H, K in [Formula: see text] so that [Formula: see text] and [Formula: see text]. It is also proved that if the factors Gα, α∈ I, are linearly ordered groups and H, K are finitely generated factor free subgroups of [Formula: see text] then [Formula: see text].
SLICED Ga ACTIONS
Authors: DEVENEY JAMES K. , FINSTON DAVID R.
Published: July 2002

Let k be a field of characteristic zero. Certain classes of fixed point free actions of the additive group of k on affine n-space over k are known to be conjugate to global translations (i.e. to admit equivariant slices). These classes include actions on complex three space for which the invariant ring contains a variable, and certain generalizations of such actions to affine space of any dimension. Methods to construct an equivariant slice for these classes are presented.
ON TORSION-FREE METABELIAN GROUPS WITH COMMUTATOR QUOTIENTS OF PRIME EXPONENT
Authors: GUPTA NARAIN , SIDKI SAID
Published: July 2002

Let G be a torsion-free metabelian group having for commutator quotient, an elementary abelian p-group of rank k. It is shown that k≥3 for all primes p. Examples of such metabelian torsion-free groups are constructed for all primes p and all ranks k≥3, except for p=2, k=3.
THE STOKES PROBLEM IN ℝn: AN APPROACH IN WEIGHTED SOBOLEV SPACES
Authors: ALLIOT F. , AMROUCHE C.
Published: July 2002

We prove some existence, uniqueness and regularity results for the solutions to the Stokes problem in ℝn, n≥2 in weighted Sobolev spaces [Formula: see text]. This framework enables us to characterise for which data the problem has solutions with prescribed decay or growth at infinity. Moreover, we obtain an explicit representation as well as an asymptotic expansion of the solution for non-smooth decaying data. We also establish the density of smooth solenoidal vector fields in the subspace of [Formula: see text] such that div v=0.
VISUALIZATION SUPPORT FOR USER-CENTERED MODEL SELECTION IN KNOWLEDGE DISCOVERY AND DATA MINING
Authors: HO TUBAO , NGUYEN TRONGDUNG , NGUYEN DUCDUNG , KAWASAKI SAORI
Published: July 2002

The problem of model selection in knowledge discovery and data mining—the selection of appropriate discovered patterns/models or algorithms to achieve such patterns/models—is generally a difficult task for the user as it requires meta-knowledge on algorithms/models and model performance metrics. Viewing knowledge discovery as a human-centered process that requires an effective collaboration between the user and the discovery system, our work aims to make model selection in knowledge discovery easier and more effective. For such a collaboration, our solution is to give the user the ability to try easily various alternatives and to compare competing models quantitatively and qualitatively. The basic idea of our solution is to integrate data and knowledge visualization with the knowledge discovery process in order to the support the participation of the user. We introduce the knowledge discovery system D2MS in which several visualization techniques of data and knowledge are developed and integrated into the steps of the knowledge discovery process. The visualizers in D2MS greatly help the user gain better insight in each step of the knowledge discovery process as well the relationship between data and discovered knowledge in the whole process.
ON SPACES OF CONNECTED GRAPHS III: THE LADDER FILTRATION
Authors: KNEISSLER JAN A.
Published: July 2002

A new filtration of the spaces of tri-/univalent graphs [Formula: see text] that occur in the theory of finite-type invariants of knots and 3-manifolds is introduced.

Combining the results of the two preceding articles, the quotients of this filtration are modeled by spaces of graphs with two types of edges and four types of vertices, and an upper bound for dim [Formula: see text] in terms of the dimensions of the filtration quotients is given. The degree m up to which [Formula: see text] is known is raised by two for u=0 and u=2.
FOUR-DIMENSIONAL INVARIANTS OF LINKS AND THE ADJUNCTION FORMULA
Authors: KAWAMURA TOMOMI
Published: July 2002

We compute the slice euler characteristic of certain links by using the so-called generalized adjunction formula, which is proved by Kronheimer, Mrowka, Morgan, Szabó and Taubes. Furthermore, for links obtained from such links by band surgery, we estimate the unknotting numbers, the 4-dimensional clasp numbers, and the slice euler characteristic.
RECOVERING THE INTERNAL DYNAMICS AND THE SHAPES OF GALAXY CLUSTERS: VIRGO CLUSTER
Authors: GURZADYAN V. G. , RAUZY S. , TRIAY R.
Published: July 2002

We describe a method for recovering of the substructure, internal dynamics and geometrical shapes of clusters of galaxies. Applying the method to the Virgo cluster, we first, reveal the substructure of the central 4 arc degree field of the Virgo cluster by means of S-tree technique. The existence of three main subgroups of galaxies is revealed and their dynamical characteristics are estimated. Then, using the previously suggested technique (Ref. 1), the bulk flow velocities of the subgroups are evaluated based on the distribution of the redshifts of the galaxies. The results enable us also to obtain a secure indication of the elongation of the Virgo cluster and its positional inclination.
EXACT INFLATIONARY SOLUTIONS
Authors: PICCINELLI GABRIELLA , MATOS TONATIUH , MONTESINOS-VELÁSQUEZ MERCED
Published: July 2002

We present a new class of exact inflationary solutions for the evolution of a universe with spatial curvature, filled with a perfect fluid, a scalar field with potential V±(ϕ) = λ(ϕ2 ± δ2)2 and a cosmological constant Λ. With the V+(ϕ) potential and a negative cosmological constant, the scale factor experiments a graceful exit. We give a brief discussion about the physical meaning of the solutions.
RELIABILITY MODELING AND ASSET MANAGEMENT FOR DISTRIBUTION SYSTEMS
Authors: VEEVERS ALAN , OBAID HUSSAIN A. Z. M.
Published: July 2002

Throughout the developed world the problem of how best to manage aging assets is being faced. It is particularly critical in distribution systems such as mains water reticulation, sewage networks and electricity supply lines. In many towns, some underground water and sewer pipelines are more than 50 years old. It is already prohibitive on cost grounds to replace all these deteriorating assets, so a cost-effective replacement/repair strategy must be used. Reliability modeling-based solutions to this problem are discussed, together with issues related to the quality of the available data. Some of the outcomes for industry are improved monitoring and record keeping, objective evaluation of alternative management options, and reliability prediction to enable sound planning decisions to be made. The applicability of these methods to other distribution systems is also discussed.
HOLOGRAPHIC IMAGES OF ADATOMS, DIMERS AND REST ATOMS ON THE Si(111)-(7 × 7) SURFACE
Authors: SHEN TSAI-SHENG , CHANG C. Y. , CHOU Y. C. , WEI C. M.
Published: July 2002

The adatoms, dimers and rest atoms in the three outermost atomic layers of the Si(111)-(7 × 7) surface are directly imaged with glancing Kikuchi electron holography. The applicability of Kikuchi electron holography to complicated multiple-emitter surfaces is evident. The three-dimensional relative positions of atoms on the Si(111)-(7 × 7) surface are in good accordance with the LEED-optimized DAS model.
STRUCTURE DETERMINATION OF THE Ge(111)-(3×1)Ag SURFACE RECONSTRUCTION
Authors: GROZEA D. , BENGU E. , COLLAZO-DAVILA C. , MARKS L. D.
Published: July 2002

For the first time, during the investigation of the Ag submonolayer on the Ge(111) system, large, independent domains of the Ge (111)-(3×1) Ag phase were imaged and investigated. Previous studies have reported it only as small insets between Ge (111)-(4×4) Ag and Ge (111)- c (2×8) domains. The transmission electron diffraction data were analyzed using a Direct Methods approach and "heavy-atom holography," with the result of an atomic model of the structure similar to that of Ge (111)-(3×1) Ag .
CHONDROSARCOMA OF THUMB METACARPAL — A CASE REPORT WITH LITERATURE REVIEW
Authors: Pathak G. , Conolly W. B. , McCarthy S. W.
Published: July 2002

Function preserving management of a dominant thumb metacarpal chondrosarcoma is reported, with a literature review for this uncommon neoplasm. Wide local excision of the metacarpal followed by temporary silicone block interposition and definitive iliac crest bone grafting was performed. A persistent wound defect was managed by a radial artery forearm flap. The functional result was acceptable. In the literature, there were seven cases of thumb metacarpal chondrosarcoma reported; two were treated by ray amputation, and the other five were treated by excision of the metacarpal. Three of those five had bone graft and the other two had simple resection. Of these seven cases, three had local recurrence and one a distant metastasis.
Hypothenar Flap
Authors: Gu Yu-Dong
Published: July 2002

The hypothenar flap was designed with its blood supply coming from the cutaneous branches of the superficial palmar arch arising from the ulnar vascular pedicle. The nerve supply is from the hypothenar cutaneous branch of the ulnar nerve. The flap was successfully applied to treat two patients with scar contractures in the hand. This paper would describe the relevant anatomy and the operative method. The indications for use of the flap were also discussed.
ARTHROSCOPIC SUTURING OF ULNAR AVULSIONS (TYPE I-B) OF THE TRIANGULAR FIBROCARTILAGE COMPLEX OF THE WRIST
Authors: De Smet L. , Van De Meulebroucke B. , Van Ransbeeck H. , Zachee B. , Fabry G.
Published: July 2002

We reviewed 17 patients with an arthroscopic repair of ulnar avulsions of the TFCC: 12 are considered good, 2 fair and 3 poor.

No major complications occurred. The grip forced averaged 71.5% of the contralateral side.

These results equal those of open procedures, without the necessity of an extensive approach.
RESTORATION OF ELBOW FLEXOR IN BRACHIAL PLEXUS INJURED PATIENTS
Authors: Chalidapong Preecha , Sananpanich Kanit , Chiengthong Korku , Sakares Variya
Published: July 2002

Biceps brachii is one major elbow flexor, which is innervated by the musculocutaneous nerve from the C5 and C6 root. From 1987 to 1996, the elbow flexor restoration procedures were performed in 461 brachial plexus injured patients by means of 347 intercostal nerve transfers, with 105° arc of flexion and 2.05 kg weight lifting; intercostal nerve transfer to 34 gracilles and 7 rectus femoris free vascularized muscle transplantation, with 111.45 and 86° arc of flexion, and 2.77 and 1.9 kg weight lifting, respectively; 41 modified Steindler flexorplasty, with 74.9° arc of flexion and 2.01 kg weight lifting; 27 lattisimus dorsi muscle (Zancolli's bipolar method), with 127.7° arc of flexion and 3.15 kg weight lifting; 3 pectoralis major tendon (Goldner's method), with 85° arc of flexion and 1.3 kg weight lifting; and 2 triceps muscle (Carroll's method) with 85° arc of flexion and 1.5 kg weight lifting. A comparison shows that, the latissimus dorsi muscle transfer obtained the best result for arc of flexion and weight lifting, followed by the gracilles muscle and the intercostal nerve transfer procedure, respectively.
USE OF A NEW EXTERNAL FIXATOR FOR THE CORRECTION OF FIXED FLEXION DEFORMITY OF THE FINGERS
Authors: Siow Y. S. , Ahmad T. S. , Goh S. Y.
Published: July 2002

Three patients with severe fixed flexion deformity of the fingers caused by trauma were reported. As an alternative treatment, a new mini external fixator was used to correct the deformities. The use of this device has made treatment of contractures simpler and more predictable. Gradual distraction and straightening was applied to loosen and extend the joints, followed by a period of mobilisation while still on the device. In all the three patients, this experimental device and approach led to improvement of the fixed flexion deformities. With use of this device, surgical release may not be necessary.
COOPERATIVE INFORMATION AGENTS FOR DIGITAL CITIES
Authors: OYAMA SATOSHI , HIRAMATSU KAORU , ISHIDA TORU
Published: July 2002

A digital city is a social information infrastructure for urban life (including shopping, business, transportation, education, welfare and so on). We started a project to develop a digital city for Kyoto based on the newest technologies including cooperative information agents. This paper presents an architecture for digital cities and shows the roles of agent interfaces in it. We propose two types of cooperative information agents as follows: (a) the front-end agents determine and refine users' uncertain goals, (b) the back-end agents extract and organize relevant information from the Internet, (c) Both types of agents opportunistically cooperate through a blackboard. We also show the research guidelines towards social agents in digital cities; the agent will foster social interaction among people who are living in/visiting the city.
LEARNING TO FACE STOCHASTIC DEMAND
Authors: FLÅM SJUR DIDRIK , SANDSMARK MARIA
Published: July 2002

We consider repeated interaction among several producers of a homogeneous, divisible good, traded at a common market. Demand is uncertain, and its law is unknown. We explore an adaptive scheme leading such producers, over time, to face correct demand data. Extensions include non-cooperative games in which strategic interaction is felt via exactly two real parameters.
PERCEPTION-BASED ANALYSIS OF ENGINEERING EXPERIMENTS IN THE SEMICONDUCTOR INDUSTRY
Authors: LAST MARK , KANDEL ABRAHAM
Published: July 2002

Comparing frequency distributions of experimental data is a routine engineering task in the semiconductor industry. The existing statistical approaches to the problem suffer from several limitations, which can be partially overcome via the time-consuming visual examination of frequency histograms by an experienced process engineer. This paper presents a novel, fuzzy-based method for automating the cognitive process of comparing frequency histograms. We use the evolving approach of type-2 fuzzy logic to utilize the domain knowledge of human experts. The proposed method is evaluated on the actual results of an engineering experiment, where it is shown to represent the experts' perception of the visualized data more accurately than a wide range of statistical tests. We also outline the potential directions for integrating the perception-based approach with other methods of data visualization and data mining.
ALGEBRAICALLY OPTIMAL PARAMETRIZATIONS OF QUASI-POLYNOMIAL ALGEBRAIC CURVES
Authors: RAFAEL SENDRA J. , VILLARINO CARLOS
Published: July 2002

In this paper we deal with the problem of computing algebraically optimal parametrizations for quasi-polynomial algebraic curves. The algebraic optimality parametrization problem consists in computing rational parametrizations which coefficients are in the smallest possible field extension of the ground field. In [6], and in [30], it is shown that for the class of polynomial curves the optimal parametrization problem is reduced to check whether the corresponding Weil's descente variety of the curve is a line over the ground field. In this paper, we introduce a bigger class of curves, namely the class of quasi-polynomial curves, and we show that this property is still true. Furthermore, we present an algorithm to decide whether the 1-dimensional component of the Weil's descente variety is a line over the ground field that avoids to compute the usually huge implicit equations of Weil's variety. In addition, we analyze main properties of quasi-polynomial curves, we present an algorithmic characterization of the definability, over a field, of curves given parametrically by means of the Weil's descente variety, and we extend Manocha and Canny's criteria, given in [20], for polynomial curves to the case of quasi-polynomial curves.
DELIVERING BUSINESS CRITICAL INFORMATION SYSTEMS THOUGH APPLICATION SERVICE PROVIDERS: THE NEED FOR A MARKET SEGMENTATION STRATEGY
Authors: CURRIE WENDY L. , SELTSIKAS PHILIP
Published: July 2002

This paper draws from the findings of a large-scale empirical research program on the global application service provider (ASP) industry funded by research grants from the European Commission (EC) and the Engineering and Physical Sciences Research Council (EPSRC). A conceptual framework consisting of a taxonomy of ASPs is used to demonstrate the different market segmentation strategies adopted by ASPs for competing in this fledgling and turbulent industry. Drawing from empirical research carried out in the US and Europe, the paper evaluates ASP strategies for deploying, hosting, managing and enabling software applications on behalf of their customers. The ASP business model is advocated as an attractive value proposition for SMEs, dot.com companies and other start-up firms seeking hyper-growth. Yet the evidence so far suggests a slow start to the ASP market as few reference sites demonstrating best practice exist. ASPs will therefore need to re-evaluate their strategies if they are to convince potential customers of the benefits of application outsourcing. Against this background, the paper evaluates the benefits and risks of the ASP model.
Algorithm 690: Chebyshev polynomial software for elliptic-parabolic systems of PDEs
Authors: Berzins M. , Dew P. M.
Published: July 2002

PDECHEB is a FORTRAN 77 software package that semidiscretizes a wide range of time-dependent partial differential equations in one space variable. The software implements a family of spacial discretization formulas, based on piecewise Chebyshev polynomial expansions with C
0
continuity. The package has been designed to be used in conjunction with a general integrator for initial value problems to provide a powerful software tool for the solution of parabolic-elliptic PDEs with coupled differential algebraic equations. Examples are provided to illustrate the use of the package with the DASSL d.a.e integrator of Petzold [18].
Algorithm 692: Model implementation and test package for the Sparse Basic Linear Algebra Subprograms
Authors: Dodson David S. , Grimes Roger G. , Lewis John G.
Published: July 2002

This paper desribes a model implementation and test software for the Sparse Basic Linear Algebra Subprograms (Sparse BLAS). The Sparse BLAS perform vector operations common in sparse linear algebra, with the goal of providing efficient, but portable, implementations of algorithms for high performance computers. The model implementation provides a portable set of FORTRAN 77 Sparse BLAS for the use on machines where specially tuned implementations do not exist or are not required. The test software is designed to verify that tuned implementations meet the specifications of the Sparse BLAS and that implementations are correctly installed.
Computing in a less-developed country
Authors: Goodman Seymour E.
Published: July 2002

Almost all of the nations of Latin America are so-called less-developed countries (LDCs). But unlike many such countries elsewhere, quite a few have recently attempted to install more democratic, or at least less authoritarian, governments that are permitting greater freedom of expression and information and encouraging market-oriented economic developments. The latter include decreasing protectionism and moves toward the privatization of state enterprises such as telecommunications companies. Given the land area, natural resources, and populations involved, these developments are potentially of enormous international importance. The information technologies (IT) could be used to accelerate and reinforce these political and economic changes.
Algorithm 707: CONHYP: a numerical evaluator of the confluent hypergeometric function for complex arguments of large magnitudes
Authors: Nardin Mark , Perger W. F. , Bhalla Atul
Published: July 2002

A numerical evaluator for the confluent hypergeometric function for complex arguments with large magnitudes using a direct summation of Kummer's series is presented. Extended precision subroutines using large arrays to accumulate a single numerator and denominator are ultimately used in a single division to arrive at the final result. The accuracy has been verified through a variety of tests and they show the evaluator to be consistently accurate to 13 significant figures, and on rare occasion accurate to only 9 for magnitudes of the arguments ranging into the thousands in any quadrant in the complex plane. Because the evaluator automatically determines the number of significant figures of machine precision, and because it is written in FORTRAN 77, tests on various computers have shown the evaluator to provide consistently accurate results, making the evaluator very portable. The principal drawback is that, for certain arguments, the evaluator is slow; however, the evaluator remains valuable as a benchmark even in such cases.
FLIP: an internetwork protocol for supporting distributed systems
Authors: Kaashoek M. Frans , van Renesse Robbert , van Staveren Hans , Tanenbaum Andrew S.
Published: July 2002

Most modern network protocols give adequate support for traditional applications such as file transfer and remote login. Distributed applications, however, have different requirements (e.g., efficient at-most-once remote procedure call even in the face of processor failures). Instead of using ad hoc protocols to meet each of the new requirements, we have designed a new protocol, called the Fast Local Internet Protocol (FLIP), that provides a clean and simple integrated approach to these new requirements. FLIP is an unreliable message protocol that provides both point-to-point communication and multicast communication, and requires almost no network management. Furthermore, by using FLIP we have simplified higher-level protocols such as remote procedure call and group communication, and enhanced support for process migration and security. A prototype implementation of FLIP has been built as part of the new kernel for the Amoeba distributed operating system, and is in daily use. Measurements of its performance are presented.
Probabilistic information retrieval as a combination of abstraction, inductive learning, and probabilistic assumptions
Authors: Fuhr Norbert , Pfeifer Ulrich
Published: July 2002

We show that former approaches in probabilistic information retrieval are based on one or two of the three concepts
abstraction, inductive learning
, and
probabilistic assumptions
, and we propose a new approach which combines all three concepts. This approach is illustrated for the case of indexing with a controlled vocabulary. For this purpose, we describe a new probabilistic model first, which is then combined with logistic regression, thus yielding a generalization of the original model. Experimental results for the pure theoretical model as well as for heuristic variants are given. Furthermore, linear and logistic regression are compared.
A note on the quality of random variates generated by the ratio of uniforms method
Authors: Hörmann Wolfgang
Published: July 2002

The one-dimensional distribution of pseudorandom numbers generated by the ratio of uniforms method using linear congruential generators (LCGs) as the source of uniform random number is investigated in this note. Due to the two-dimensional lattice structure of LCGs there is always a comparable large gap without a point in the one-dimensional distribution of any ratio of uniforms method. Lower bounds for these probabilities only depending on the modulus and the Beyer quotient of the LCG are proved for the case that Cauchy normal or exponential random numbers are generated. These bounds justify the recommendation not to use the ratio of uniform method combined with LCGs.
The roles of digital libraries in teaching and learning
Authors: Marchionini Gary , Maurer Hermann
Published: July 2002

Libraries have long served crucial roles in learning. The first great library, in Alexandria 2,000 years ago, was really the first university. It consisted of a zoo and various cultural artifacts in addition to much of the ancient world's written knowledge and attracted scholars from around the Mediterranean, who lived and worked in a scholarly community for years at a time. Today, the rhetoric associated with the National/Global Information Infrastructure (N/GII) always includes examples of how the vast quantities of information that global networks provide (i.e., digital libraries) will be used in educational settings [16].
Performance and dependability evaluation of scalable massively parallel computer systems with conjoint simulation
Authors: Hein Axel , Cin Mario Dal
Published: July 2002

Computer systems are becoming more and more a part of our daily life; business and industry rely on their service, and the health of human beings depends on their correct functioning. Computer systems used for critical tasks have to be carefully designed and tested during the early design stage, the prototype phase, and their operational life. Methods and tools are required to support and facilitate this vital task. In this article, we tackle the issue of system-level performance and dependability analysis of fault-tolerant scalable computer systems. A modeling methodology called “Conjoint Simulation” is presented, which is based on the parti tioning of the system model and the combination of several modeling techniques. Object-oriented model construction and process-based simulation are applied for architecture and workload modeling, and timed Petri nets are the core modeling technique representing the failure scenarios and repair policies. Splitting the overall model and exploiting appropriate modeling techniques ease the development, maintenance, and extensibility of large-scale and complex simulation models. Furthermore, techniques are provided for hierarchical model construction, object-oriented workload modeling, and simulated error injection in order to perform combined performance and dependability analysis.
Behavioral synthesis of combinational logic using spectral-based heuristics
Authors: Thornton M. A. , Nair V. S. S.
Published: July 2002

A prototype system developed to convert a behavioral representation of a Boolean function in OBDD form into an initial structural representation is described and experimental results are given. The system produces a multilevel circuit using heuristic rules based on properties of a subset of spectral coefficients. Since the behavioral description is in OBDD form, efficient methods are used to quickly compute the small subset of spectral coefficients needed for the application of the heuristics. The heuristics guide subsequent decompositions of the OBDD, resulting in an iterative construction of the structural form. At each stage of the translation, the form of the decomposition is chosen in order to achieve optimization goals.
The traveling salesman problem in graphs with 3-edge cutsets
Authors: Cornuéjols G. , Naddef D. , Pulleyblank W.
Published: July 2002

This paper analyzes decomposition properties of a graph that, when they occur, permit a polynomial solution of the traveling salesman problem and a description of the traveling salesman polytope by a system of linear equalities and inequalities. The central notion is that of a 3-edge cutset, namely, a set of 3 edges that, when removed, disconnects the graph. Conversely, our approach can be used to construct classes of graphs for which there exists a polynomial algorithm for the traveling salesman problem. The approach is illustrated on two examples, Halin graphs and prismatic graphs.
Statistical database design
Authors: Chin Francis Y. , Ozsoyoglu Gultekin
Published: July 2002

The security problem of a statistical database is to limit the use of the database so that no sequence of statistical queries is sufficient to deduce confidential or private information. In this paper it is suggested that the problem be investigated at the conceptual data model level. The design of a statistical database should utilize a statistical security management facility to enforce the security constraints at the conceptual model level. Information revealed to users is well defined in the sense that it can at most be reduced to nondecomposable information involving a group of individuals. In addition, the design also takes into consideration means of storing the query information for auditing purposes, changes in the database, users' knowledge, and some security measures.
Determining View dependencies using tableaux
Authors: Klug Anthony , Price Rod
Published: July 2002

A relational database models some part of the real world by a set of relations and a set of constraints. The constraints model properties of the stored information and must be maintained true at all times. For views defined over physically stored (base) relations, this is done by determining whether the view constraints are logical consequences of base relation constraints. A technique for determining such valid view constraints is presented in this paper. A generalization of the tableau chase is used. The idea of the method is to generate a tableau for the expression whose summary violates the test constraints in a “canonical” way. The chase then tries to remove this violation.

It is also shown how this method has applications to schema design. Relations not in normal form or having other deficiencies can be replaced by normal form projections without losing the ability to represent all constraint information.
Multiversion concurrency control—theory and algorithms
Authors: Bernstein Philip A. , Goodman Nathan
Published: July 2002

Concurrency control is the activity of synchronizing operations issued by concurrently executing programs on a shared database. The goal is to produce an execution that has the same effect as a serial (noninterleaved) one. In a multiversion database system, each write on a data item produces a new copy (or
version
) of that data item. This paper presents a theory for analyzing the correctness of concurrency control algorithms for multiversion database systems. We use the theory to analyze some new algorithms and some previously published ones.
Automatic Controlled Precision Calculations
Authors: Chartres Bruce A.
Published: July 2002

Recent developments in computer design and error analysis have made feasible the use of variable precision arithmetic and the preparation of programs that automatically determine their own precision requirements. Such programs enable the user to specify the accuracy he wants, and yield answers guaranteed to lie within the bounds prescribed. A class of such programs, called “contracting error programs,” is defined in which the precision is determined by prescribing error bounds on the data. A variant of interval arithmetic is defined which enables a limited class of algorithms to be programmed as contracting error programs. A contracting error program for the solution of simultaneous linear equations is described, demonstrating the application of the idea to a wider class of problems.
Some Topics in Code Optimization
Authors: Earnest Christopher
Published: July 2002

Many compilers for higher order languages attempt to translate the source code into “good” object code. Cocke and Schwartz have described an algorithm for discovering when the computation of an expression is redundant (common), and when it can be moved to a less frequently executed region of the program. The present paper includes a tutorial presentation of their basic methods, along with a number of improvements and extensions. These include simplification of the solution method, to save a pass; extension of it to treat the safety constraint, handle multi-entry regions directly, detect additional commonality and code motion after unsafe code motion, and decide where moved code should be put; and combination of the algorithms for commonality and the dead condition, making use of important work of Ken Kennedy.

The methods here applied to collecting information for use in code optimization include general algorithms for solving a set of linear equations in Boolean algebra. The algorithms are most useful when the coefficient matrix is sparse.
On the Parsing of Deterministic Languages
Authors: Havel Ivan M. , Harrison Michael A.
Published: July 2002

A parsing method for strict deterministic grammars is presented and a technique for using it to parse any deterministic language is indicated. An important characterization of the trees of strict deterministic grammars is established. This is used to prove iteration theorems for (strict) deterministic languages, and hence proving that certain sets are not in these families becomes comparatively straightforward. It is shown that every strict deterministic grammar is LR(0) and that any strict deterministic grammar is equivalent to a bounded right context (1, 0) grammar. Thus rigorous proofs that the families of deterministic, LR (
k
), and bounded right context languages are coextensive are presented for the first time.
Type-checking OQL queries in the ODMG type systems
Authors: Alagíc Suad
Published: July 2002

Several negative results are proved about the ability to type-check queries in the only existing proposed standard for object-oriented databases. The first of these negative results is that it is not possible to type-check OQL queries in the type system underlying the ODMG object model and its definition language ODL. The second negative result is that OQL queries cannot be type-checked in the type system of the Java binding of the ODMG standard either. A solution proposed in this paper is to extend the ODMG object model with explicit support for parametric polymorphism (universal type quantification). These results show that Java cannot be a viable database programming language unless extended with parametric polymorphism. This is why type-checking OQL queries presents no problem for the type system of the C++ binding of the ODMG standard. However, a type system that is strictly more powerful than any of the type systems of the ODMG standard is required in order to properly type ordered collectgions and indices. The required form of polymorphism is bounded type quantification (constrained genericity) and even F-bounded polymorphism. A further result is that neither static nor the standard dynamic object-oriented type-checking is possible for Java OQL, in spite of the fact that Java OQL combines features of two strongly and mostly statically-typed languages. Contrary to one of the promises of object-oriented database technology, this result shows that the impedance mismatch does not disappear in the ODMG standard. A type-safe reflective technique is proposed for overcoming this mismatch.
A high-level abstraction of shared accesses
Authors: Keleher Peter J.
Published: July 2002

We describe the design and use of thetapemechanism, a new high-level abstraction of accesses to shared data for software DSMs. Tapes consolidate and generalize a number of recent protocol optimizations, including update-based locks and recorded-replay barriers. Tapes are usually created by “recording” shared accesses. The resulting recordings can be used to anticipate future accesses by tailoring data movement to application semantics. Tapes-based mechanisms are layered on top of existing shared-memory protocols, and are largely independent of the underlying memory model. Tapes can also be used to emulate the data-movement semantics of several update-based protocol implementations, without altering the underlying protocol implementation. We have used tapes to create the Tapeworm synchronization library. Tapeworm implements sophisticated record-replay mechanisms across barriers, augments locks with data-movement semantics, and allows the use of producer-consumer segments, which move entire modified segments when any portion of the segment is accessed. We show that Tapeworm eliminates 85% of remote misses, reduces message traffic by 63%, and improves performance by an average of 29% for our application suite.
Editorial
Authors: Hodgins Jessica
Published: July 2002

I'm very pleased to have the opportunity to take over as editor-in-chief after Holly Rushmeier's strong leadership of the past three years. ACM has made a big effort to get TOG back on schedule after the delays caused by changing to a new publication system. With this issue, we are almost on schedule again and the backlog of accepted papers is significantly reduced. I hope to further shorten the time the return reviews to authors and to get accepted paper to readers. As part of that effort, I have asked Steve Fortune for Bell Labs, John Hart from Washington State, Joe Marks from MERL, and Jorg Peters from the University of Florida to be new members of the editorial board to replace those who retired with the end of Holly's term.

I expect that we'll see significant changes in the role of journals during my three-year term. Right now, journals utilize peer reviews and a revision cycle to provide accreditation to research, but this process is tied to a particular distribution medium and requires financial support in the form of subscription fees. With the increasing use of web-baed publishing, I expect that the accreditation and distribution functions will begin to separate. Accreditation will continue to play an important role in scientific reputations and academic careers, while the publication media will become far more diverse. This diversification is particularly important for graphics because many of its important results are not represented well on paper. TOG has moved in this direction with a web page that is expertly maintained by Eric Haines and contains occasional supplemental material (http://www.acm.org./tog/). If TOG is to represent the true breadth of graphics, however, we will have to make much more of an effort in this direction.

During the next three years, we will almost certainly see significant changes in graphics as well. Clearly, the field is expanding beyond the creation of beautiful and useful images and image sequences.

New emphases include increasingly realistic physical modeling, interactive worlds, and nonvisual modalities. Graphics is a fascinating field, in part because researchers are able to adopt and adapt new ideas from so many other fields: art, vision, physics, materials science, control, optimization and biomechanics. I look forward to the innovative and creative work that the community will submit to TOG during the next three years.
Periodification scheme
Authors: kutyłowski Mirosław , Loryś Krzysztof , Oesterdiekhoff Brigitte , Wanka Rolf
Published: July 2002

We consider comparator networks
M
that are used repeatedly: while the output produced by
M
is not sorted, it is fed again into
M
. Sorting algorithms working in this way are called
periodic
. The number of parallel steps performed during a single run of
M
is called its
period
, the sorting
time
of
M
is the total number of parallel steps that are necessary to sort in the worst case. Periodic sorting networks have the advantage that they need little hardware (control logic, wiring, area) and that they are adaptive. We are interested in comparator networks of a constant period, due to their potential applications in hardware design.

Previously, very little was known on such networks. The fastest solutions required time
O(n
ε
) where the depth was roughly 1/ε. We introduce a general method called
periodification scheme
that converts automatically an arbitrary sorting network that sorts
n
items in time
T(n
) and that has layout area
A(n
) into a sorting network that has period 5, sorts ***(
n
•
T
(
n
) items in time
O(T(<n
)• log
n
), and has layout area
O(A(n)
) •
T(n
)). In particular, applying this scheme to Batcher's algorithms, we get practical period 5 comparator networks that sort in time
O
(log
3
n
). For theoretical interest, one may use the AKS netork resulting in a period 5 comparator network with runtime
O
(log
2
n
).
A case of too much precision
Authors: Synge Michael J.
Published: July 2002

I was so impressed and pleased by RDNUM, A. Hassitt's General-Purpose Input Routine [
Comm. ACM 7
, 6 (June 1964), 350-355], that I have transliterated it into FORTRAN II for the IBM 7094. In doing this I stumbled across solutions to a decimal-to-binary conversion problem that has long bugged FORTRAN. Let me hasten to say, before C. H. Weisert [Letter to the Editor,
Comm. ACM 7
, 5 (May 1964), 314] castigates me for discussing 7090 problems in your columns, that the matter discussed here is relevant to any machine conversion algorithm.
Scanning text with a 1401
Authors: Baker James J.
Published: July 2002

Scanning text on a computer, as in forming word lists or editing, usually involves isolating and identifying certain characters or classes of characters. For example, if we scan text to form a list of words, the definition of “word” might be “everything between two blanks that isn't punctuation.” To program this, we must be able to identify a single character (blank) and a class of characters (punctuation). In a computer such as the 7090, where characters are numbers, we can put a character into an index register and index a table of transfers (one table-entry per character), thus getting to a section of code appropriate for handling that particular character. This is not natural for the 1401 because characters are not numbers and turning them into numbers is a bit clumsy. However, 1401 addresses are a combination of numbers and other characters, and we can use characters directly to reference certain addresses provided we can turn all characters (there are 64) into the 40 that are allowable in specifying an address.
A comparative study of computer programs for integrating differential equations
Authors: Fox Phyllis
Published: July 2002

A study comparing the performance of several computer programs for integrating systems of ordinary differential equations is reported. The integration methods represented include multistep methods (predictor-correctors), single-step methods (Runge-Kutta) and extrapolation methods (both polynomial and rational). The testing procedure is described together with the evaluation criteria applied. A set of test problems on which the programs were tested is included in an appendix. For the particular problems and criteria used in the investigation it was found that a program based on rational extrapolation showed the best performance.
Sequential formula translation
Authors: Samelson K. , Bauer F. L.
Published: July 2002

The syntax of an algorithmic language such as ALGOL is conveniently described as a sequence of states indicated by an element called cellar. Transitions are controlled by admissible state-
s
ymbol pairs which may be represented by a transition matrix. This description of syntax furnishes at the same time an extremely simple rule for translating into machine programs statements in the algorithmic language. Sequential treatment, however, is not feasible in the case of certain optimizing processes such as recursive address calculation.
Program development by stepwise refinement
Authors: Wirth Niklaus
Published: July 2002

The creative activity of programming—to be distinguished from coding—is usually taught by examples serving to exhibit certain techniques. It is here considered as a sequence of design decisions concerning the decomposition of tasks into subtasks and of data into data structures. The process of successive refinement of specifications is illustrated by a short but nontrivial example, from which a number of conclusions are drawn regarding the art and the instruction of programming.