bluuebunny/crossref_metadata_2025 huggingface dataset:
ON REACHABILITY AND SAFETY IN INFINITE-STATE SYSTEMS
Authors: IBARRA OSCAR H. , BULTAN TEVFIK , SU JIANWEN
Published: July 2002

We introduce some new models of infinite-state transition systems. The basic model, called a (reversal-bounded) counter machine (CM), is a nondeterministic finite automaton augmented with finitely many reversal-bounded counters (i.e. each counter can be incremented or decremented by 1 and tested for zero, but the number of times it can change mode from nondecreasing to nonincreasing and vice-versa is bounded by a constant, independent of the computation). We extend a CM by augmenting it with some familiar data structures: (i) A pushdown counter machine (PCM) is a CM augmented with an unrestricted pushdown stack. (ii) A tape counter machine (TCM) is a CM augmented with a two-way read/write worktape that is restricted in that the number of times the head crosses the boundary between any two adjacent cells of the worktape is bounded by a constant, independent of the computation (thus, the worktape is finite-crossing). There is no bound on how long the head can remain on a cell. (iii) A queue counter machine (QCM) is a CM augmented with a queue that is restricted in that the number of alternations between non-deletion phase and non-insertion phase on the queue is bounded by a constant. A non-deletion (non-insertion) phase is a period consisting of insertions (deletions) and no-changes, i.e., the queue is idle. We show that emptiness, (binary, forward, and backward) reachability, nonsafety, and invariance for these machines are solvable. We also look at extensions of the models that allow the use of linear-relation tests among the counters and parameterized constants as "primitive" predicates. We investigate the conditions under which these problems are still solvable.
SINK INSERTION FOR MESH IMPROVEMENT
Authors: EDELSBRUNNER HERBERT , GUOY DAMRONG
Published: July 2002

We propose sink insertion as a new technique to improve the mesh quality of Delaunay triangulations. We compare it with the conventional circumcenter insertion technique under three scheduling regimes: incremental, in blocks, and in parallel. Justification for sink insertion is given in terms of mesh quality, numerical robustness, running time, and ease of parallelization.
SZNAJD SOCIAL MODEL ON SQUARE LATTICE WITH CORRELATED PERCOLATION
Authors: MOREIRA A. A. , ANDRADE J. S. , STAUFFER D.
Published: July 2002

The Sznajd model for the spread of opinions is applied to the incipient infinite percolation cluster on the square lattice, with and without power-law correlations for the occupied sites. We trace the phase transition between the two fixed points of all spins up and all spins down.
CREATION AND ANNIHILATION OPERATORS AND COHERENT STATES FOR THE PT-SYMMETRIC OSCILLATOR
Authors: BAGCHI B. , QUESNE C.
Published: July 2002

We construct two commuting sets of creation and annihilation operators for the PT-symmetric oscillator. We then build coherent states of the latter as eigenstates of such annihilation operators by employing a modified version of the normalization integral that is relevant to PT-symmetric systems. We show that the coherent states are normalizable only in the range (0,1) of the underlying coupling parameter α.
OPEN DESCENDANTS OF U(2N) ORBIFOLDS AT RATIONAL RADII
Authors: SCHELLEKENS A. N. , SOUSA N.
Published: July 2002

We construct explicitly the open descendants of some exceptional automorphism invariants of U (2N) orbifolds. We focus on the case N = p1 × p2, p1 and p2 prime, and on the automorphisms of the diagonal and charge conjugation invariants that exist for these values of N. These correspond to orbifolds of the circle with radius R2 = 2p1/p2. For each automorphism invariant we find two consistent Klein bottles, and for each Klein bottle we find a complete (and probably unique) set of boundary states. The two Klein bottles are in each case related to each other by simple currents, but surprisingly for the automorphism of the charge conjugation invariant neither of the Klein bottle choices is the canonical (symmetric) one.
THE CMS ECAL PROJECT – OVERVIEW AND STATUS REPORT
Authors: NESSI-TEDALDI FRANCESCA
Published: July 2002

The status is given of the lead tungstate electromagnetic crystal calorimeter for the CMS detector at the Large Hadron Collider: calorimeter design, development of calorimeter components and results obtained in particle beams are discussed.
ANOMALIES IN WARD IDENTITIES FOR THREE-POINT FUNCTIONS REVISITED
Authors: BATTISTEL O. A. , BATTISTEL O. L.
Published: July 2002

A general calculational method is applied to investigate symmetry relations among divergent amplitudes in a free fermion model. A very traditional work on this subject is revisited. A systematic study of one, two and three-point functions associated to scalar, pseudoscalar, vector and axial-vector densities is performed. The divergent content of the amplitudes are left in terms of five basic objects (external momentum independent). No specific assumptions about a regulator is adopted in the calculations. All ambiguities and symmetry violating terms are shown to be associated with only three combinations of the basic divergent objects. Our final results can be mapped in the corresponding Dimensional Regularization calculations (in cases where this technique could be applied) or in those of Gertsein and Jackiw which we will show in detail. The results emerging from our general approach allow us to extract, in a natural way, a set of reasonable conditions (e.g. crucial for QED consistency) that could lead us to obtain all Ward Identities satisfied. Consequently, we conclude that the traditional approach used to justify the famous triangular anomalies in perturbative calculations could be questionable. An alternative point of view, dismissed of ambiguities, which lead to a correct description of the associated phenomenology, is pointed out.
COUNTEREXAMPLES IN FRACTAL ROUGHNESS ANALYSIS AND THEIR PHYSICAL PROPERTIES
Authors: Pfeifer Peter , Gheorghiu Stefan
Published: July 2002

We disprove the widely held notion that a surface with nontrivial roughness exponents fluctuates at all scales ("structure within structure") and has nontrivial fractal dimension. Strong counterexamples are Cantor staircases, which have nontrivial roughness exponents, do not fluctuate at all, and have trivial fractal dimension. Weak counterexamples fluctuate intermittently and have nontrivial fractal dimension. Characteristic of all counterexamples is: (i) they consist of terraces of all sizes and exhibit scaling over the entire range of terrace sizes. (ii) they have roughness exponents Hq that vary strongly with order q; (iii) they are self affine, but not all affinities are invertible. The strong variation of Hq drives a strongly varying surface response to different external interactions (different interactions are governed by different orders q) and abrupt changes similar to a phase transition, with Hq playing the role of temperature. A summary of this extraordinary functional tunability and its applications is given.
QUANTAL ANDREEV BILLIARDS: SEMICLASSICAL APPROACH TO MESOSCALE OSCILLATIONS IN THE DENSITY OF STATES
Authors: ADAGIDELI İNANÇ , GOLDBART PAUL M.
Published: July 2002

Andreev billiards are finite, arbitrarily-shaped, normal-state regions, surrounded by superconductor. At energies below the superconducting gap, single-quasiparticle excitations are confined to the normal region and its vicinity, the essential mechanism for this confinement being Andreev reflection. This Paper develops and implements a theoretical framework for the investigation of the short-wave quantal properties of these single-quasiparticle excitations. The focus is primarily on the relationship between the quasiparticle energy eigenvalue spectrum and the geometrical shape of the normal-state region, i.e. the question of spectral geometry in the novel setting of excitations confined by a superconducting pair-potential. Among the central results of this investigation are two semiclassical trace formulas for the density of states. The first, a lower-resolution formula, corresponds to the well-known quasiclassical approximation, conventionally invoked in settings involving superconductivity. The second, a higher-resolution formula, allows the density of states to be expressed in terms of: (i) An explicit formula for the level density, valid in the short-wave limit, for billiards of arbitrary shape and dimensionality. This level density depends on the billiard shape only through the set of stationary-length chords of the billiard and the curvature of the boundary at the endpoints of these chords; and (ii) Higher-resolution corrections to the level density, expressed as a sum over periodic orbits that creep around the billiard boundary. Owing to the fact that these creeping orbits are much longer than the stationary chords, one can, inter alia, "hear" the stationary chords of Andreev billiards.
SCALING BETWEEN LOCALIZATION LENGTH AND TC IN DISORDERED YBa2Cu3O6.9
Authors: GAUZZI ANDREA , PAVUNA DAVOR
Published: July 2002

We quantitatively study the effect of growth-induced reduction of long range structural order on the superconducting transition in epitaxial YBa 2 Cu 3 O 6.9 films. The corresponding reduction of structural coherence length rc is determined from the width of X-ray diffraction rocking curves. Tc measurements in the films give evidence for the validity of the empirical scaling relation ΔTc~ rc,ab-2, where ΔTc is the disorder-induced reduction of Tc and rc,ab is the structural coherence length in the ab-plane. To explain this algebraic law we propose a simple phenomenological model based on the disorder-induced localization of the charge carriers within each ordered domain of size rc,ab. This picture enables us to precisely determine the Ginzburg-Landau superconducting coherence length in the ab-plane, and we obtain ξab=1.41±0.04 nm.
CuxSbySz THIN FILMS PRODUCED BY ANNEALING CHEMICALLY DEPOSITED Sb2S3-CuS THIN FILMS
Authors: RODRÍGUEZ-LAZCANO Y. , NAIR M. T. S. , NAIR P. K.
Published: July 2002

The possibility of generating ternary compounds through annealing thin film stacks of binary composition has been demonstrated before. In this work we report a method to produce large area coating of ternary compounds through a reaction in solid state between thin films of Sb2S3 and CuS. Thin films of Sb2S3 -CuS were deposited on glass substrates in the sequence of Sb2S3 followed by CuS (on Sb2S3 ) using chemical bath deposition method. The multilayer stack, thus produced, of approximately 0.5 μm in thickness, where annealed under nitrogen and argon atmospheres at different temperatures to produce films of ternary composition, CuxSbySz . An optical band gap of ~1.5 eV was observed in these films, suggesting that the thin films of ternary composition formed in this way are suitable for use as absorber materials in photovoltaic devices. The results on the analyses of structural, electrical and optical properties of films formed with different combinations of thickness in the multilayers will be discussed in the paper.
Fractons with Scalar and Vector Interactions and Two Scaling Relations between the Static and Dynamic Critical Exponents
Authors: Skal Asya S.
Published: July 2002

Using new equilibrium equation [PhysicaA242, 13 (1997)] and Einstein's relation, new critical exponents for Young modulus Y(p)∝(p-p c )2t-g and regular diffusion [Formula: see text] are introduced, where t is the conductivity critical exponent and g=0.6 is the Hall coefficient critical exponent above the threshold. These results allows us to introduce two superuniversal fractons dimensions: with the scalar displacements d s =4/3 (the Alexander and Orbach conjecture) and with the vector displacements d v =21/20) which leads to new scaling relations between the static and dynamic critical exponents: t=1/2[(3d-4)ν-g]; t=[2ν(20d-21)+21g+2β)/42 in all (3≼d≼6) space dimensions.
ON THE ULTRASONIC ANOMALIES NEAR 260 K IN Y1Ba2Cu4O8
Authors: WU A. T.
Published: July 2002

Single phase polycrystalline high-T c superconductor Y 1 Ba 2 Cu 4 O 8 (Y124) has been measured by employing longitudinal and transverse ultrasonic waves, low-temperature X-ray diffraction, and specific heat. Comparison of the obtained data with the data of nuclear quadrupole resonance, nuclear magnetic resonance, and magnetic susceptibility measurements available in the literature from other groups implies the opening of a pseudospin gap near 260 K in Y124. It is proposed that the ultrasonic anomalies observed in Y124 near 260 K originate from the interactions between ultrasonic waves and long wavelength spin excitations.
A CLASSIFICATION RELIABILITY DRIVEN REJECT RULE FOR MULTI-EXPERT SYSTEMS
Authors: SANSONE C. , TORTORELLA F. , VENTO M.
Published: July 2002

In this paper we propose a reject rule applicable to a Multi-Expert System (MES). The rule is adaptive to the given domain and allows the achievement of the best trade-off between reject and error rates as a function of the costs attributed to errors and rejects in the considered application. The results of the method are particularly effective since the method does not rely on particular statistical assumptions, as other reject rules. An experimental analysis carried out on publicly available databases is reported together with a comparison with other methods present in the literature.
A SEGMENTATION-FREE RECOGNITION OF HANDWRITTEN TOUCHING NUMERAL PAIRS USING MODULAR NEURAL NETWORK
Authors: CHOI SOON-MAN , OH Il-SEOK
Published: July 2002

The conventional approach to the recognition of handwritten touching numeral pairs uses a process with two steps; splitting the touching numerals and recognizing individual numerals. It shows a limitation mainly due to a large variation in touching styles between two numerals. In this paper, we adopt the segmentation-free approach, which regards a touching numeral pair as an atomic pattern. Two important issues are raised, i.e. solving the large-set classification and constructing a large-size training set. For the 100-class classification, we use a modular neural network which consists of 100 separate subnetworks. We construct the training set with a balance among 100 classes and using a sufficient amount by extracting actual samples from a numeral database and synthesizing samples with a scheme of forcing two numerals to touch. The experimental results show a promising performance.
A DIGITAL LINKING NUMBER FOR DISCRETE CURVES
Authors: FOUREY SÉBASTIEN , MALGOUYRES RÉMY
Published: July 2002

A topological invariant, analogous to the linking number as defined in knot theory, is defined for pairs of digital closed paths of ℤ3. This kind of invariant is very useful for proofs which involve homotopy classes of digital paths. Indeed, it can be used, for example, in order to state the connection between the tunnels in an object and the ones in its complement. Even if its definition is not as immediate as in the continuous case it has the good property that it is immediately computable from the coordinates of the voxels of the paths with no need of a regular projection. The aim of this paper is to state and prove that the linking number has the same property as its continuous analogue: it is invariant under any homotopic deformation of one of the two paths in the complement of the other.
DYNAMICS OF NUMERICAL METHODS FOR COSYMMETRIC ORDINARY DIFFERENTIAL EQUATIONS
Authors: GOVORUKHIN V. N. , TSYBULIN V. G. , KARASÖZEN B.
Published: July 2002

The dynamics of numerical approximation of cosymmetric ordinary differential equations with a continuous family of equilibria is investigated. Nonconservative and Hamiltonian model systems in two dimensions are considered and these systems are integrated with several first-order Runge–Kutta methods. The preservation of symmetry and cosymmetry, the stability of equilibrium points, spurious solutions and transition to chaos are investigated by presenting analytical and numerical results. The overall performance of the methods for different parameters is discussed.
EXPERIMENTAL CONTROL OF CHAOS BY MODIFICATIONS OF DELAYED FEEDBACK
Authors: YAGASAKI KAZUYUKI , TOCHIO YOSHIYUKI
Published: July 2002

We present two modifications of the delayed feedback control technique for controlling chaotic dynamical systems. In these methods, control force is applied only when trajectories enter neighborhoods of the targets. So three shortcomings in the delayed feedback technique, the nonsmallness of control force, impossibility of targeting unstable periodic orbits and birth of undesirable stable orbits, are improved. The delay coordinate embedding technique is also used for specifying the target orbits and determining whether trajectories enter their neighborhood. We demonstrate the effectiveness of the two approaches for an experimental system, a feedback controlled pendulum.
INDUCED ONE-PARAMETER BIFURCATIONS IN IDENTIFIED NONLINEAR DYNAMICAL MODELS
Authors: AGUIRRE LUIS A. , MAQUET JEAN , LETELLIER CHRISTOPHE
Published: July 2002

It is shown that nonlinear global models identified from a single time series can be used to reproduce the same sequence of bifurcations of the original system. This has been observed for simulated and real data and for both difference equation and differential equation models, thus suggesting some generality. The results reported in this paper are of a practical character and seem to have some bearing not only on the important subject of estimating bifurcation diagrams from data, but also in model validation problems since some models can reproduce the bifurcation sequence of a system even when such models do not settle to the original attractor at first. In this case, models which would be dismissed are shown to display consistent dynamic information about the original system, as illustrated by a simulated and a real data example. An additional example that uses real data is provided in which the original bifurcation sequence is recovered by the addition of multiplicative noise with increasing variance.
FREE CONVECTION WITH RADIATIVE THERMAL TRANSFER OF GREY BODIES: ANALYSIS AND APPROXIMATION BY FINITE ELEMENT METHODS
Authors: MONNIER J.
Published: July 2002

We study a steady-state free (or mixed) convection model in two- or three-dimensions of space, taking into account radiative thermal transfer of grey bodies separated by a nonparticipating media. The existence of a weak solution is proved and the uniqueness is obtained when the viscosity and thermal conductivity of the fluid are large enough. Then, we discretize the model using classical finite element schemes and prove in detail the existence, uniqueness and the convergence of the discrete solution (when the viscosity and the thermal conductivity are large enough and the step size is small enough).
AN INFINITE SYSTEM OF DIFFUSION EQUATIONS ARISING IN TRANSPORT THEORY: THE COUPLED SPHERICAL HARMONICS EXPANSION MODEL
Authors: DEGOND PIERRE
Published: July 2002

In this paper, we derive a diffusion model of "SHE" type from a diffusion approximation of the Boltzmann equation. SHE (or Spherical Harmonics Expansion) models consist of a diffusion equation in the position-energy space. In the present model, the diffusion operator couples the various energy levels, while they stay uncoupled in the standard SHE model, at least in the force-free case. This new model is expected to give a better description of particle transport when inelastic collisions are important. The duality structure of the diffusion operator is underlined. A uniqueness result for the diffusion model is shown. A rigorous proof that the solutions of the Boltzmann equation converge (in a weak sense) towards those of the SHE model is developed in the force-free case.
LINEAR CURVED ROD MODEL: GENERAL CURVE
Authors: JURAK MLADEN , TAMBAČA JOSIP
Published: July 2002

A one-dimensional model of a curved rod is derived from the three-dimensional linearized elasticity. No positivity assumption on the curvature of the central line of the curved rod is made. The model is obtained by taking the limit in the equilibrium equation of the three-dimensional elastic rod when the thickness of the rod goes to zero. The appropriate convergence result is proved.
ON PARTICLE WEIGHTED METHODS AND SMOOTH PARTICLE HYDRODYNAMICS
Authors: VILA J. P.
Published: July 2002

This paper deal with designing of weighted particle approximation of conservation laws. New ideas concerning the use of variable smoothing length, renormalization and the use of Godunov type finite difference fluxes in particle methods are introduced and discussed in connection with standard implementation of the SPH method. A detailed analysis of boundary conditions approximation is also provided.
THE NONLINEAR GALERKIN METHOD APPLIED TO SHALLOW WATER EQUATIONS
Authors: DI MARTINO B. , CHATELON F. J. , ORENGA P.
Published: July 2002

In this work, we present some numerical approximations for a shallow water problem with a depth-mean velocity formulation and we give, where possible, an error bound. To prove the existence of solutions, we build a sequence of approximated solutions with the Galerkin method for the momentum equation and solve the continuity equation with the method of the characteristics. This leads to an expensive natural numerical scheme. Then, in order to reduce the CPU time, we present other numerical approximations based on the linear or nonlinear Galerkin method.
NUMERICAL SOLUTION OF A FREE BOUNDARY PROBLEM TAKING PLACE IN AN ELECTROMAGNETIC CASTING
Authors: BERMÚDEZ A. , MUÑIZ M. C.
Published: July 2002

A numerical model to describe the electromagnetic behaviour of an aluminium casting device is introduced. It is obtained by using an asymptotic expansion of the magnetic induction and an integral representation of the magnetic potential in an unbounded domain. Then a coupled finite/boundary element method is used. An iterative algorithm and numerical results for a real electromagnetic casting device are presented.
Polynomial invariants for Algebraically Split Links
Authors: Han YouFa , Zhang You
Published: July 2002

We deal with the properties of derivative of Jones polynomial for algebraically split links. In particularly, the properties of νn(L) and ϕn(L) are discussed.
VECTOR FIELD MEDIATED MODELS OF DYNAMICAL LIGHT VELOCITY
Authors: CLAYTON M. A. , MOFFAT J. W.
Published: July 2002

A vector–tensor theory of gravity that was introduced in an earlier publication is analyzed in detail and its consequences for early universe cosmology are examined. The multiple light cone structure of the theory generates different speeds of gravitational and matter wave fronts, and the contraction of these light cones produces acausal, superluminary inflation that can resolve the initial value problems of cosmology.
DOMAIN WALLS IN HIGHER DIMENSIONS
Authors: BANERJEE A. , DAS AJANTA
Published: July 2002

Thick domain walls with nonvanishing stress component in the direction perpendicular to the plain of the wall are considered. Their exact solutions are obtained in the background of a five-dimensional spacetime. There may be both expanding and collapsing walls. The energy density decreases on both sides of the walls and the spacetime in all cases is found to be reflection symmetric with respect to the walls.
THE HAUSDORFF DIMENSION OF SOME SNOWFLAKE-LIKE RECURSIVE CONSTRUCTIONS
Authors: JACKA S. D. , CROFT J. C.
Published: July 2002

Fractal subsets of ℝn with a highly regular structure are often constructed as a limit of a recursive procedure based on contractive maps.

The Hausdorff dimension of recursively constructed fractals is relatively easy to find when the contractive maps associated with each recursive step satisfy the Open Set Condition (OSC). We present a class of random recursive constructions which resemble snowflake structures and which break the OSC. We calculate the associated Hausdorff dimension and conjecture that an a.s. deterministic exact Hausdorff function does not exist.
ACTIVE FOURIER CONTOUR APPLIED TO REAL TIME 3D ULTRASOUND OF THE HEART
Authors: STETTEN GEORGE D. , DREZEK REBEKAH
Published: July 2002

We describe an active contour based on the elliptical Fourier series, and its application to matrix-array ultrasound. Matrix-array, or Real Time 3D (RT3D), ultrasound is a relatively new medical imaging modality that scans a 3D-volume electronically without physically moving the transducer, allowing for real-time continuous 3D imaging of the heart. With the goal of automatically tracking the heart wall, an active contour has been developed using the elliptical Fourier series to find perpendicular lines intersecting an initial contour. The neighborhood defined by these perpendiculars is mapped into a rectangular space, called a swath, whose vertical axis represents the inside-vs-outside dimension of the contour (perpendicular to the contour), and whose horizontal axis represents parametric distance along the contour (tangent to the contour). A dynamic programming technique is then used to find the optimum error function traversing the rectangle horizontally, and this error function is mapped back into image space to yield a new contour. The method does not iterate, but rather simultaneously searches for the optimum contour within a limited domain. Results are presented applying the technique to RT3D ultrasound images of in vivo hearts.
NOISE-INDUCED ESCAPE FROM THE LORENZ ATTRACTOR
Authors: ANISHCHENKO V. S. , KHOVANOV I. A. , KHOVANOVA N. A. , LUCHINSKY D. G. , McCLINTOCK P. V. E.
Published: July 2002

Noise-induced escape from a quasi-hyperbolic attractor in the Lorenz system is investigated via an analysis of the distributions of both the escape trajectories and the corresponding realizations of the random force. It is shown that a unique escape path exists, and that it consists of three parts with noise playing a different role in each. It is found that the mechanism of the escape from a quasi-hyperbolic attractor differs from that of escape from a non-hyperbolic attractor. The possibility of calculating the escape probability is discussed.
Error estimation in automatic quadrature routines
Authors: Berntsen Jarle , Espelid Terje O.
Published: July 2002

A new algorithm for estimating the error in quadrature approximations is presented. Based on the same integrand evaluations that we need for approximating the integral, one may, for many quadrature rules, compute a sequence of null rule approximations. These null rule approximations are then used to produce an estimate of the local error. The algorithm allows us to take advantage of the degree of precision of the basic quadrature rule. In the experiments we show that the algorithm works satisfactorily for a selection of different quadrature rules on all test families of integrals.
Stability of block algorithms with fast level-3 BLAS
Authors: Demmel James W. , Higham Nicholas J.
Published: July 2002

Block algorithms are becoming increasingly popular in matrix computations. Since their basic unit of data is a submatrix rather than a scalar, they have a higher level of granularity than point algorithms, and this makes them well suited to high-performance computers. The numerical stability of the block algorithms in the new linear algebra program library LAPACK is investigated here. It is shown that these algorithms have backward error analyses in which the backward error bounds are commensurate with the error bounds for the underlying level-3 BLAS (BLAS3). One implication is that the block algorithms are as stable as the corresponding point algorithms when conventional BLAS3 are used. A second implication is that the use of BLAS3 based on fast matrix multiplication techniques affects the stability only insofar as it increases the constant terms in the normwise backward error bounds. For linear equation solvers employing
LU
factorization, it is shown that fixed precision iterative refinement helps to mitigate the effect of the larger error constants. Despite the positive results presented here, not all plausible block algorithms are stable; we illustrate this with the example of
LU
factorization with block triangular factors and describe how to check a block algorithm for stability without doing a full error analysis.
New NAG library software for first-order partial differential equations
Authors: Pennington S. V. , Berzins M.
Published: July 2002

New NAG Fortran Library routines are described for the solution of systems of nonlinear, first-order, time-dependent partial differential equations in one space dimension, with scope for coupled ordinary differential or algebraic equations. The method-of-lines is used with spatial discretization by either the central-difference Keller box scheme or an upwind scheme for hyperbolic systems of conservation laws. The new routines have the same structure as existing library routines for the solution of second-order partial differential equations, and much of the existing library software is reused. Results are presented for several computational examples to show that the software provides physically realistic numerical solutions to a challenging class of problems.
Organizational obstacles to interface design and development
Authors: Poltrock Steven E. , Grudin Jonathan
Published: July 2002

The development of human-computer interfaces was studied in two large software product development organizations. Researchers joined development projects for approximately one month and participated in interface design while concurrently interviewing other project participants and employees, recording activity in meetings and on electronic networks, and otherwise observing the process. The two organizations differed in their approaches to development, and, in each case, the approach differed in practice from the model supported by the organizational structure. Development practices blocked the successful application of accepted principles of interface design. The obstacles to effective design that results from people noticing and being affected by interface changes, and a lack of communication among those sharing responsibility for different aspects of the interface.
On the conversion of indirect to direct recursion
Authors: Kaser Owen , Ramakrishnan C. R. , Pawagi Shaunak
Published: July 2002

Procedure inlining can be used to convert mutual recursion to direct recursion. This allows use of optimization techniques that are most easily applied to directly recursive procedures, in addition to the well-known benefits of inlining. We present tight (necessaryandsufficient) conditions under which inlining can transform all mutual recursion to direct recursion, and those under which heuristics to eliminate mutual recursion always terminate. We also present a technique to eliminate mutually recursive circuits that consist of only tail calls. From this, we conclude that tail recursion elimination should be interleaved with inlining.
On the power of cascade ciphers
Authors: Even S. , Goldreich O.
Published: July 2002

The unicity distance of a cascade of random ciphers, with respect to known plaintext attack, is shown to be the sum of the key lengths. A time-space trade-off for the exhaustive cracking of a cascade of ciphers is shown. The structure of the set of permutations realized by a cascade is studied; it is shown that only
l
.2

k

exhaustive experiments are necessary to determine the behavior of a cascade of
l
stages, each having
k
key bits. It is concluded that the cascade of random ciphers is not a random cipher. Yet, it is shown that, with high probability, the number of permutations realizable by a cascade of
l
random ciphers, each having
k
key bits, is 2

lk

. Next, it is shown that two stages are not worse than one, by a simple reduction of the cracking problem of any of the stages to the cracking problem of the cascade. Finally, it is shown that proving a nonpolynomial lower bound on the cracking problem of long cascades is a hard task,
since such a bound implies that
P
≉
NP
.
Pavlov
Authors: Wolber David
Published: July 2002

Conventional interface builders provide little support for interactive development of interfaces with application-specific graphics. Some Programming by Demonstration (PBD) systems do provide such support, but none provide full support for demonstrating interfaces, such as those in games, in which the graphics are animated. This article proposes a number of techniques for creating animated interfaces, all of which have been included in an exploratory system,
Pavlov
. Many of the techniques are based on the addition of timing controls to a form of PBD called
stimulus-response demonstration
. Others are based on an adaptation of a traditional animation time-line that integrates end-user interaction with animation. The article also evaluates
Pavlov
with (1) a comparison to other PBD systems in terms of the behaviors that can be specified interactively and (2) a report on an informal user study comparing development in
Pavlov
to development in a conventional interface builder.
An experimental comparison of RGB, YIQ, LAB, HSV, and opponent color models
Authors: Schwarz Michael W. , Cowan William B. , Beatty John C.
Published: July 2002

The increasing availability of affordable color raster graphics displays has made it important to develop a better understanding of how color can be used effectively in an interactive environment. Most contemporary graphics displays offer a choice of some 16 million colors; the user's problem is to find the
right
color.

Folklore has it that the RGB color space arising naturally from color display hardware is user-hostile and that other color models such as the HSV scheme are preferable. Until now there has been virtually no experimental evidence addressing this point.

We describe a color matching experiment in which subjects used one of two tablet-based input techniques, interfaced through one of five color models, to interactively match target colors displayed on a CRT.

The data collected show small but significant differences between models in the ability of subjects to match the five target colors used in this experiment. Subjects using the RGB color model matched quickly but inaccurately compared with those using the other models. The largest speed difference occurred during the early
convergence phase
of matching. Users of the HSV color model were the slowest in this experiment, both during the convergence phase and in total time to match, but were relatively accurate. There was less variation in performance during the second
refinement phase
of a match than during the convergence phase.

Two-dimensional use of the tablet resulted in faster but less accurate performance than did strictly one-dimensional usage.

Significant learning occurred for users of the Opponent, YIQ, LAB, and HSV color models, and not for users of the RGB color model.
A fixpoint semantics for nondeterministic data flow
Authors: Staples John , Nguyen V. L.
Published: July 2002

Criteria for adequacy of a data flow semantics are discussed and Kahn's successful semantics for functional (deterministic) data flow is reviewed. Problems arising from nondeterminism are introduced and the paper's approach to overcoming them is introduced. The approach is based on generalizing the notion of input-output relation, essentially to a partially ordered multiset of input-output histories. The Brock-Ackerman anomalies concerning the input-output relation model of nondeterministic data flow are reviewed, and it is indicated how the proposed approach avoids them. A new anomaly is introduced to motivate the use of multisets. A formal theory of asynchronous processes is then developed. The main result is that the operation of forming a process from a network of component processes is associative. This result shows that the approach is not subject to anomalies such as that of Brock and Ackerman.
Optimal static load balancing in distributed computer systems
Authors: Tantawi Asser N. , Towsley Don
Published: July 2002

A distributed computer system that consists of a set of heterogeneous host computers connected in an arbitrary fashion by a communications network is considered. A general model is developed for such a distributed computer system, in which the host computers and the communications network are represented by product-form queuing networks. In this model, a job may be either processed at the host to which it arrives or transferred to another host. In the latter case, a transferred job incurs a communication delay in addition to the queuing delay at the host on which the job is processed. It is assumed that the decision of transferring a job does not depend on the system state, and hence is
static
in nature. Performance is optimized by determining the load on each host that minimizes the mean job response time. A nonlinear optimization problem is formulated, and the properties of the optimal solution in the special case where the communication delay does not depend on the source-destination pair is shown.

Two efficient algorithms that determine the optimal load on each host computer are presented. The first algorithm, called the
parametric-study algorithm
, generates the optimal solution as a function of the communication time. This algorithm is suited for the study of the effect of the speed of the communications network on the optimal solution. The second algorithm is a
single-point algorithm
; it yields the optimal solution for given system parameters. Queuing models of host computers, communications networks, and a numerical example are illustrated.
Some contributions to the metatheory of the situation calculus
Authors: Pirri Fiora , Reiter Ray
Published: July 2002

We focus on a rich axiomatization for actions in the situation
calculus that includes, among other features, a solution to the frame problem for deterministic actions. Our work is foundational in nature, directed at simplifying the entailment problem for these axioms. Specifically, we make four contributions to the metatheory of situation calculus axiomatizations of dynamical systems:

(1) We prove that the above-mentioned axiomatization for actions has a relative satisfiability property; the full axiomatization is satisfiable iff the axioms for the initial state are.

(2)We define the concept of regression relative to these axioms, and prove a soundness and completeness theorem for a regression-based approach to the entailment problem for a wide class of queries.

(3) Our formalization of the situation calculus requires certain foundational axioms specifying the domain of situations. These include an induction axiom, whose presence complicates human and automated reasoning in the situation calculus. We characterize various classes of sentences whose proofs do not require induction, and in some cases, some of the other foundational axioms.

(4)We prove that the logic programming language GOLOG never requires any of the foundational axioms for the evaluation of programs.
Turing Machines, Finite Automata and Neural Nets
Authors: Arbib Michael
Published: July 2002

This paper
1
compares the notions of Turing machine, finite automaton and neural net. A new notation is introduced to replace net diagrams. “Equivalence” theorems are proved for nets with receptors, and finite automata; and for nets with receptors and effectors, and Turing machines. These theorems are discussed in relation to papers of Copi, Elgot and Wright; Rabin and Scott; and McCulloch and Pitts. It is shown that sets of positive integers “accepted” by finite automata are recursive; and a strengthened form of a theorem of Kleene is proved.
Large Parallel Computers
Authors: Schwartz J.
Published: July 2002

Various classes of machines incorporating parallelism are considered. A general class of large-scale multiprocessors is outlined, and some problems of hardware and software implementation for computers of this class are discussed.
A Machine-Independent Theory of the Complexity of Recursive Functions
Authors: Blum Manuel
Published: July 2002

The number of steps required to compute a function depends, in general, on the type of computer that is used, on the choice of computer program, and on the input-output code. Nevertheless, the results obtained in this paper are so general as to be nearly independent of these considerations.

A function is exhibited that requires an enormous number of steps to be computed, yet has a “nearly quickest” program: Any other program for this function, no matter how ingeniously designed it may be, takes practically as many steps as this nearly quickest program.

A different function is exhibited with the property that no matter how fast a program may be for computing this function another program exists for computing the function very much faster.
Numerical Inversion of Laplace Transforms by Relating Them to the Finite Fourier Cosine Transform
Authors: Dubner H. , Abate J.
Published: July 2002

In this paper the problem of readily determining the inverse Laplace transform numerically by a method which meets the efficiency requirements of automatic digital computation is discussed. Because the result inverse function is given as a Fourier cosine series, the procedure requires only about ten FORTRAN statements. Furthermore, it does not require the use of involved algorithms for the generation of any special functions, but uses only cosines and exponentials.

The basis of the method hinges on the fact that in evaluating the inverse Laplace transform integral there exists a freedom in choosing the contour of integration. Given certain restrictions, the contour may be any vertical line in the right-half plane. Specifying a line, the integral to be evaluated is essentially a Fourier integral. However, the method is concerned with determining the proper line, so that when the integral (along this line) is approximated, the error is as small as desired by virtue of having chosen the particular contour.
Mean-Value Analysis of Closed Multichain Queuing Networks
Authors: Reiser M. , Lavenberg S. S.
Published: July 2002

It is shown that mean queue sizes, mean waiting times, and throughputs in closed multiple-chain queuing networks which have product-form solution can be computed recursively without computing product terms and normalization constants. The resulting computational procedures have improved properties (avoidance of numerical problems and, in some cases, fewer operations) compared to previous algorithms. Furthermore, the new algorithms have a physically meaningful interpretation which provides the basis for heuristic extensions that allow the approximate solution of networks with a very large number of closed chains, and which is shown to be asymptotically valid for large chain populations.
An algorithm for generating chi random variables
Authors: Monahan John F.
Published: July 2002

An algorithm is presented for generating random variables from the chi family of distributions with
degrees of freedom parameter LY 2 1. It is based on the ratio of uniforms method and can be used
effectively for the gamma family.
Implementing Clenshaw-Curtis quadrature, I methodology and experience
Authors: Gentleman W. Morven
Published: July 2002

Clenshaw-Curtis quadrature is a particularly important automatic quadrature scheme for a variety of reasons, especially the high accuracy obtained from relatively few integrand values. However, it has received little use because it requires the computation of a cosine transformation, and the arithmetic cost of this has been prohibitive.

This paper is in two parts; a companion paper, “II Computing the Cosine Transformation,” shows that this objection can be overcome by computing the cosine transformation by a modification of the fast Fourier transform algorithm. This first part discusses the strategy and various error estimates, and summarizes experience with a particular implementation of the scheme.
An assessment of the prototyping approach to information systems development
Authors: Alavi Maryam
Published: July 2002

A two-phased research project comparing the prototyping approach with the more traditional life cycle approach finds that prototyping facilitates communication between users and designers during the design process. However, the findings also indicate that designers who used prototyping experienced difficulties in managing and controlling the design process.
Region representation
Authors: Dyer Charles R. , Rosenfeld Azriel , Samet Hanan
Published: July 2002

There has been recent interest in the use of quadtrees to represent regions in an image. It thus becomes desirable to develop efficient methods of conversion between quadtrees and other types of region representations. This paper presents an algorithm for converting from quadtrees to a simple class of boundary codes. The algorithm is shown to have an execution time proportional to the perimeter of the region.
Best sorting algorithm for nearly sorted lists
Authors: Cook Curtis R. , Kim Do Jin
Published: July 2002

Straight Insertion Sort, Shellsort, Straight Merge Sort,
Quickersort, and Heapsort are compared on nearly sorted lists. The
ratio of the minimum number of list elements which must be removed
so that the remaining portion of the list is in order to the size
of the list is the authors' measure of sortedness. Tests on
randomly generated lists of various combinations of list length and
small sortedness ratios indicate that Straight Insertion Sort is
best for small or very nearly sorted lists and that Quickersort is
best otherwise. Cook and Kim also show that a combination of the
Straight Insertion Sort and Quickersort with merging yields a
sorting method that performs as well as or better than either
Straight Insertion Sort or Quickersort on nearly sorted lists.
Search and strategies in OPL
Authors: Van Hentenryck Pascal , Perron Laurent , Puget Jean-François
Published: July 2002

OPL is a modeling language for mathematical programming and combinatorial optimization. It is the first language to combine high-level algebraic and set notations from mathematical modeling languages with a rich constraint language and the ability to specify search procedures and strategies that are the essence of constraint programming. This paper describes the facilities available in OPL to specify search procedures. It describes the abstractions of OPL to specify both the search tree (search) and how to explore it (strategies). The paper also illustrates how to use these high-level constructs to implement traditional search procedures in constraint programming and scheduling.
Hybrid simulation models of computer systems
Authors: Schwetman H. D.
Published: July 2002

This paper describes the structure and operation of a hybrid simulation model in which both discrete-event simulation and analytic techniques are combined to produce efficient yet accurate system models. In an example based on a simple hypothetical computer system, discrete-event simulation is used to model the arrival and activation of jobs, and a central-server queueing network models the use of system processors. The accuracy and efficiency of the hybrid technique are demonstrated by comparing the result and computational costs of the hybrid model of the example with those of an equivalent simulation-only model.
Concurrent reading and writing
Authors: Lamport Leslie
Published: July 2002

The problem of sharing data among asynchronous processes is considered. It is assumed that only one process at a time can modify the data, but concurrent reading and writing is permitted. Two general theorems are proved, and some algorithms are presented to illustrate their use. These include a solution to the general problem in which a read is repeated if it might have obtained an incorrect result, and two techniques for transmitting messages between processes. These solutions do not assume any synchronizing mechanism other than data which can be written by one process and read by other processes.
A formal system for information retrieval from files
Authors: Hsiao David , Harary Frank
Published: July 2002

A generalized file structure is provided by which the concepts of keyword, index, record, file, directory, file structure, directory decoding, and record retrieval are defined and from which some of the frequently used file structures such as inverted files, index-sequential files, and multilist files are derived.

Two algorithms which retrieve records from the generalized file structure are presented.