bluuebunny/crossref_metadata_2025 huggingface dataset:
PARTICLE CREATION IN THE CHIRAL COSMIC STRING SPACETIME
Authors: BEZERRA V. B. , MOSTEPANENKO V. M. , FILHO R. M. TEIXEIRA
Published: July 2002

We analyze particle production in the spacetime of a chiral cosmic string when it evolves to a static cosmic string configuration. The number of created particles and their energy per unit length of a string are estimated. They appear to be five orders smaller than gravitational particle production in the formation of a static cosmic string but still is rather significant.
MULTIPLE IMAGING BY GRAVITATIONAL WAVES
Authors: FARAONI VALERIO
Published: July 2002

Gravitational waves act like lenses for the light propagating through them. This phenomenon is described using the vector formalism employed for ordinary gravitational lenses, which was proved to be applicable also to a nonstationary spacetime, with the appropriate modifications. In order to have multiple imaging an approximate condition analogous to that for ordinary gravitational lenses must be satisfied. Certain astrophysical sources of gravitational waves satisfy this condition, while the gravitational wave background, on average, does not. Multiple imaging by gravitational waves is, in principle, possible, but the probability of observing such a phenomenon is extremely low.
TALES OF TAILS IN COSMOLOGY
Authors: FARAONI VALERIO , GUNZIG EDGARD
Published: July 2002

Late time mild inflation (LTMI) proposes to solve the age of the universe problem and the discrepancy between locally and globally measured values of the Hubble parameter. However, the mechanism proposed to achieve LTMI is found to be physically pathological by applying the theory of tails for the solutions of wave equations in curved spaces. Alternative mechanisms for LTMI are discussed, and the relevance of scalar wave tails for cosmology is emphasized.
GRAVITATIONAL LENSING BOUND ON THE AVERAGE REDSHIFT OF GAMMA RAY BURSTS IN MODELS WITH EVOLVING LENSES
Authors: JAIN DEEPAK , PANCHAPAKESAN N. , MAHAJAN S. , BHATIA V. B.
Published: July 2002

Identification of gravitationally lensed Gamma Ray Bursts (GRBs) in the BATSE 4B catalog can be used to constrain the average redshift  of the GRBs. In this paper we investigate the effect of evolving lenses on the  of GRBs in different cosmological models of the universe. The cosmological parameters Ω and Λ have an effect on the  of GRBs. The other factor which can change the  is the evolution of galaxies. We consider three evolutionary model of galaxies. In particular, we find that the upper limit on  of GRBs is higher in evolving model of galaxies as compared to non-evolving models of galaxies.
CONSERVATION LAWS AND VECTOR MODEL OF PARTICLES
Authors: TSAN UNG CHAN
Published: July 2002

Any particle is defined by a set of additive quantum numbers: A, L, individual flavours. These numbers could be considered as the components of a vector C which is characteristic of each particle. Each particle is associated to a vector C representing the particle in an abstract space. The electric charge Q could be interpreted as the projection of C on a vector Q(0). If C=0, particle and antiparticle are the same particle. If C≠0, particle and antiparticle are represented by opposite vectors and are different even if Q=0. In this framework, the neutron is different from the antineutron (many experimental facts confirm this statement) and the neutrino is different from the antineutrino. A direct and important consequence of the difference between the neutrino and the antineutrino is that ββ0ν decay should be strictly forbidden. It is indeed in agreement with all up to now experimental results which show no hint of any ββ0ν event. The features of messengers would explain why electromagnetism and strong interaction conserve A, L and individual flavours and consequently also total flavour while weak interaction conserves only A, L and total flavour.
MARKOVIAN AVAILABILITY MEASUREMENT WITH TWO TYPES OF SOFTWARE FAILURES DURING THE OPERATION PHASE
Authors: TOKUNO KOICHI , YAMADA SHIGERU
Published: July 2002

This paper develops a plausible software availability model considering two types of failures during the operation phase. The first type is caused by the faults that could not be detected/corrected during the testing phase and the second type caused by those introduced by deviating from the specification during the operation phase. The former and the latter types of software failure-occurrence phenomena are described by a geometrically decreasing and a constant hazard rate, respectively. This model also describes the imperfect debugging environment in which a debugging activity does not always remove a fault perfectly. Taking notice of the cumulative number of faults corrected during the operation phase, we use a Markov process to describe the time-dependent behavior of the software system. Several quantitative measures of software system performance are derived from this model. Finally, numerical examples are presented for illustration of software availability measurement.
DYNAMIC SCALING IN RECRYSTALLIZATION OF AN ELECTROCHEMICALLY ROUGHENED SILVER ELECTRODE SURFACE IN WATER
Authors: OTSUKA ICHIRO , IWASAKI TAKATOSHI
Published: July 2002

We have studied the kinetic mechanisms in recrystallization of an electrochemically roughened silver electrode surface in Ar-saturated water at room temperature using dynamic scaling theory and tapping mode atomic force microscopy (TMAFM). We observed dynamic scaling behavior during the recrystallization. The roughness (α) and growth (β) exponents measured were α=0.95 ± 0.05 and β=0.16± 0.04 for the scale length (L)< the average diameter of Ag nodules (d), and α=0.61±0.05 and β=0.20± 0.05 for L>d. These scaling exponents are relatively close to the predictions (β=0.25, 0.20) of conservative models where surface diffusion is the main mechanism of mass transport in determining a growing surface morphology.
THE HAIR-THREAD-TOURNIQUET SYNDROME — REPORT OF AN UNUSUAL PRESENTATION OF THIS RARE CONDITION
Authors: Sunil T. M.
Published: July 2002

The Hair-Thread-Tourniquet syndrome is a rare disorder with merely 17 cases of finger involvement reported so far. This is a report of one such case of accidental digital constriction, which presented as late as three months after injury. This is the longest reported duration between injury and detection. The constriction band was in the form of an eschar lying in an epithelialised crease. Treatment involved excision of the crease followed by multiple z-plasties to close the resulting defect. This is the first case in English literature to report epithelialisation of the crease and consequently the first case to require excision of the band followed by z-plasty.
CONVERGENCE OF MINIMUM ENTROPY OPTION PRICES FOR WEAKLY CONVERGING INCOMPLETE MARKET MODELS
Authors: HUBALEK FRIEDRICH , HUDETZ THOMAS
Published: July 2002

We study weak convergence of a sequence of (approximating) asset price models Sn to a limiting model S: both Sn and S are multi-dimensional asset price processes with some physical probability measures Pn resp. P, and a natural notion of process convergence is the weak convergence of the induced path probability measures, denoted by (Sn|Pn) resp. (S|P), on the abstract topological space of possible asset price trajectories.

For the purpose of no-arbitrage pricing of options or more general derivatives on the model assets, there are two different aspects of this convergence: (i) convergence under the given physical probability measures, (Sn|Pn) → (S|P) and (ii) convergence under suitably chosen equivalent martingale measures (EMM) relevant for pricing derivatives, (Sn|Qn) → (S|Q). A simple example is the convergence of a sequence of discrete-time binomial models to the Black–Scholes model (geometric Brownian motion), where the model markets are complete and hence the choice of Qn resp. Q is unique. This example and the general case of complete limit markets (S|P) have been studied in [1].

In contrast we have several choices for Qn resp. Q when all the model markets are incomplete. A natural choice is the minimum entropy EMM [2, 3], defined as the (unique) EMM R minimizing the relative entropy H(R|P) to the physical measure P, among all EMMs. We prove the following: given that the approximating models converge under the physical measures, (Sn|Pn) → (S|P) — with some mild assumptions on P and on the minimum entropy EMMs Rn for Sn resp. R for S — entropy number convergence implies weak convergence of the minimum entropy option price processes: H(Rn|Pn) → H(R|P) implies (Sn|Rn) → (S|R). Several rigorous examples illustrate the result; cf. also [4].
A DIFFERENTIAL GAME APPROACH TO EVOLUTIONARY EQUILIBRIUM SELECTION
Authors: HOFBAUER JOSEF , SORGER GERHARD
Published: July 2002

The equilibrium selection model of Matsui and Matsuyama (1995), which is based on rational players who maximise their discounted future payoff, is analysed with the help of an associated differential game. Equilibrium selection results are derived for games with a ½-dominant equilibrium, for games with a potential function, and some simple supermodular games.
IMPROVED BOUNDS FOR GOSSIPING IN MESH BUS NETWORKS
Authors: BERMOND JEAN-CLAUDE , MARSHALL SUSAN , YU MIN-LI
Published: July 2002

Improved bounds for the minimum gossiping time in mesh bus networks of arbitrary dimension for 1-port model are given. More precisely, the gossiping protocol consists of steps during which messages are sent via buses and at the end of the protocol, all the nodes should know all the information. Furthermore, during one step a bus can carry at most one message, and each node can either send or receive (not both) on at most one bus The minimum gossiping time of a bus network G is the minimum number of steps required to perform a gossip under this model. Here we determine almost exactly the minimum gossip time for 2-dimensional mesh bus networks and give tight bounds for d-dimensional mesh bus networks.
ESTIMATION OF ELECTRON ENERGY RELAXATION TIME IN 2DEG CHANNELS FROM TRANSVERSE AND LONGITUDINAL NOISE
Authors: ARDARAVICIUS L. , LIBERIS J. , MATULIONIS A. , RAMONAS M.
Published: July 2002

Microwave noise is investigated in heterostructures subjected to an electric field applied parallel to the interfaces. The longitudinal and transverse noise temperatures are measured and simulated in the plane of electron confinement in the directions perpendicular and parallel to the electric field. Monte Carlo simulation is performed for a subcritically doped InAlAs/InGaAs/InAlAs heterostructure containing a two-dimensional electron gas in a single channel. The simulated longitudinal noise temperature is found to be nearly the same as the transverse one in the field range where the interwell transfer of hot electrons is not important. The longitudinal noise temperature exceeds the transverse one considerably in a supercritically doped InAlAs/InGaAs/InAlAs/InP heterostructure containing three separate quantum-well channels, each accommodating a two-dimensional electron gas at equilibrium. The observed strong planar anisotropy is ascribed to the channel occupancy fluctuations caused by the interwell transfer of equilibrium electrons. A possibility to estimate energy relaxation time from the transverse and the longitudinal microwave noise measurements is discussed.
ON PERSISTENCE AND STABILITY OF COUPLED MAP LATTICES
Authors: AHMED E. , HEGAZI A. S.
Published: July 2002

Linear stability of homogeneous and inhomogeneous steady state solutions for coupled map lattices (CML) are studied. Some persistence problems in CML are discussed and applied to immune and an economic models. The stability results are applied to CML motivated by forced circle map, Winfree model, Josephson junction arrays and an ecological CML model. Global stability results for some CML systems are given.
APPLICATIONS OF SYNCHROTRON X-RAY MICROTOMOGRAPHY TO MESOSCALE MATERIALS
Authors: SEIDLER G. T. , ATKINS L. J. , BEHNE E. A. , NOOMNARM U. , KOEHLER S. A. , GUSTAFSON R. R. , MCKEAN W. T.
Published: July 2002

We discuss the application of synchrotron X-ray microtomography (XMT) to granular matter, foams, crumpled membranes, and paper. XMT provides rapid, high-resolution, fully three-dimensional characterization of each of these classes of material. In some cases, subsequent three-dimensional image processing allows the virtual reconstruction of the disordered material as a specified assemblage of idealized basic structural units. This allows measurement of otherwise inaccessible correlation functions and can also be used as the starting point for data-initiated simulations.
Are wait-free algorithms fast?
Authors: Attiya Hagit , Lynch Nancy , Shavit Nir
Published: July 2002

The time complexity of wait-free algorithms in “normal” executions, where no failures occur and processes operate at approximately the same speed, is considered. A lower bound of log
n
on the time complexity of any wait-free algorithm that achieves
approximate agreement
among
n
processes is proved. In contrast, there exists a non-wait-free algorithm that solves this problem in constant time. This implies an Ω(log
n
) time separation between the wait-free and non-wait-free computation models. On the positive side, we present an O(log
n
) time wait-free approximate agreement algorithm; the complexity of this algorithm is within a small constant of the lower bound.
From programming environments to environments for designing
Authors: Winograd Terry
Published: July 2002

Though there have been advances in end-user programming, complex applications still need professional developers. This inspired look at the future of creating complex software explores the shift from programming environments to design environments, discussing environments that help developers satisfy end-users' cognitive needs and help deal with contextual issues such as the aesthetic, practical, and social properties of the application and the users. A strong case is made that design environments will need to provide robust support for communication between developers and end users.
Motion recovery for video content classification
Authors: Dimitrova Nevenka , Golshani Forouzan
Published: July 2002

Like other types of digital information, video sequences must be classified based on the semantics of their contents. A more-precise and completer extraction of semantic information will result in a more-effective classification. The most-discernible difference between still images and moving pictures stems from movements and variations. Thus, to go from the realm of still-image repositories to video databases, we must be able to deal with motion. Particularly, we need the ability to classify objects appearing in a video sequence based on their characteristics and features such as shape or color, as well as their movements. By describing the movements that we derive from the process of motion analysis, we introduce a dual hierarchy consisting of spatial and temporal parts for video sequence representation. This gives us the flexibility to examine arbitrary sequences of frames at various levels of abstraction and to retrieve the associated temporal information (say, object trajectories) in addition to the spatial representation. Our algorithm for motion detection uses the motion compensation component of the MPEG video-encoding scheme and then computes trajectories for objects of interest. The specification of a language for retrieval of video based on the spatial as well as motion characteristics is presented.
Automatic generation of functional vectors using the extended finite state machine model
Authors: Cheng Kwang-Ting , Krishnakumar A. S.
Published: July 2002

We present a method of automatic generation of functional vectors for sequential circuits. These vectors can be used for design verification, manufacturing testing, or power estimation. A high-level description of the circuit in VHDL or C is assumed available. Our method automatically transforms the high-level description of a circuit in VHDL or C into an extended finite state machine (EFSM) model that is used to generate functional vectors. The EFSM model is a generalization of the traditional state machine model. It is a compact representation of models with local data variables and preserves many nice properties of a traditional state machine model. The theoretical background of the EFSM model is addressed in this article. Our method guarantees that the generated vectors cover every statement in the high-level description at least once. Experimental results show that a set of comprehensive functional vectors for sequential circuits with more than a hundred flip-flops can be generated automatically in a few minutes of CPU time using our prototype system.
HFS
Authors: Krieger Orran , Stumm Michael
Published: July 2002

The Hurricane File System (HFS) is designed for (potentially large-scale) shared-memory multiprocessors. Its architecture is based on the principle that, in order to maximize performance for applications with diverse requirements, a file system must support a wide variety of file structures, file system policies, and I/O interfaces. Files in HFS are implemented using simple building blocks composed in potentially complex ways. This approach yields great flexibility, allowing an application to customize the structure and policies of a file to exactly meet its requirements. As an extreme example, HFS allows a file's structure to be optimized for concurrent random-access write-only operations by 10 threads, something no other file system can do. Similarly, the prefetching, locking, and file cache management policies can all be chosen to match an application's access pattern. In contrast, most parallel file systems support a single file structure and a small set of policies. We have implemented HFS as part of the Hurricane operating system running on the Hector shared-memory multiprocessor. We demonstrate that the flexibility of HFS comes with little processing or I/O overhead. We also show that for a number of file access patterns, HFS is able to deliver to the applications the full I/O bandwidth of the disks on our system.
The design, implementation, and evaluation of a symmetric banded linear solver for distributed-memory parallel computers
Authors: Gupta Anshul , Gustavson Fred G. , Joshi Mahesh , Toledo Sivan
Published: July 2002

This article describes the design, implementation, and evaluation of a parallel algorithm for the Cholesky factorization of symmetric banded matrices. The algorithm is part of IBM's parallel engineering and scientific subroutine library version 1.2 and is compatible with ScaLAPACK's banded solver. Analysis, as well as experiments on an IBM SP2 distributed-memory parallel computer, shows that the algorithm efficiently factors banded matrices with wide bandwidth. For example, a 31-mode SP2 factors a large matrix more than 16 times faster than a single node would factor it using the best sequential algorithm, and more than 20 times faster than a single node would using LAPACK's DPBTRF. The algorithm uses novel ideas in the area of distributed dense-matrix computations that include the use of a dynamic schedule for a blocked systolic-like algorithm and the separation of the input and output layouts from the layout the algorithm uses internally. The algorithm alson uses known techniques such as blocking to improve its communication-to-computation ratio and its data-cache behavior.
Bus-based communication synthesis on system level
Authors: Gasteier Michael , Glesner Manfred
Published: July 2002

In this article, we present an approach to automatic generation of communication topologies for statically scheduled systems of subsystems. Given a specification containing a set of processes that communicate via abstract send and receive functions, we show how a cost-efficient communication topology consisting of one or more buses without arbitration scheme can be set up for such applications.
Physical integrity in a large segmented database
Authors: Lorie Raymond A.
Published: July 2002

A database system can generally be divided into three major components. One component supports the logical database as seen by the user. Another component maps the information into physical records. The third component, called the storage component, is responsible for mapping these records onto auxiliary storage (generally disks) and controlling their transfer to and from main storage.

This paper is primarily concerned with the implementation of a storage component. It considers a simple and classical interface to the storage component: Seen at this level the database is a collection of segments. Each segment is a linear address space.

A recovery scheme is first proposed for system failure (hardware or software error which causes the contents of main storage to be lost). It is based on maintaining a dual mapping between pages and their location on disk. One mapping represents the current state of a segment being modified; the other represents a previous backup state. At any time the backup state can be replaced by the current state without any data merging. Procedures for segment modification, save, and restore are analyzed. Another section proposes a facility for protection against damage to the auxiliary storage itself. It is shown how such protection can be obtained by copying on a tape (checkpoint) only those pages that have been modified since the last checkpoint.
The Solvability of the Halting Problem for 2-State Post Machines
Authors: Aanderaa Stål , Fischer Patrick C.
Published: July 2002

A Post machine is a Turing machine which cannot both write and move on the same machine step. It is shown that the halting problem for the class of 2-state Post machines is solvable. Thus, there can be no universal 2-state Post machine. This is in contrast with the result of Shannon that there exist universal 2-state Turing machines when the machines are capable of both writing and moving on the same step.
The Concept of Demodulation in Theorem Proving
Authors: Wos Lawrence , Robinson George A. , Carson Daniel F. , Shalla Leon
Published: July 2002

In many fields of mathematics the richness of the underlying axiom set leads to the establishment of a number of very general equalities. For example, it is easy to prove that in groups (
x
-1
)
-1
=
x
and that in rings -
x
· -
y
=
x
·
y
. In the presence of such an equality, each new inference made during a proof search by a theorem-proving program may immediately yield a set of very closely related inferences. If, for example,
b
·
a
=
c
is inferred in the presence of (
x
-1
)
-1
=
x
, substitution immediately yields obviously related inferences such as (
b
-1
)
-1
·
a
=
c
. Retention of many members of each such set of inferences has seriously impeded the effectiveness of automatic theorem proving. Similar to the gain made by discarding instances of inferences already present is that made by discarding instances of repeated application of a given equality. The latter is achieved by use of demodulation. Its definition, evidence of its value, and a related rule of inference are given. In addition a number of concepts are defined the implementation of which reduces both the number and sensitivity to choice of parameters governing the theorem-proving procedures.
A Backtrack Procedure for Isomorphism of Directed Graphs
Authors: Berztiss A. T.
Published: July 2002

A reasonably efficient procedure for testing pairs of directed graphs for isomorphism is important in information retrieval and other application fields in which structured data have to be matched. One such procedure, a backtrack procedure based on a representation of directed graphs by linear formulas, is described. A procedure for finding a partial subdigraph of a digraph that is isomorphic to a given digraph is also described.
Scheduling for Minimum Total Loss Using Service Time Distributions
Authors: Sevcik Kenneth C.
Published: July 2002

An analytic model of a single processor scheduling problem is investigated. The scheduling objective is to minimize the total loss incurred by a finite number of initially available requests when each request has an associated linear loss function. The assumptions of the model are that preemption is allowed with negligible loss of processor time, and that the distribution of actual service times is known for each class of requests. A request is associated with a class by any of its characteristics except its actual service time. A contrived example demonstrates that one reasonable scheduling rule does not always minimize expected total loss. The major results of the paper are the definition of a new scheduling rule based on the known service time distributions, and the proof that expected total loss is always minimized by using this new rule. Brief consideration is given to generalizations of the model in which new requests arrive randomly, and preemption requires a non-negligible amount of processor time.
Supporting cognitive models as users
Authors: Ritter Frank E. , Baxter Gordon D. , Jones Gary , Young Richard M.
Published: July 2002

Cognitive models are computer programs that simulate human performance of cognitive skills. They have been useful to HCI by predicting task times, by assisting users, and by acting as surrogate users. If cognitive models could interact with the same interfaces that users do, the models would be easier to develop and would be easier to apply as interface testers. This approach can be encapsulated as a cognitive model interface management system (CMIMS), which is analogous to and based on a user interface management system (UIMS). We present five case studies using three different UIMSes. These show how models can interact with interfaces using an interaction mechanism that is designed to apply to all interfaces generated within a UIMS. These interaction mechanisms start to support and constrain performance in the same ways that human performance is supported and constrained by interaction. Most existing UIMSes can and should be extended to create CMIMSes, and models can and should use CMIMSes to look at larger and more complex tasks. CMIMSes will help to further exploit the synergy between the disciplines of cognitive modeling and HCI by supporting cognitive models as users.
An empirical study of list structure in Lisp
Authors: Clark Douglas W. , Green C. Cordell
Published: July 2002

Static measurements of the list structure of five large Lisp programs are reported and analyzed in this paper. These measurements reveal substantial regularity, or predictability, among pointers to atoms and especially among pointers to lists. Pointers to atoms are found to obey, roughly, Zipf's law, which governs word frequencies in natural languages; pointers to lists usually point to a location physically nearby in memory. The use of such regularities in the space-efficient representation of list structure is discussed. Linearization of lists, whereby successive cdrs (or cars) are placed in consecutive memory locations whenever possible, greatly strengthens the observed regularity of list structure. It is shown that under some reasonable assumptions, the entropy or information content of a car-cdr pair in the programs measured is about 10 to 15 bits before linearization, and about 7 to 12 bits after.
A comparison of tree-balancing algorithms
Authors: Baer J.-L. , Schwab B.
Published: July 2002

Several algorithms — height-balance (i.e. AVL and extensions), weight-balance (i.e. BB and WB), and total restructuring — for building balanced binary search trees are compared. The criteria for comparison encompass theoretical aspects (e.g. path lengths) and implementation independent and machine/algorithm-dependent measures (e.g. run time). A detailed analysis of code is also presented at a level believed to be language- and compiler-independent. The quality of the resulting trees and the overhead spent on building them are analyzed, and some guidelines are given for an efficient use of the methods. If insertion and subsequent queries are the only operations of interest, then “pure” AVL trees present the overall best qualities.
Database abstractions
Authors: Smith John Miles , Smith Diane C. P.
Published: July 2002

Aggregation is introduced as an abstraction which is important in conceptualizing the real world. Aggregation transforms a relationship between objects into a higher-level object. A new data type, called aggregate, is developed which, under certain criteria of “well-definedness,” specifies aggregation abstractions. Relational databases defined as collections of aggregates are structured as a hierarchy of n-ary relations. To maintain well-definedness, update operations on such databases must preserve two invariants. Well-defined relations are distinct from relations in third normal form. It is shown that these notions are complementary and both are important in database design. A top-down methodology for database design is described which separates decisions concerning aggregate structure from decisions concerning key identification. It is suggested that aggregate types, and other types which support real-world abstractions without introducing implementation detail, should be incorporated into programming languages.
A unifying approach to scheduling
Authors: Ruschitzka Manfred , Fabry R. S.
Published: July 2002

This paper presents a scheme for classifying scheduling algorithms based on an abstract model of a scheduling system which formalizes the notion of priority. Various classes of scheduling algorithms are defined and related to existing algorithms. A criterion for the implementation efficiency of an algorithm is developed and results in the definition of time-invariant algorithms, which include most of the commonly implemented ones. For time-invariant algorithms, the dependence of processing rates on priorities is derived. The abstract model provides a framework for implementing flexible schedulers in real operating systems. The policy-driven scheduler of Bernstein and Sharp is discussed as an example of
On quadratic adaptive routing algorithms
Authors: Agnew Carson E.
Published: July 2002

Two analytic models of a store-and-forward communications network are constructed, one to find the optimal message routing and the other to illustrate the equilibrium (stationary state) maintained by an adaptive routing algorithm. These models show that adaptive routing does not satisfy the necessary conditions for an optimal routing. Adaptive routing tends to overuse the direct path and underuse alternate routes because it does not consider the impact of its current routing decision on the future state of the network. The form of the optimality conditions suggests that a modification of the adaptive algorithm will result in optimality. The modification requires the substitution of a quadratic bias term instead of a linear one in the routing table maintained at each network node. Simulation results are presented which confirm the theoretical analysis for a simple network.
A stochastic evaluation model for database organizations in data retrieval systems
Authors: Siler Kenneth F.
Published: July 2002

Experimental work in the valuation of large scale data retrieval systems has been scarce due to its difficulty and prohibitive cost. This paper discusses a simulation model of a data retrieval system which has the effect of significantly reducing the cost of experimentation and enabling research never attempted before. The model is designed to estimate the retrieval workload of alternative data retrieval systems. These data retrieval systems can be organized under several database organizations, including inverted list, threaded list, and cellular list organizations and hybrid combinations of these systems. Effectiveness of the methodology is demonstrated by using the model to study the effect of database organizations in data retrieval systems. In particular, the impact of query complexity is analyzed.
Characteristics of program localities
Authors: Madison A. Wayne , Batson Alan P.
Published: July 2002

The term “locality” has been used to denote that subset of a program's segments which are referenced during a particular phase of its execution. A program's behavior can be characterized in terms of its residence in localities of various sizes and lifetimes, and the transitions between these localities. In this paper the concept of a locality is made more explicit through a formal definition of what constitutes a phase of localized reference behavior, and by a corresponding mechanism for the detection of localities in actual reference strings. This definition provides for the existence of a hierarchy of localities at any given time, and the reasonableness of the definition is supported by examples taken from actual programs. Empirical data from a sample of production Algol 60 programs is used to display distributions of locality sizes and lifetimes, and these results are discussed in terms of their implications for the modeling of program behavior and memory management in virtual memory systems.
More on
k
th shortest paths
Authors: Fox B. L.
Published: July 2002

In a recent paper [4], Minieka proposes an algorithm for finding
k
th shortest paths between all pairs of nodes in an
N
node network. His claimed time is
O
(
k
2
N
3
).
Register allocation via usage counts
Authors: Freiburghouse R. A.
Published: July 2002

This paper introduces the notion of usage counts, shows how usage counts can be developed by algorithms that eliminate redundant computations, and describes how usage counts can provide the basis for register allocation. The paper compares register allocation based on usage counts to other commonly used register allocation techniques, and presents evidence which shows that the usage count technique is significantly better than these other techniques.
Common phrases and minimum-space text storage
Authors: Wagner Robert A.
Published: July 2002

A method for saving storage space for text strings, such as compiler diagnostic messages, is described. The method relies on hand selection of a set of text strings which are common to one or more messages. These phrases are then stored only once. The storage technique gives rise to a mathematical optimization problem: determine how each message should use the available phrases to minimize its storage requirement. This problem is nontrivial when phrases which overlap exist. However, a dynamic programming algorithm is presented which solves the problem in time which grows linearly with the number of characters in the text. Algorithm 444 applies to this paper.
Least squares piecewise cubic curve fitting
Authors: Ferguson J. , Staley P. A.
Published: July 2002

The matrices involved in a linear least squares formulation are determined for the problem of fitting piecewise cubic functions, those possessing a continuous derivative, to arrays of planar data.
Multiple exits from a loop without the GOTO
Authors: Bochmann G. V.
Published: July 2002

For several years, there has been discussion about the use of the
goto
statement in programming languages [1, 2]. It has been pointed out that
goto
free programs tend to be easier to understand, allow better optimization by the compiler, and are better suited for an eventual proof of correctness. On the other hand, the
goto
statement is a flexible tool for many programmers. Most programming languages have constructs which allow the programmer to write control flows that occur frequently without the use of a
goto
. In particular, the language Pascal [3] contains, besides the
goto
, the following control structures:
if-then-else
,
case
,
while-do
,
repeat-until
, stepping loop. Wulf [4] has described the use of the construct “
leave
〈label〉” in the language Bliss, where 〈label〉 is the name of a program section which is exited when the statement is executed. It is important to note that these constructs are invented to describe control flows that occur frequently in programs. They describe the flow on a higher level [5] than an equivalent construction using a
goto
would do.
Simple
LR(k)
grammars
Authors: DeRemer Franklin L.
Published: July 2002

A class of context-free grammars, called the “Simple
LR
(
k
)” or
SLR
(
k
) grammars is defined. This class has been shown to include weak precedence and simple precedence grammars as proper subsets. How to construct parsers for the
SLR
(
k
) grammars is also shown. These parser-construction techniques are extendible to cover all of the
LR
(
k
) grammars of Knuth; they have been implemented and by direct comparison proved to be superior to precedence techniques, not only in the range of grammars covered, but also in the speed of parser construction and in the size and speed of the resulting parsers.
The Altran system for rational function manipulation — a survey
Authors: Hall Andrew D.
Published: July 2002

Altran is a complete system for symbolic computation with rational functions in several variables with integer coefficients. It has been designed and implemented to handle large problems with ease and efficiency. Considerable effort has been spent to ensure a minimum amount of machine dependence in the implementation, thus permitting the system to be installed quickly and easily on a variety of computing machines. In this paper a brief description of the language, run time data structures, and implementation is given.
The allocation of computer resources—is pricing the answer?
Authors: Nielsen Norman R.
Published: July 2002

The widespread use of complex third generation computing systems has led to a much broader concern about the means by which the resources of these systems are allocated among the user community. One means that is suggested more and more frequently is a pricing procedure. In this paper the manner in which one would like to allocate computing resources is considered, and then the extent to which a pricing mechanism fits this mold is discussed. Inasmuch as pricing must serve as a rationing mechanism at times, consideration is given to the means by which prices can be adjusted flexibly in order to make a dynamic allocation of resources. Consideration is also given to the means by which users can be insulated from the harmful effects of frequent price fluctuations.

Although the subject of pricing has been given a lot of attention recently, a number of misconceptions persist about its purpose and its operation. An attempt is made to clarify some of these misunderstandings and to highlight the advantages and disadvantages of pricing. Two illustrative pricing systems are also discussed in order to demonstrate the applicability of pricing in quite different environments.
Full table quadratic searching for scatter storage
Authors: Day A. Colin
Published: July 2002

The quadratic residue search method for hash tables avoids much of the clustering experienced with a linear search method. The simple quadratic search only accesses half the table. It has been shown that when the length of the table is a prime of the form 4
n
+ 3, where
n
is an integer, the whole table may be accessed by two quadratic searches plus a separate access for the original entry point. A search method is presented which is computationally simple, has all the advantages of the quadratic search, and yet accesses all the table in one sweep.
Description of FORMAT, a text-processing program
Authors: Berns Gerald M.
Published: July 2002

FORMAT is a production program which facilitates the editing and
printing of “finished” documents directly on the
printer of a relatively small (64k) computer system. It features
good performance, totally free-form input, very flexible formatting
capabilities including up to eight columns per page, automatic
capitalization, aids for index construction, and a minimum of
nontext items. It is written entirely in FORTRAN IV.
Operating Systems: Program overlay techniques
Authors: Pankhurst R. J.
Published: July 2002

The general features of program overlay systems are described. Three main types—automatic, semiautomatic and non-automatic—are classified, and the programming techniques are explained as a function of machine hardware and other system features. The implementation of a semiautomatic overlay facility in a multiprogrammed system on the CDC 6600 is described in detail, with special reference to real time applications.
Programming Languages: Generation of positive test matrices with known positive spectra
Authors: Hall C. A. , Porsching T. A.
Published: July 2002

Sufficient conditions are given for a real matrix to be similar to a positive matrix. This result is used to construct a similarity transformation which, when applied to a particular upper triangular matrix, yields a positive matrix with a preassigned positive spectrum.
A fast procedure for generating exponential random variables
Authors: MacLaren M. D. , Marsaglia G. , Bray T. A.
Published: July 2002

A very fast method for generating exponential random variables in a digital computer is outlined.
Use of tree structures for processing files
Authors: Sussenguth Edward H.
Published: July 2002

In data processing problems, files are frequently used which must both be searched and altered. Binary search techniques are efficient for searching large files, but the associated file organization is not readily adapted to the file alterations. Conversely, a chained file allocation permits e 1 cient alteration but cannot be searched efficiently. A file organized into a tree-like structure is discussed, and it is shown that such a file may both be searched and altered with times proportional to
s
log

s

N
, where
N
is the number of file items and
s
is a parameter of the tree. It is also shown that optimizing the value of
s
leads to a search time which is only 25 per cent slower than the binary search. The tree organization employs two data chains and may be considered to be a compromise between the organizations for the binary search and the chained file. The relation of the tree organization to multidimensional indexing and to the trie structure is also discussed.
A list-type storage technique for alphanumeric information
Authors: Bowlden Henry J.
Published: July 2002

A method which is economic in terms of space and time is proposed for the storage and manipulation of character strings of arbitrary length in a fixed word-length computer. The method is illustrated in an application to Algol-type identifiers in an Algol-like block structure.
Continued operation notation for symbol manipulation and array processing
Authors: Barnett M. P.
Published: July 2002

A brief account is given of a notational device that is very useful in the formal representation of syntaxes, string relationships and string transformation procedures and also of computing procedures that deal with arrays of functions of many variables. The device consists of the use of certain “continued operation” or “collective” symbols that are analogous to the summation symbol ∑ and continued multiplication symbol ∏ of conventional mathematics.
A computer program for editing the news
Authors: Danielson Wayne A. , Briggs Bruce
Published: July 2002

The computer news editing program is designed to perform the following functions: (1) it will input automatically those stories from the AP Teletypesetter tape which the editor wishes to use; (2) it will make additions and deletions in these stories according to instructions received from the editor; (3) it will attempt to “edit,” i.e. cut from the bottom, the stories in its possession according to (a) an overall news hole limitation, (b) a minimum-lines-per-story limitation, (c) the general interests of the paper's editor in various
categories
of news, (d) a formula which grants more space to those stories which the editor thinks are more important, and (e) the availability of news on the day in question; (4) it will print out stories cut to desired lengths and arranged in categories.

There are, of course, many editing functions which the program does not perform. It does not assign stories to pages; it does not lay out the news and advertising; it does not crop pictures nor provide for display headlines; it does not cut stories (as an editor would) with regard for their meaningfulness and literary effectiveness. In short, the present program is presented more as an “aid to the editor” handling the news than as a complete computer editing system. Designing a complete editing system, though probably feasible, would be a major undertaking.
An interface for melody input
Authors: Prechelt Lutz , Typke Rainer
Published: July 2002

We present a software system, called Tunserver, which recognizes a musical tune whistled by the user, finds it in a database, and returns its name, composer, and other information. Such a service is useful for track retrieval at radio stations, music stores, etc., and is also a step toward the long-term goal of communicating with a computer much like one would with a human being. Tuneserver is implemented as a public Java-based WWW service with a database of approximately 10,000 motifs. Tune recognition is based on a highly error-resistant encoding, proposed by Parsons, that uses only the direction of the melody, ignoring the size of intervals as well as rhythm. We present the design and implementation of the tune recognition core, outline the design of the Web service, and describe the results obtained in an empirical evaluation of the new interface, including the derivation of suitable system parameters, resulting performance figures, and an error analysis.
A simple on-line bin-packing algorithm
Authors: Lee C. C. , Lee D. T.
Published: July 2002

The one-dimensional on-line bin-packing problem is considered, A simple
O
(1)-space and
O
(
n
)-time algorithm, called HARMONIC

M

, is presented. It is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the
O
(
n
)-space and
O
(
n
log
n
)-time algorithm FIRST FIT. Also shown is that 1.691 … is a lower bound for
all
0
(1)-space on-line bin-packing algorithms. Finally a revised version of HARMONIC

M

, an
O
(
n
)-space and
O
(
n
)- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636.
An intelligent distributed environment for active learning
Authors: Shang Yi , Shi Hongchi , Chen Su-Shing
Published: July 2002

Active learning is an effective learning approach. In this article we present an intelligent agent-assisted environment for active learning to better support the student-centered, selfpaced, and highly interactive learning approach. The environment uses the students learningrelated profile such as learning style and background knowledge in selecting, organizing, and presenting learning material, and it adopts a new approach to course content organization and delivery based on smart instructional components that can be integrated into a wide range of courses. The environment is being implemented using the prevalent Internet, Web, digital library, and multiagent technologies.
Plotting contour surfaces of a function of three variables
Authors: Sewell Granville
Published: July 2002

A technique is presented for the graphical representation of some contour (level) surfaces of a function of three variables defined by its values on an array of points (

x
i

,

y
j

,

z
k

). The algorithm involves drawing and projecting the contour curves corresponding to the cross sections
x
=

x
I

and
y
=

y
j

. Because the curves are drawn as thick, opaque bands, which mask all bands in the immediate background, a sense of depth is retained, yet background contours are still visible between the bands.
A homogeneous relational model and query languages for temporal databases
Authors: Gadia Shashi K.
Published: July 2002

In a temporal database, time values are associated with data item to indicate their periods of validity. We propose a model for temporal databases within the framework of the classical database theory. Our model is realized as a temporal parameterization of static relations. We do not impose any restrictions upon the schemes of temporal relations. The classical concepts of normal forms and dependencies are easily extended to our model, allowing a suitable design for a database scheme. We present a relational algebra and a tuple calculus for our model and prove their equivalence. Our data model is homogeneous in the sense that the periods of validity of all the attributes in a given tuple of a temporal relation are identical. We discuss how to relax the homogeneity requirement to extend the application domain of our approach.