bluuebunny/crossref_metadata_2025 huggingface dataset:
EFFECTS OF HYDROGEN GAS FLOW RATIO ON THE QUALITY OF NANO-DIAMOND FILMS
Authors: Wang S. G. , Zhang Q. , Yang D. J. , Yoon S. F. , Ahn J. , Gan B.
Published: July 2002

In this paper, we studied the effects of hydrogen gas flow ratio of [H2]/[N2 + CH4 + H2] on the quality of nanometer diamond (nano-diamond) films prepared by microwave plasma enhanced chemical vapor deposition method. Nano-diamond films were deposited on the silicon substrates from a gaseous mixture of nitrogen, methane and hydrogen. The experimental results show that if only using a gaseous mixture of nitrogen and methane, although we can obtain nano-diamond films with a grain size of about 5nm, the diamond films contain much non-diamond components. With hydrogen addition, and with increasing the hydrogen gas flow ratio from 1 to 10%, the non-diamond components in the films are significantly reduced and the grain size of the films increases from 5nm to 60nm. However optical transmittance of the films increases with increasing hydrogen gas flow ratio from 1 to 7% because of an improvement of film quality, and then decreases with further increasing hydrogen gas flow ratio owing to the increase of film roughness.
PREPARATION OF NANOCRYSTALLINE DIAMOND FIELD EMITTERS USING POROUS SILICON AS HOST MATRIXES
Authors: CAI RANGQI , ZHANG YATAO , YANG ZHONGSHI , HE DEYAN , CHEN GUANGHUA
Published: July 2002

Nanocrystalline diamond field emitters were deposited by microwave plasma-enhanced chemical vapor deposition using porous Si as host matrixes. Scanning electron microscopy observations showed that the nuclei of diamond occurred at the edges of the etched pores, and the nanoscale diamond grains were partly embedded into the pores of the porous Si. The structure was beneficial to the electron field emission. The electron emission became more stable and the emission current was significantly enchanced comparing with those of the diamond films deposited on Si substrates scratched by diamond powder.
AB-INITIO CALCULATIONS OF SUPERCONDUCTING PROPERTIES OF YBa2Cu3O7
Authors: ZHAO G. L. , BAGAYOKO D.
Published: July 2002

We present ab-initio calculations for the electronic structure and superconducting properties of YBa 2 Cu 3 O 7 (YBCO). The electronic structure was calculated using a self-consistent ab-initio LCAO method. We solved the anisotropic Eliashberg gap equation numerically. The strong coupling of the high energy optical phonons around 60-73 meV, with the electrons at the Fermi surface, leads to a high Tc in YBCO. The calculated Tc is about 89 K for μ*=0.1. The good agreement of the calculated results with experimental measurements and the ab-initio nature of the calculations support the scenario of an anisotropic s-wave superconductor for YBCO.
ENHANCEMENT OF SUPERCONDUCTIVE CRITICAL TEMPERATURES IN ALMOST EMPTY OR FULL BANDS IN TWO DIMENSIONS: POSSIBLE RELEVANCE TO β-HfNCl, C60 AND MgB2
Authors: KOHMOTO MAHITO , CHANG IKSOO , FRIEDEL JACQUES
Published: July 2002

We examine the possibility of enhancement of superconductive critical temperature in two-dimensions using the BCS theory. When the Fermi level is near an edge of a band the density of states (DOS) is not particularly high but k-dependent contribution to DOS (electron density on the Fermi surface) has a divergent peak at the bottom or top of the band (van Hove singularity). The attractive phonon-mediated interaction depends on q (momentum transfer) due to finite screening (non-local interaction). Enhancement of the critical temperatures is shown for the first time in this case. The results are qualitatively consistent with the superconductive behaviors of HfNCl (T c ≤ 25 K ) and ZrNCl (T c ≤ 15 K ), C 60 with a field-effect transistor configuration (T c = 52 K ), and MgB 2 (T c ≈ 40 K ) which have unexpectedly high critical temperatures.
GROWTH AND CHARACTERIZATION OF p-Type GaAs LAYERS USING ATOMIC HYDROGEN AS A REAGENT
Authors: SILVA-ANDRADE F. , CHÁVEZ F. , TENORIO F. , MORALES N. , DE LEON J. I. BECERRA PONCE , PEÑA-SIERRA R. , BRAVO-GARCÍA Y. E.
Published: July 2002

Atomic hydrogen has been found to have a great number of useful applications in the technological field of semiconducting materials. It has been used as a reagent in the epitaxial growth processes to control the incorporation of residual impurities. Atomic hydrogen can react with GaAs thus producing Ga- and As- hydrogen volatile species in controlled conditions. The atomic hydrogen can be produced in a chemical vapor deposition chamber using a hot tungsten filament. In this work we report the results of a study on GaAs layers grown using the close space vapor deposition technique with atomic hydrogen as a reagent. The conductivity type of the grown layers is closely related to the conductivity type of the GaAs source. We have grown p-type GaAs layers with l×1018 cm-3 hole concentration using GaAs sources with the same acceptor concentration. 10 K photoluminesence measurements were nlade on the source and the epitaxial GaAs layers. The PL spectra revealed that the residual impurities in the GaAs layers were originated from the source. The mirror like appearance of the grown layers as well as their electrical and optical characteristics demonstrate they can be used in the manufacture of GaAs semiconductor devices.
OPTICAL DOPING OF NITRIDES BY ION IMPLANTATION
Authors: ALVES E. , LORENZ K. , VIANDEN R. , BOEMARE C. , SOARES M. J. , MONTEIRO T.
Published: July 2002

A series of rare earth elements (RE) were implanted in GaN epilayers to study the lattice site location and optical activity. Rutherford backscattering spectrometry in the channeling mode (RBS/C) was used to follow the damage behavior in the Ga sublattice and the site location of the RE. For all the implanted elements (Ce, Pr, Dy, Er, and Lu) the results indicate the complete substitutionality on Ga sites after rapid thermal annealing at 1000°C for 2 min. The only exception occurs for Eu, which occupies a Ga displaced site. Annealing at 1200°C in nitrogen atmosphere at a pressure of 1GPa is necessary to achieve the complete recovery of the damage in the samples. After annealing the recombination processes of the implanted samples were studied by above and below band gap excitation. For Er implanted samples besides the 1.54 μm emission green and red emissions are also observed. Red emissions from 5 D 0 → 7 F 2 and 3 P 0 → 3 F 2 transitions were found in Eu and Pr implanted samples even at room temperature.
APPLICATION OF ESR TO HIGH-Tc SUPERCONDUCTORS AND RELATED MATERIALS IV: ALKALI K DOPING EFFECTS ON THE SUPERCONDUCTING CHARACTERISTICS OF K3C60
Authors: SUGAWARA K. , OHYA N. , ARAI N. , ICHIMURA S. , YAMAMOTO K. , HIROSE H.
Published: July 2002

Several samples of K 3 C 60 have been made by the calcination of C 60 powder plus K flakes in evacuated quartz tubes at temperatures between 100°C and 700°C for 24 hours. The non-resonant microwave absorption (NRMA) measurements have been done below T c for these samples. From the linewidths and intensities of the NRMA signals, the superconducting properties (T c superconducting volume fraction and vortex size) have been studied as a function of the calcination temperature.
PHOTON SHOT NOISE
Authors: BEENAKKER C. W. J. , PATRA M.
Published: July 2002

A recent theory is reviewed for the shot noise of coherent radiation propagating through a random medium. The Fano factor [Formula: see text] (the ratio of the noise power and the mean transmitted current) is related to the scattering matrix of the medium. This is the optical analogue of Büttiker's formula for electronic shot noise. Scattering by itself has no effect on the Fano factor, which remains equal to 1 (as for a Poisson process). Absorption and amplification both increase the Fano factor above the Poisson value. For strong absorption [Formula: see text] has the universal limit [Formula: see text], with f the Bose–Einstein function at the frequency of the incident radiation. This is the optical analogue of the one-third reduction factor of electronic shot noise in diffusive conductors. In the amplifying case the Fano factor diverges at the laser threshold, while the signal-to-noise ratio [Formula: see text] reaches a finite, universal limit.
NONTWIST AREA PRESERVING MAPS WITH REVERSING SYMMETRY GROUP
Authors: PETRISOR EMILIA
Published: July 2002

The aim of this paper is to give a theoretical explanation of the rich phenomenology exhibited by nontwist mappings of the cylinder, in numerical experiments reported in [del-Castillo et al., 1996; Howard & Humpherys, 1995], and to give new insights on the dynamics of nontwist standard-like maps. Our approach is based on the reversing symmetric properties of the nontwist standard-like systems. We relate the bifurcation of periodic orbits of such maps to their position with respect to a group-invariant circle, and to a critical circle, at whose points the twist property is violated. Moreover, we show that appearance of the meanders, i.e. homotopically nontrivial invariant circles of the cylinder, that are not graphs of real functions of angular variable, is a global bifurcation of a curve on the cylinder, with nodal-type singularities, and invariant with respect to the action of a reversing symmetry group.
ANALYZING DISPLACEMENT TERM'S MEMORY EFFECT IN A VAN DER POL TYPE BOUNDARY CONDITION TO PROVE CHAOTIC VIBRATION OF THE WAVE EQUATION
Authors: CHEN GOONG , HSU SZE-BI , HUANG TINGWEN
Published: July 2002

Consider the one-dimensional wave equation on a unit interval, where the left-end boundary condition is linear, pumping energy into the system, while the right-end boundary condition is self-regulating of the van der Pol type with a cubic nonlinearity. Then for a certain parameter range it is now known that chaotic vibration occurs. However, if the right-end van der Pol boundary condition contains an extra linear displacement feedback term, then it induces a memory effect and considerable technical difficulty arises as to how to define and determine chaotic vibration of the system. In this paper, we take advantage of the extra margin property of the reflection map and utilize properties of homoclinic orbits coupled with a perturbation approach to show that for a small parameter range, chaotic vibrations occur in the sense of unbounded growth of snapshots of the gradient. The work also has significant implications to the occurrence of chaotic vibration for the wave equation on a 3D annular domain.
CHAOTIC BURST IN THE DYNAMICS OF A CLASS OF NONCRITICALLY FINITE ENTIRE FUNCTIONS
Authors: KAPOOR G. P. , PRASAD M. GURU PREM
Published: July 2002

Devaney [1991] and Devaney and Durkin [1991] exhibited the chaotic burst in the dynamics of certain critically finite entire transcendental functions such as λ exp z and iλ cos z. The Julia set of critically finite entire function Eλ(z)=λ ez for 0<λ<(1/e) is a nowhere dense subset entirely contained in the right half-plane, while it explodes and equals to the extended complex plane for λ>(1/e), a phenomena referred to as chaotic burst in the dynamics of functions in one parameter family ℰ≡{Eλ: Eλ(z)=λ exp z, λ>0}. In the present work, a class [Formula: see text] of noncritically finite entire functions is introduced and the dynamics of functions in one parameter family [Formula: see text] generated from each function g(z) in the class [Formula: see text] is investigated. It is proved that there exists a real number [Formula: see text] such that bifurcation in the dynamics of functions [Formula: see text] occurs at [Formula: see text]. Further, it is established that chaotic burst occurs in the dynamics of noncritically finite functions in one parameter family [Formula: see text] at the parameter value [Formula: see text]. Finally, certain interesting examples of the family [Formula: see text], viz. [Formula: see text], where [Formula: see text] is the well-known modified Bessel function of zero order and [Formula: see text] , where [Formula: see text] with fixed k=1, 2,… and [Formula: see text] are provided.
CHAOTIC NEURAL FUZZY ASSOCIATIVE MEMORY
Authors: CHAN HUBERT Y. , ŻAK STANISLAW H.
Published: July 2002

A chaotic neuron model with the linear saturating activation function is analyzed. The model accounts for the property of relative refractoriness, that is, gradual recovery of responsiveness of a biological neuron after a stimulus is applied to the neuron. A neural network model composed of chaotic neurons with the linear saturating activation functions, which includes the generalized Brain-State-in-a-Box (gBSB) model as a special case, is proposed and analyzed. The proposed model is then used to implement associative memory. The existence and stability of equilibrium points of the model are analyzed. Fuzzy logic is used to tune associative memory parameters for the purpose of directing the network trajectory to visit memory patterns with sought features. Simulation results are presented to illustrate the effectiveness of the memory retrieval capability.
A SIMPLE ALGORITHM FOR COMPUTING THE GLOBAL CRYSTAL BASIS OF AN IRREDUCIBLE Uq(sln)-MODULE
Authors: LECLERC BERNARD , TOFFIN PHILIPPE
Published: July 2002

We describe a simple algorithm for computing Kashiwara's global crystal basis of a finite-dimensional irreducible representation of Uq(sln).

Résumé: Nous décrivons un algorithme simple pour calculer la base cristalline globale de Kashiwara d'une représentation irréductible de dimension finie de Uq(sln).
A POLYNOMIAL TIME ALGORITHM FOR LOCAL TESTABILITY AND ITS LEVEL
Authors: TRAHTMAN A. N.
Published: July 2002

A locally testable semigroup S is a semigroup with the property that for some non-negative integer k, called the order or level of local testability, two words u and v in some set of generators for S are equal in the semigroup if (1) the prefix and suffix of the words of length k coincide, and (2) the set of intermediate substrings of length k of the words coincide. The local testability problem for semigroups is, given a finite semigroup, to decide, if the semigroup is locally testable or not.

Recently, we introduced a polynomial time algorithm for the local testability problem and to find the level of local testability for semigroups based on our previous description of identities of k-testable semigroups and the structure of locally testable semigroups.

The first part of the algorithm we introduce solves the local testability problem.

The second part of the algorithm finds the order of local testability of a semigroup. The algorithm is of order n2, where n is the order of the semigroup.
MATHEMATICAL MODELLING AND SIMULATION OF NON-ISOTHERMAL CRYSTALLIZATION OF POLYMERS
Authors: BURGER MARTIN , CAPASSO VINCENZO
Published: July 2002

This paper is devoted to the study of mathematical problems arising in the modelling of nonisothermal polymer crystallization under industrial conditions. A review of the hybrid stochastic-deterministic modelling procedure, which yields an averaged model,5,8 is given and supplied by the study of mathematical problems arising from it.

Furthermore, multiple scale effects in the crystallization process are studied using different scalings, focussing either on the heat conduction or on the crystallization part. It is shown that in the limit of fast nucleation and slow growth, the model is equivalent to a direct extension of the classical Avrami–Kolmogorov model equations.

In addition, numerical simulations are presented to illustrate the behavior during crystallization. Finally, open questions from mathematical and engineering view points are discussed.
MODELLING OF THE IMMUNE RESPONSE: CONCEPTUAL FRAMEWORKS AND APPLICATIONS
Authors: DE ANGELIS E. , MESIN L.
Published: July 2002

This paper deals with the modelling of the immune response to the evolution of the progression of endothelial cells which have lost their differentiation and start their evolution toward methastatic states. The aim of this paper is to design a general mathematical framework toward modelling the so-called kinetic cellular theory. Some specific models are proposed within the above framework and suitable simulations are developed with special attention to bifurcation analysis.
EXTRACTING WEB USER PROFILES USING RELATIONAL COMPETITIVE FUZZY CLUSTERING
Authors: NASRAOUI OLFA , FRIGUI HICHEM , KRISHNAPURAM RAGHU , JOSHI ANUPAM
Published: July 2002

The proliferation of information on the World Wide Web has made the personalization of this information space a necessity. An important component of Web personalization is to mine typical user profiles from the vast amount of historical data stored in access logs. In the absence of any a priori knowledge, unsupervised classification or clustering methods seem to be ideally suited to analyze the semi-structured log data of user accesses. In this paper, we define the notion of a "user session" as being a temporally compact sequence of Web accesses by a user. We also define a new distance measure between two Web sessions that captures the organization of a Web site. The Competitive Agglomeration clustering algorithm which can automatically cluster data into the optimal number of components is extended so that it can work on relational data. The resulting Competitive Agglomeration for Relational Data (CARD) algorithm can deal with complex, non-Euclidean, distance/similarity measures. This algorithm was used to analyze Web server access logs successfully and obtain typical session profiles of users.
MAIN SEQUENCE-LIKE STARS WITH SOLITONIC CORES IN EFFECTIVE GRAVITY MODELS
Authors: ROOPRAI NIMMI , LOHIYA DAKSH
Published: July 2002

Lee–Wick type nontopological solitons (NTS's) are known to arise in a generic class of nonminimally coupled theories. Size of these solutions depend upon the nature and the amount of their associated conserved charge. Such NTS's would have characteristic features and would represent novel astrophysical objects. We explore the possibility of having main sequence stars condensing around small NTS's. In particular, if such an NTS is embedded in the radiative zone of a star, the exterior attributes could be indistinguishable from those of a normal star. Possible application to stellar modeling is explored.
A MODEL FOR VECTOR TRANSMITTED DISEASES WITH SATURATION INCIDENCE
Authors: ESTEVA LOURDES , MATIAS MARIANO
Published: July 2002

A model for a disease that is transmitted by vectors is formulated. All newborns are assumed susceptible, and human and vector populations are assumed to be constant. The model assumes a saturation effect in the incidences due to the response of the vector to change in the susceptible and infected host densities. Stability of the disease free equilibrium and existence, uniqueness and stability of the endemic equilibrium is investigated. The stability results are given in terms of the basic reproductive number R0.
HIGHER-ORDER MASS-LUMPED FINITE ELEMENTS FOR THE WAVE EQUATION
Authors: MULDER W. A.
Published: July 2002

The finite-element method (FEM) with mass lumping is an efficient scheme for modeling seismic wave propagation in the subsurface, especially in the presence of sharp velocity contrasts and rough topography. A number of numerical simulations for triangles are presented to illustrate the strength of the method. A comparison to the finite-difference method shows that the added complexity of the FEM is amply compensated by its superior accuracy, making the FEM the more efficient approach.
MODELING AND RELIABILITY PREDICTION FOR THE STEP-STRESS DEGRADATION MEASUREMENTS USING NEURAL NETWORKS METHODOLOGY
Authors: CHANG DONG SHANG , CHIU CHIH-CHOU , JIANG SHWU-TZY
Published: July 2002

Rapidly evolving accelerated degradation testing (ADT) has provided an efficient channel for reliability assessment without the labor of conventional life testing that observations are complete or incomplete data. In step-stress loading, a specimen is subjected to successively higher level stress until an appropriate termination time. All specimens go through the same specified pattern of stress levels and testing time. A step-stress degradation testing (SSDT) is corresponding to collect the degradation measurements over time from a step-stress life testing before any specimen fail. The advantages of SSDT may shorten the testing time and reduce the test units compared to ADT. Conventional statistical approach for modeling the step-stress degradation process may be complicated. In this paper, we address a nonparametric approach by applying the methodology of neural networks to calibrate the step-stress degradation measurements and conducting the reliability prediction at use condition. A light emitting diode (LED) example is given to illustrate the implementation procedure.
ULNAR GROOVE PLASTY FOR FRICTION NEUROPATHY AT THE ELBOW
Authors: Tsujino Akihito , Ochiai Naoyuki
Published: July 2002

In this paper, we report on a new operation for ulnar neuropathy caused by friction at the elbow. The operation consists of ulnar groove plasty proximal to the cubital tunnel. The ulnar nerve is replaced into this reconstructed groove. Patients are relieved of discomfort, and motor and sensory functions are recovered. The nerve is kept stable throughout the full range of elbow motion and showed neither irritation nor adhesion. Friction ulnar neuropathy is traditionally treated by anterior transpositon or medial epicondylectomy. The ulnar nerve may become entrapped in scar tissue after these operations. We believe that this anatomical position is optimum for the nerve and that this procedure is essential for treatment of friction neuropathy.
ULTRASOUND IMAGING OF OCCULT GLOMUS TUMOURS OF THE FINGERTIP
Authors: Wheen D.J. , Conolly W.B. , Read J.W.
Published: July 2002

Small glomus tumours of the hand are notoriously difficult to diagnose. There is often the classical triad of symptoms, with no localising signs. Without precise localisation, surgical planning is also difficult. In 12 patients, preoperative high resolution ultrasound imaging has been used to assist with the diagnosis and localisation of these tumours. Three patients had undergone previous surgery. All tumours were beyond the distal interphalangeal joint. The average maximum dimension of lesions was 5 mm (2–13 mm). A 93% true positive rate of detection was found. Ultrasound was also able to accurately localise the site of the tumour preoperatively.
PROCLETS: A FRAMEWORK FOR LIGHTWEIGHT INTERACTING WORKFLOW PROCESSES
Authors: VAN DER AALST W. M. P. , BARTHELMESS P. , ELLIS C. A. , WAINER J.
Published: July 2002

The focus of traditional workflow management systems is on control flow within one process definition. The process definition describes how a single case (i.e. workflow instance) in isolation is handled. For many applications this paradigm is inadequate. Interaction between cases to support communication and collaboration is at least as important. This paper introduces and advocates the use of interacting proclets, i.e. lightweight workflow processes. By promoting interactions to first-class citizens it is possible to model complex workflows in a more natural manner. In addition, the expressive power and flexibility are improved compared to the more traditional workflow modeling languages.
TELCO's Small Car
Authors: Venugopal R.
Published: July 2002

TELCO is the leading manufacturer of commercial vehicles (trucks) in India. In 1998, TELCO succeeded in manufacturing a small car of international standards without financial or technological collaboration with any leading foreign car manufacturer. This case deals with TELCO's success in its small car project and the challenges that lie ahead. It highlights the role played by creative resource leverage in the success of firms from developing countries in a global environment.
QUANTUM TRIGONOMETRY
Authors: GUSTAFSON KARL
Published: July 2002

Our purpose here is to establish that a general operator trigonometry created by us 30 years ago provides a natural geometry and useful tool for certain situations occurring in quantum probability. In particular we will embed the Bell–Wigner–Accardi theory of quantum spin systems into this operator trigonometry. We will also establish a new connection of the operator trigonometry to CP symmetry violation. We begin with a hopefully helpful brief history starting with the famous Einstein–Podolsky–Rosen gedankenexperiment paper (1935). We close with a short discussion of possible future developments.
STRATEGIC BEHAVIOR AND INFORMATION TRANSMISSION IN A STYLIZED (SO-CALLED CHINOS) GUESSING GAME
Authors: PASTOR-ABIA LUIS , PÉREZ-JORDÁ JOSÉ M. , SAN-FABIÁN EMILIO , LOUIS ENRIQUE , VEGA-REDONDO FERNANDO
Published: July 2002

A guessing game very popular in some European countries involves several players hiding in their hands a number of coins (or pebbles) between zero and three, then attempting to guess in turn the total number of coins in the hands of everyone, with the restriction that no player can repeat the guess issued by any predecessor. After a full round, the player, if any, who guesses correctly wins. Of course, rounds without a winner are also possible, in which case a new round is started afresh. The purpose of the present article is to present an analysis of this game (called Chinos in Spain, as a perturbation of "chinas", i.e. pebbles), and some of its possible variants. Our primary aim is to show its potential to shed light on some issues of strategic behavior and information transmission that seem very germane to some social and economic problems.
An ACM response: the scope and directions of Computer Science
Authors: Simons Barbara , Frailey Dennis J. , Turner A. Joe , Zweben Stuart H. , Denning Peter J.
Published: July 2002

The National Research Council's Computer Science and Telecommunications Board (CSTB) chartered a two-year study on the scope and directions of computer science. As part of this study, ACM was asked to provide input on three important questions, the answers to which could have significant impact on the future direction of our discipline and profession.
Electronic social fields in bureaucracies
Authors: Perin Constance
Published: July 2002

Advanced computer tools designed to facilitate collaboration in a common task or across functions have had a remarkably disappointing record of diffusion and adoption [16]. Technologies that are unresponsive to users needs will not find their markets. Groupware such as electronic mail, conferencing, and on-line editing, however, has an apparently natural affinity to the team and project work of salaried professional employees.
An algorithm for generating NC tool paths for arbitrarily shaped pockets with islands
Authors: Hansen Allan , Arbab Farhad
Published: July 2002

In this paper we describe algorithms for generating NC tool paths for machining of arbitrarily shaped 2 l/2 dimensional pockets with arbitrary islands. These pocketing algorithms are based on a new offsetting algorithm presented in this paper. Our offsetting algorithm avoids costly two-dimensional Boolean set operations, relatively expensive distance calculations, and the overhead of extraneous geometry, such as the Voronoi diagrams, used in other pocketing algorithms.
Gross motion planning—a survey
Authors: Hwang Yong K. , Ahuja Narendra
Published: July 2002

Motion planning is one of the most important areas of robotics research. The complexity of the motion-planning problem has hindered the development of practical algorithms. This paper surveys the work on gross-motion planning, including motion planners for point robots, rigid robots, and manipulators in stationary, time-varying, constrained, and movable-object environments. The general issues in motion planning are explained. Recent approaches and their performances are briefly described, and possible future research directions are discussed.
The minimum consistent DFA problem cannot be approximated within any polynomial
Authors: Pitt Leonard , Warmuth Manfred K.
Published: July 2002

The minimum consistent DFA problem is that of finding a DFA with as few states as possible that is consistent with a given sample (a finite collection of words, each labeled as to whether the DFA found should accept or reject). Assuming that P ≠ NP, it is shown that for any constant
k
, no polynomial-time algorithm can be guaranteed to find a consistent DFA with fewer than

opt
k

states, where
opt
is the number of states in the minimum state DFA consistent with the sample. This result holds even if the alphabet is of constant size two, and if the algorithm is allowed to produce an NFA, a regular expression, or a regular grammar that is consistent with the sample. A similar nonapproximability result is presented for the problem of finding small consistent linear grammars. For the case of finding minimum consistent DFAs when the alphabet is not of constant size but instead is allowed to vary with the problem specification, the slightly stronger lower bound on approximability of
opt

(1-ϵ)log log
opt

is shown for any ϵ > 0.
Page placement algorithms for large real-indexed caches
Authors: Kessler R. E. , Hill Mark D.
Published: July 2002

When a computer system supports both paged virtual memory and large real-indexed caches, cache performance depends in part on the main memory page placement. To date, most operating systems place pages by selecting an arbitrary page frame from a pool of page frames that have been made available by the page replacement algorithm. We give a simple model that shows that this naive (arbitrary) page placement leads to up to 30% unnecessary cache conflicts. We develop several page placement algorithms, calledcareful-mapping algorithms, that try to select a page frame (from the pool of available page frames) that is likely to reduce cache contention. Using trace-driven simulation, we find that careful mapping results in 10–20% fewer (dynamic) cache misses than naive mapping (for a direct-mapped real-indexed multimegabyte cache). Thus, our results suggest that careful mapping by the operating system can get about half the cache miss reduction that a cache size (or associativity) doubling can.
An investigation of content representation using text grammars
Authors: Rama D. V. , Srinivasan Padmini
Published: July 2002

We extend prior work on a model for natural language text representation and retrieval using a linguistic device called text grammar. We demonstrate the value of this approach in accessing relevant items from a collection of empirical abstracts in a medical domain. The advantage, when compared to traditional keyword retrieval, is that this approach is a significant move towards knowledge representation and retrieval. Text representation in this model includes keywords and their conceptual roles in the text. In particular, it involves extracting TOPIC predicates representing the research issue addressed and DESIGN predicates representing important methodological features of the empirical study. Preliminary experimentation shows that keywords exhibit a variety of text-grammar roles in a text database. Second, as intuitively expected, retrieval using TOPIC predicates identifies a smaller subset of texts than Boolean retrieval does. These empirical results along with the theoretical work indicate that the representation and retrieval strategies proposed have a significant potential. Finally, EMPIRICIST, a prototype system is described. In it the text representation predicates are implemented as a network while retrieval is through constrained-spreading activation strategies.
A Bernoulli factory
Authors: Keane M. S. , O'Brien George L.
Published: July 2002

Necessary and sufficient conditions on a function f(p) are given for the existence of a simulation procedure to simulate a Bernoulli variable with success probability f(p) from independent Bernoulli variables with success probability p, with p being constrained to lie in a subset
P
of [0,1] but otherwise unknown
—Authors' Abstract
.
Precise executable interprocedural slices
Authors: Binkley David
Published: July 2002

The notion of a
program slice
, originally introduced by Mark Weiser, is useful in program debugging, automatic parallelization, program integration, and software maintenance. A slice of a program is taken with respect to a program point
p
and a variable
x
; the slice consists of all statements of the program that might affect the value of
x
at point
p
. An interprocedural slice is a slice of an entire program, where the slice crosses the boundaries of procedure calls.

Weiser's original interprocedural-slicing algorithm produces imprecise slices that are executable programs. A recent algorithm developed by Horwitz, Reps, and Binkley produces more precise (smaller) slices by more accurately identifying those statements that might affect the values of
x
at point
p
. These slices, however, are not executable. An extension to their algorithm that produces more precise executable interprocedural slices is described together with a proof of correctness for the new algorithm.
Automated resolution of semantic heterogeneity in multidatabases
Authors: Bright M. W. , Hurson A. R. , Pakzad S.
Published: July 2002

A multidatabase system provides integrated access to heterogeneous, autonomous local databases in a distributed system. An important problem in current multidatabase systems is identification of semantically similar data in different local databases. The Summary Schemas Model (SSM) is proposed as an extension to multidatabase systems to aid in semantic identification. The SSM uses a global data structure to abstract the information available in a multidatabase system. This abstracted form allows users to use their own terms (imprecise queries) when accessing data rather than being forced to use system-specified terms. The system uses the global data structure to match the user's terms to the semantically closest available system terms. A simulation of the SSM is presented to compare imprecise-query processing with corresponding query-processing costs in a standard multidatabase system. The costs and benefits of the SSM are discussed, and future research directions are presented.
User interface software tools
Authors: Myers Brad A.
Published: July 2002

Almost as long as there have been user interfaces, there have been special software systems and tools to help design and implement the user interface software. Many of these tools have demonstrated significant productivity gains for programmers, and have become important commercial products. Others have proven less successful at supporting the kinds of user interfaces people want to build. This article discusses the different kinds of user interface software tools, and investigates why some approaches have worked and others have not. Many examples of commercial and research systems are included. Finally, current research directions and open issues in the field are discussed.
A randomized linear-time algorithm to find minimum spanning trees
Authors: Karger David R. , Klein Philip N. , Tarjan Robert E.
Published: July 2002

We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.
Fractal views
Authors: Koike Hideki
Published: July 2002

Computer users often must view large amounts of information through video displays which are physically limited in size. Although some methods, which automatically display/erase information units based on their degrees of importance, have been proposed, they lack an ability to keep the total amount of displayed information nearly constant. We propose a new method for information display based on fractal theory. By regarding the information structures used in computers as complex objects, we can abstract these objects as well as control their amount. Using our method, (1) the total amount of information is kept nearly constant even when users change their focuses of attention and (2) this amount can be set flexibly. Through mathematical analysis, we show our method's ability to control the amount. An application to program display is also shown. When this method is applied to the display of structured programs, it provides fisheye-like views which integrate local details around the focal point and major landmarks further away.
Going digital
Authors: Levy David M. , Marshall Catherine C.
Published: July 2002

What are digital libraries, how should they be designed, how will they be used, and what relationship will they bear to what we now call “libraries”? Although we cannot hope to answer all these crucial questions in this short article, we do hope to encourage, and in some small measure to shape, the dialog among computer scientists, librarians, and other interested parties out of which answers may arise. Our contribution here is to make explicit, and to question, certain assumptions that underlie current digital library efforts. We will argue that current efforts are limited by a largely unexamined and unintended allegiance to an idealized view of what libraries have been, rather than what they actually are or could be. Since these limits come from current ways of thinking about the problem, rather than being inherent in the technology or in social practice, expanding our conception of digital libraries should serve to expand the scope and the utility of development efforts.
On the minimality and global consistency of row-convex constraint networks
Authors: van Beek Peter , Dechter Rina
Published: July 2002

Constraint networks have been shown to be useful in formulating such diverse problems as scene labeling, natural language parsing, and temporal reasoning. Given a constraint network, we often wish to (i) find a solution that satisfies the constraints and (ii) find the corresponding minimal network where the constraints are as explicit as possible. Both tasks are known to be NP-complete in the general case. Task (1) is usually solved using a backtracking algorithm, and task (ii) is often solved only approximately by enforcing various levels of local consistency. In this paper, we identify a property of binary constraint called
row convexity
and show its usefulness in deciding when a form of local consistency called path consistency is sufficient to guarantee that a network is both minimal and globally consistent. Globally consistent networks have the property that a solution can be found without backtracking. We show that one can test for the row convexity property efficiently and we show, by examining applications of constraint networks discussed in the literature, that our results are useful in practice. Thus, we identify a class of binary constraint networks for which we can solve both tasks (i) and (ii) efficiently. Finally, we generalize the results for binary constraint networks to networks with nonbinary constraints.
Error messages
Authors: Brown P. J.
Published: July 2002

The quality of error messages produced by software used in the field was tested by a simple experiment; it was found to be far from adequate. The results of the experiment are analyzed, and some responses which tend to collaborate the original findings are discussed. Finally, some suggestions are made for improving the quality of error messages.
Data model issues for object-oriented applications
Authors: Banerjee Jay , Chou Hong-Tai , Garza Jorge F. , Kim Won , Woelk Darrell , Ballou Nat , Kim Hyoung-Joo
Published: July 2002

Presented in this paper is the data model for ORION, a prototype database system that adds persistence and sharability to objects created and manipulated in object-oriented applications. The ORION data model consolidates and modifies a number of major concepts found in many object-oriented systems, such as objects, classes, class lattice, methods, and inheritance. These concepts are reviewed and three major enhancements to the conventional object-oriented data model, namely, schema evolution, composite objects, and versions, are elaborated upon. Schema evolution is the ability to dynamically make changes to the class definitions and the structure of the class lattice. Composite objects are recursive collections of exclusive components that are treated as units of storage, retrieval, and integrity enforcement. Versions are variations of the same object that are related by the history of their derivation. These enhancements are strongly motivated by the data management requirements of the ORION applications from the domains of artificial intelligence, computer-aided design and manufacturing, and office information systems with multimedia documents.
Branching time and abstraction in bisimulation semantics
Authors: van Glabbeek Rob J. , Weijland W. Peter
Published: July 2002

In comparative concurrency semantics, one usually distinguishes between
linear time
and
branching time
semantic equivalences. Milner's notion of
observatin equivalence
is often mentioned as the standard example of a branching time equivalence. In this paper we investigate whether observation equivalence really does respect the branching structure of processes, and find that in the presence of the unobservable action τ of CCS this is not the case.

Therefore, the notion of
branching bisimulation equivalence
is introduced which strongly preserves the branching structure of processes, in the sense that it preserves computations together with the potentials in all intermediate states that are passed through, even if silent moves are involved. On closed CCS-terms branching bisimulation congruence can be completely axiomatized by the single axion scheme:
a.(τ.(y+z)+y)=a.(y+z)
(where
a
ranges over all actions) and the usual loaws for strong congruence.

We also establish that for sequential processes observation equivalence is not preserved under refinement of actions, whereas branching bisimulation is.

For a large class of processes, it turns out that branching bisimulation and observation equivalence are the same. As far as we know, all protocols that have been verified in the setting of observation equivalence happen to fit in this class, and hence are also valid in the stronger setting of branching bisimulation equivalence.
The mean square discrepancy of randomized nets
Authors: Hickernell Fred J.
Published: July 2002

One popular family of low dicrepancy sets is the (t, m, s)-nets. Recently a randomization of these nets that preserves their net property has been introduced. In this article a formula for the mean squareL2-discrepancy of (0, m, s)-nets in basebis derived. This formula has a computational complexity of only O(s log(N) + s2) for largeNor s, whereN = bmis the number of points. Moreover, the root mean squareL2-discrepancy of (0, m, s)-nets is show to be O(N-1[log(N)](s-1)/2) asNtends to infinity, the same asymptotic order as the known lower bound for theL2-discrepancy of an arbitrary set.
Latin supercube sampling for very high-dimensional simulations
Authors: Owen Art B.
Published: July 2002

This article introduces Latin supercube sampling (LSS) for very high-dimensional simulations such as arise in particle transport, finance, and queueing. LSS is developed as a combination of two widely used methods: Latin hypercube sampling (LHS) and quasi-Monte Carlo (QMC). In LSS, the input variables are grouped into subsets, and a lower-dimensional QMC method is used within each subset. The QMC points are presented in random order within subsets. QMC methods have been observed to lose effectiveness in high-dimensional problems. This article shows that LSS can extend the benefits of QMC to much higher dimensions, when one can make a good grouping of input variables. Some suggestions for grouping variables are given for the motivating examples. Even a poor grouping can still be expected to do as well as LHS. The article also extends LHS and LSS to infinite-dimensional problems. The paper includes a survey of QMC methods, randomized versions of them (RQMC), and previous methods for extending QMC to higher dimensions. Furthermore it shows that LSS applied with RQMC is more reliable than LSS with QMC.
Randomized binary search trees
Authors: Martínez Conrado , Roura Salvador
Published: July 2002

In this paper, we present randomized algorithms over binary search trees such that: (a) the insertion of a set of keys, in any fixed order, into an initially empty tree always produces a random binary search tree; (b) the deletion of any key from a random binary search tree results in a random binary search tree; (c) the random choices made by the algorithms are based upon the sizes of the subtrees of the tree; this implies that we can support accesses by rank without additional storage requirements or modification of the data structures; and (d) the cost of any elementary operation, measured as the number of visited nodes, is the same as the expected cost of its standard deterministic counterpart; hence, all search and update operations have guaranteed expected cost O(log
n
), but now irrespective of any assumption on the input distribution.
Semistructured messages are surprisingly useful for computer-supported coordination
Authors: Malone Thomas W. , Grant Kenneth R. , Lai Kum-Yew , Rao Ramana , Rosenblitt David
Published: July 2002

This paper argues that using a set of semistructured message templates is surprisingly helpful in designing a variety of computer-based communication and coordination systems. Semistructured messages can help provide automatic aids for (1) composing messages to be sent, (2) selecting, sorting, and prioritizing messages that are received, (3) responding automatically to some messages, and (4) suggesting likely responses to other messages. The use of these capabilities is illustrated in a range of applications including electronic mail, computer conferencing, calendar management, and task tracking. The applications show how ideas from artificial intelligence (such as inheritance and production rules) and ideas from user interface design (such as interactive graphical editors) can be combined in novel ways for dealing with semistructured messages. The final part of the paper discusses how communities can evolve a useful set of message type definitions.
High-precision division and square root
Authors: Karp Alan H. , Markstein Peter
Published: July 2002

We present division and square root algorithm for calculations with more bits than are handled by the floating-point hardware. These algorithms avoid the need to multiply two high-precision numbers, speeding up the last iteration by as much as a factor of 10. We also show how to produce the floating-point number closest to the exact result with relatively few additional operations.
Multidimensional access methods
Authors: Gaede Volker , Günther Oliver
Published: July 2002

Search operations in databases require special support at the physical level. This is true for conventional databases as well as spatial databases, where typical search operations include thepoint query(find all objects that contain a given search point) and theregion query(find all objects that overlap a given search region). More than ten years of spatial database research have resulted in a great variety of multidimensional access methods to support such operations. We give an overview of that work. After a brief survey of spatial data management in general, we first present the class ofpoint access methods, which are used to search sets of points in two or more dimensions. The second part of the paper is devoted tospatial access methodsto handle extended objects, such as rectangles or polyhedra. We conclude with a discussion of theoretical and experimental results concerning the relative performance of various approaches.