bluuebunny/crossref_metadata_2025 huggingface dataset:
AN OPTIMISTIC THIRD PARTY PROTOCOL TO PROTECT A MOBILE AGENT'S BINARY CODE
Authors: WESTHOFF DIRK
Published: July 2002

In the world of mobile agents, security aspects are being discussed extensively, with strong emphasis on how agents can be protected against malicious hosts and vice versa. While in recent years many research groups presented solutions offering protection schemes for hosts that receive and run un-trusted, possibly malicious agents, in the field of protecting the agent against malicious hosts, development seems to grow very slowly. This paper discusses a protocol for detecting modifications at the agent's binary code that, for a particular class of modifications, undoubtedly unmasks the attacking host. Furthermore, it is shown that in co-operation with a special kind of route protection in a lot of scenarios the protocol resists attacks from coaliting malicious hosts as well as from a single malicious host.
FROM SCENARIOS TO HIERARCHICAL BROADCASTING SOFTWARE ARCHITECTURES USING UML-RT
Authors: KRÜGER INGOLF , PRENNINGER WOLFGANG , SANDNER ROBERT , BROY MANFRED
Published: July 2002

The definition of a transparent software architecture is one of the key issues in the early development phases for complex distributed and reactive software systems. In this paper, we show how to derive an architecture systematically for systems with communication models based on broadcasting. Adequate graphical description techniques for capturing interaction requirements and logical component architectures for broadcasting systems are unavailable so far. We introduce an extension to UML's sequence diagrams to capture broadcasting scenarios. Furthermore, we present methodological steps for constructively deriving structural and behavioral aspects of the architecture under consideration from the captured scenarios.
ON PRESENTATIONS OF COMMUTATIVE MONOIDS
Authors: ROSALES J. C. , GARCÍA-SÁNCHEZ P. A. , URBANO-BLANCO J. M.
Published: July 2002

In this paper, we introduce the concept of a strongly reduced monoid and we characterize the minimal presentations for such monoids. As a consequence, we give a method to obtain a presentation for any commutative monoid.
INVERSE RADIOTHERAPY TREATMENT PLANNING MODEL APPLYING BOLTZMANN-TRANSPORT EQUATION
Authors: TERVO JOUKO , KOLMONEN PEKKA
Published: July 2002

In the external radiation therapy the source of radiation is from outside. The healthy tissue and some organs, called critical organs which are quite intolerable for radiation, are always irradiated, too. Therefore, the careful treatment plan has to be constructed to ensure high and homogeneous dose in the tumor, but on the other hand to spare the normal tissue and critical organs possibly well.

In the radiation therapy treatment planning one tries to optimize the dose distribution in the way that the above aim is satisfied. The dose distributions can be generated with different techniques. The most recent of them is the so-called multileaf collimator (MLC) delivery technique. Calculation of the dose distribution demands some dose calculation model. The paper gives a model and theoretical basis of planning applying the Boltzmann-transport equation in dose calculation and MLC delivery technique. The existence of solutions and the optimal treatment planning are considered. A preliminary artificial computer simulation is included.
ON THE RELAXATION LIMITS OF THE HYDRODYNAMIC MODEL FOR SEMICONDUCTOR DEVICES
Authors: QIU YOUCHUN , ZHANG KAIJUN
Published: July 2002

The initial-boundary value problem of a simplified one-dimensional hydrodynamic model for semiconductors is considered. The global weak solution and its relaxation limit are obtained through using the compensated compactness methods. The traces of weak solutions are also discussed.
EFFICIENT UNSUPERVISED CONTENT-BASED SEGMENTATION IN STEREOSCOPIC VIDEO SEQUENCES
Authors: DOULAMIS ANASTASIOS , DOULAMIS NIKOLAOS , NTALIANIS KLIMIS , KOLLIAS STEFANOS
Published: July 2002

This paper presents an efficient technique for unsupervised content-based segmentation in stereoscopic video sequences by appropriately combined different content descriptors in a hierarchical framework. Three main modules are involved in the proposed scheme; extraction of reliable depth information, image partition into color and depth regions and a constrained fusion algorithm of color segments using information derived from the depth map. In the first module, each stereo pair is analyzed and the disparity field and depth map are estimated. Occlusion detection and compensation are also applied for improving the depth map estimation. In the following phase, color and depth regions are created using a novel complexity-reducing multiresolution implementation of the Recursive Shortest Spanning Tree algorithm (M-RSST). While depth segments provide a coarse representation of the image content, color regions describe very accurately object boundaries. For this reason, in the final phase, a new segmentation fusion algorithm is employed which projects color segments onto depth segments. Experimental results are presented which exhibit the efficiency of the proposed scheme as content-based descriptor, even in case of images with complicated visual content.
SUGGESTION STRATEGIES FOR CONSTRAINT-BASED MATCHMAKER AGENTS
Authors: FREUDER EUGENE C. , WALLACE RICHARD J.
Published: July 2002

In this paper we describe a paradigm for content-focused matchmaking, based on a recently proposed model for constraint acquisition and satisfaction. Matchmaking agents are constraint-based solvers that interact with other, possibly human, agents (Customers). The Matchmaker provides potential solutions ("suggestions") based on partial knowledge, while gaining further information about the problem itself from the other agent through the latter's evaluation of these suggestions. The dialogue between Matchmaker and Customer results in iterative improvement of solution quality, as demonstrated in simple simulations. We also show empirically that this paradigm supports "suggestion strategies" for finding acceptable solutions more efficiently or for increasing the amount of information obtained from the Customer. This work also indicates some ways in which the tradeoff between these two metrics for evaluating performance can be handled.
POWER FILTRATION OF CMB OBSERVATIONAL DATA
Authors: NOVIKOV D. I. , NASELSKY P. , JØRGENSEN H. E. , CHRISTENSEN P. R. , NOVIKOV I. D. , NØRGAARD-NIELSEN H. U.
Published: July 2002

We propose a power filter G p for linear reconstruction of the CMB signal from one-dimensional scans of observational maps. This G p filter preserves the power spectrum of the CMB signal in contrast to the Wiener filter which diminishes the power spectrum of the reconstructed CMB signal. We demonstrate how peak statistics and a cluster analysis can be used to estimate the probability of the presence of a CMB signal in observational records. The efficiency of the G p filter is demonstrated on a toy model of an observational record consisting of a CMB signal and noise in the form of foreground point sources.
FOUR- AND HIGHER-DIMENSIONAL MODELS WITH DILATON–ELECTROMAGNETIC FIELDS
Authors: CHAKRABORTY NARAYAN CHANDRA , CHAKRABORTY SUBENOY
Published: July 2002

The Einstein–Maxwell dilaton field equations are constructed for four-dimensional Bianchi III and five-dimensional FRW models. The general solutions have been obtained and their asymptotic behavior have been studied.
DYNAMICS OF EJECTION FROM GALAXIES AND THE VARIABLE MASS HYPOTHESIS
Authors: NARLIKAR J. V. , VISHWAKARMA R. G. , BANERJEE S. K. , DAS P. K. , ARP H. C.
Published: July 2002

Increasing numbers of active galaxies with significant alignments of quasars are being observed. It is the purpose of this paper to explore ejection dynamics of these quasars using the variable mass hypothesis (VMH) originally discussed by Narlikar and Das in 1980. According to the VMH quasars are ejected from parent galaxies initially with zero rest mass which grows through a Machian interaction. The intrinsic redshift of the quasar steadily decreases as its mass grows, but always remains in excess of the redshift of the galaxy. The ultimate aim of this hypothesis is to quantitatively relate the observed ordering of redshifts of ejected quasars, with separation from the galaxy, their intrinsic redshifts and the age of the evolutionary stage of the ejecta.
RELATIVISTIC ELECTRONS IN A ROTATING SPHERICAL MAGNETIC DIPOLE: LOCALIZED THREE-DIMENSIONAL STATES
Authors: GELB JAMES M. , GOPINATH KAUNDINYA S. , KENNEDY DALLAS C.
Published: July 2002

Paralleling a previous paper, we examine single- and many-body states of relativistic electrons in an intense, rotating magnetic dipole field. Single-body orbitals are derived semiclassically and then applied to the many-body case via the Thomas-Fermi approximation. The many-body case is reminiscent of the quantum Hall state. Electrons in a realistic neutron star crust are considered with both fixed density profiles and constant Fermi energy. In the first case, applicable to young neutron star crusts, the varying magnetic field and relativistic Coriolis correction lead to a varying Fermi energy and macroscopic currents. In the second, relevant to older crusts, the electron density is redistributed by the magnetic field.
SCALE INVARIANT COSMOLOGY
Authors: MIDY PIERRE , PETIT JEAN-PIERRE
Published: July 2002

An attempt is made here to extend to the microscopic domain the scale invariant character of gravitation — which amounts to consider expansion as applying to any physical scale. Surprisingly, this hypothesis does not prevent the redshift from being obtained. It leads to strong restrictions concerning the choice between the presently available cosmological models and to new considerations about the notion of time. Moreover, there is no horizon problem and resorting to inflation is not necessary.
CHIRAL UNIFICATION OF ELECTROWEAK AND GRAVITATIONAL INTERACTIONS
Authors: COHEN MARCUS
Published: July 2002

Vector potentials and their associated fields are embodied in the left and right spin connections and their spin curvatures. These measure the path-dependence of the transport of spin frames, or the "vorticity of the spinfluid," produced by local sources. Electroweak interactions emerge from PT-antisymmetric u(1) × su(2) phase perturbations of the spin frames which do not show up in the spacetime tetrad. Gravitation emerges from PT-symmetric spin perturbations, whose path dependence shows up as spacetime curvature. We also predict a new "nonsymmetric" component of electrogravitation on particles with nontrivial electroweak form factors.
BIOLOGICAL RECEPTORS: IMPLICATIONS OF RADIOLIGAND QUALITY IN BINDING ASSAYS
Authors: VENTURINO ANDRÉS , RIVERA ELENA S.
Published: July 2002

We tested the ability of different fitting procedures to discern differences in the binding affinity between the labeled and unlabeled ligand in a receptor assay, in order to obtain the correct value of the radiotracer specific activity. This point is critical for the correct conversion of the estimated binding constants to meaningful units. We simulated sets of receptor assays which considered distinct experimental situations, and fitted the data with two models considering either a unique or two different affinities for the two classes of ligand. We compared direct non-linear regression, linear robust regression on transformed data, and an experimental approach called pseudo-saturation (labeled plus unlabeled ligand in constant ratio) assay.

It emerges from the results that none of these methods would be sensitive enough, even in commonly acceptable error levels in the measured variables, to indicate the appropriate model with a reasonable certainty. The a priori consideration of a different binding capacity for both categories of the ligand gives an acceptable estimation of the parameters, regardless of the fact that the fitting criteria reflect a better fitting of the other model. We conclude that a two-affinity binding model should be routinely fitted to experimental data and the binding constants compared to the simple binding model when the specific activity of the radiotracer needs to be assessed.
ON THE WAITING TIME PARADOX AND RELATED TOPICS
Authors: HUILLET THIERRY
Published: July 2002

Consider a pure recurrent positive renewal process generated by some interarrival waiting time. The waiting time paradox reveals that, asymptotically, the time interval covering one's arrival in the file is statistically longer than the typical waiting time. Special properties are known to hold, were the waiting time to be infinitely divisible, two particular subclasses of interest being the exponential power mixtures' and the Lévy's ones. These models are revisited in some detail. Questions related to these problems are investigated and special examples of interest are underlined.
A FREQUENCY DOMAIN INVERSION METHOD APPLIED TO OBLIQUE REFLECTED SIGNALS FROM A WATER–SEDIMENT INTERFACE
Authors: VANDENPLAS S. , TEMSAMANI A. B. , CISNEROS Z. , VAN BIESEN L.
Published: July 2002

Due to the complexity of the seafloor as an acoustical system, it is very important to validate wave propagation models and test inversion methods first in the laboratory. A known sediment is placed in a water-filled tank, in such a way that a smooth water–sediment interface is obtained with minimal air bubbles retained in the sediment. Two broadband piston transducers are used to carry out reflection experiments at oblique incidence. The placement of the emitter and receiver is symmetrical with respect to a vertical plane perpendicular to the sediment surface. The aim of this work is to find physical parameters of the sediment from the reflected signals. A general viscoelastic model that considers losses due to absorption and dispersion along the propagation of the wave through the sediments is proposed. A rational transfer function is used to model the viscoelastic modulus of the bulk sediments and a comparison with constant Q viscoelastic modelling is performed. The estimation of the model parameters is elaborated using a Maximum Likelihood Estimator in the frequency domain.
FABRICATION OF BIMETALLIC CANTILEVERS AND ITS CHARACTERIZATION
Authors: JUNG MI-YOUNG , CHOI S. S. , KANG C. J. , KUK Y.
Published: July 2002

Most SPM sensors utilize a current-imaging technique or force-imaging techniques that allow imaging nanoscale topography of the surface using a nanoscale tip on cantilever. In this work, the various cantilevers were microfabricated with a SiO 2 thin film or a Si 3 N 4 thin film. Thermal imaging technique using microfabricated Si 3 N 4 cantilevers has been investigated. The temperature change and heat flow across the fabricated bimetallic cantilever will create angular bending of the bimetallic metal-coated lever. Its thermal response was qualitatively examined during an endothermic chemical reaction using optical deflection methods. The chemical used in this experiment is the tetradecanol CH 3( CH 2)13 OH , with a known theoretical phase transition temperature of ~ 313 K.
THE EFFECT OF ASPIRIN AND PROSTAGLANDINE1ON THE PATENCY OF MICROVASCULAR ANASTOMOSIS IN THE RATS
Authors: Lee Kwang Suk , Suh Jeong Dae , Han Seung Beom , Yoo Jae Chul , Lee Seoung Joon , Cho Seong Jin
Published: July 2002

The purpose of this study was to evaluate the effect of oral prostaglandin E1( PGE1) on the patency of the microvascular anastomosis of the carotid artery in rat. A total of 48 rats were used, and divided into three groups. The first group (A) was used as a control with no medical agent being used after anastomosis, the second group (B) was medicated with aspirin, and the third group (C) was medicated with oral PGE1. In each group, four rats were sacrificed serially on every post-operative 3, 5, 10 and 15 days after arterial anastomosis. Patency and histologic evaluations at the anastomotic site were observed. The results revealed that the PGE1therapied group showed highest patency rate (100%), lesser formation of mural thrombosis, and also minimal changes in the intimal hyperplasia and medial fibrosis. From these findings, we could conclude that PGE1has superior effect on maintaining the patency after microvascular surgery.
SYNOVECTOMY, JOINT RELEASE AND LATERAL BAND TRANSLOCATION FOR STIFF SWAN NECK DEFORMITY
Authors: Tonkin Michael A , Gianoutsos Mark P , Ryan Damian , Duckworth David
Published: July 2002

This paper presents the results of surgery on 36 fingers, in 15 patients with swan neck deformity treated by synovectomy, joint release and lateral band translocation. Overall, the range of motion postoperatively was 56 degrees and the arc was transposed to a more functional position (centre of arc of motion at 12 degrees preoperatively versus 42 degrees postoperatively). Even the more severe Type 5 deformity as well as those fingers with evidence of degenerative change, derived lasting benefit from the procedure, both in terms of range and arc of motion. This technique of treating stiff swan neck deformity is an effective means of obtaining a greater and more functional range of motion and maintaining it in the medium term.
A SIMPLE MODEL FOR THE NONEQUILIBRIUM DYNAMICS AND EVOLUTION OF A FINANCIAL MARKET
Authors: FARMER J. DOYNE
Published: July 2002

By developing a simple model for market making, price formation can be studied in a nonequilibrium setting. Commonly used trading strategies, such as value investing based on fundamentals, or technical trading based on past price history, generate characteristic price dynamics, including excess volatility, clustered volatility, and long tails. The long term evolution of capital in the market can be modeled in terms of reinvestment of profits, which when combined with the price formation rule leads to generalized Lotka–Volterra equations, originally developed to model predator-prey systems in ecology. Sensible estimates of the characteristic time for substantial capital reallocations are years to decades, suggesting that the progression toward market efficiency may be rather slow.
STRONGLY MEAGER SETS DO NOT FORM AN IDEAL
Authors: BARTOSZYNSKI TOMEK , SHELAH SAHARON
Published: July 2002

A set X⊆ℝ is strongly meager if for every measure zero set H, X+H ≠ℝ. Let [Formula: see text] denote the collection of strongly meager sets. We show that assuming [Formula: see text], [Formula: see text] is not an ideal.
PERFORMANCE ANALYSIS OF A MAC PROTOCOL FOR BROADBAND WIRELESS ATM NETWORKS WITH QUALITY OF SERVICE PROVISIONING
Authors: VAN HOUDT B. , BLONDIA C. , CASALS O. , GARCÍA J.
Published: July 2002

This paper presents a Medium Access Control (MAC) protocol for broadband wireless LANs based on the ATM transfer mode, together with the evaluation of its performance in terms of throughput and access delay. Important characteristics of the MAC protocol are the way information between the Mobile Stations (MSs) and the Base Station (BS) is exchanged and the algorithm used to allocate the bandwidth in order to support the service categories. A detailed analytical evaluation, both on cell level and packet level, leads to an assessment of the efficiency and the access delay of the system.
ADMITTANCE FIELD METHOD FOR THE CALCULATION OF THE SPECTRAL DENSITY OF CURRENT FLUCTUATIONS
Authors: SHIKTOROV PAVEL , STARIKOV EVGENIJ , GRUŽINSKIS VIKTORAS , VARANI LUCA , VAISSIERE JEAN-CLAUDE , NOUGIER JEAN-PIERRE , REGGIANI LINO
Published: July 2002

In the framework of the Green-function formalism the admittance field method is proposed for the calculation of the spectral density of current fluctuations of two and more terminal devices. The usefulness of the theory is illustrated by hydrodynamic calculations performed for a submicron GaAs structure. The unifying property of the formalism evidences the same physical ground of both the admittance and impedance field methods when instantaneous fluctuations of carrier accelerations during scattering events are taken as noise sources.
STOCHASTIC VERSIONS OF ANOSOV'S AND NEISTADT'S THEOREMS ON AVERAGING
Authors: KIFER YURI
Published: July 2002

In systems which combine slow and fast motions the averaging principle says that a good approximation of the slow motion can be obtained by averaging its parameters in fast variables. This setup arises, for instance, in perturbations of Hamiltonian systems where motions on constant energy manifolds are fast and across them are slow. When these perturbations are deterministic Anosov's theorem says that the averaging principle works except for a small in measure set of initial conditions while Neistadt's theorem gives error estimates in the case of perturbations of integrable Hamiltonian systems. These results are extended here to the case of fast and slow motions given by stochastic differential equations.
PERIODICITY AND SHARKOVSKY'S THEOREM FOR RANDOM DYNAMICAL SYSTEMS
Authors: KLÜNGER MARC
Published: July 2002

We generalize the deterministic notion of periodicity to random dynamical systems, which leads to three different objects, called random periodic orbits, point and cycles. We analyze the relation of these three notions and prove a "random fixed point theorem" for one-dimensional random dynamical systems. Finally we use these notions to prove partial generalizations of Sharkovsky's theorem to random dynamical systems.
TWO-STEP TRANSITION IN NONAUTONOMOUS BIFURCATIONS: AN EXPLANATION
Authors: JOHNSON R. A. , KLOEDEN P. E. , PAVANI R.
Published: July 2002

We consider the two-step bifurcation scenario which has been studied by L. Arnold and his co-workers. We formulate a "continuous case" and a "measurable case" of the scenario, and present results and conjectures regarding sufficient conditions that it take place.
LYAPUNOV EXPONENTS AND RESONANCE FOR SMALL PERIODIC AND RANDOM PERTURBATIONS OF A CONSERVATIVE LINEAR SYSTEM
Authors: BAXENDALE PETER H.
Published: July 2002

We give algorithms for the asymptotic expansions of the almost sure and moment Lyapunov exponents associated with the two-dimensional stochastic differential equation obtained as a small perturbation of the deterministic rotation with rate ω. The matrices in the perturbation terms are all assumed to be periodic functions of time with period l. The form of the algorithms depends on whether or not the periods 2π/ω and l of the unperturbed system and the perturbation coefficients are commensurable (i.e. the ratio of the periods is rational). In the commensurable case certain resonances may cause jumps in the Lyapunov exponents. We give an example of a stochastically perturbed Hill's oscillator which is almost surely stable when 2ω is not an integer, but is almost surely unstable at resonant frequencies ω = m/2. This work extends recent results of Imkeller and Milstein.
A DYNAMIC THEORY OF A FIRM: AN APPLICATION OF 'ECONOMIC FORCES'
Authors: ESTOLA MATTI
Published: July 2002

Static neoclassical theory of a firm and its dynamization by dynamic optimization assume profit functions inconsistent with each other. As a solution to this, we present a dynamic theory of a firm which is consistent with the static neoclassical theory. We define the 'economic forces' which act upon the production of the firm and show that the adjustment of production in a profit-seeking way may be stable or unstable. Explosive unstable production dynamics may occur due to 'economies of scale' or due to the development of wealth or technology; in stable cases the adjustment leads to the profit maximizing situation. Our model provides a micro basis for the modeling of economic growth at macro-level.
Formalizing the gene centered view of evolution
Authors: Bar-Yam Yaneer
Published: July 2002

A historical dispute in the conceptual underpinnings of evolution is the validity of the gene centered view of evolution (Dawkins, 1989; Sober and Lewontin, 1982). We transcend this debate by formalizing the gene centered view as a dynamic version of the mean field approximation. This establishes the conditions under which it is applicable and when it is not. In particular, it breaks down for trait divergence which corresponds to symmetry breaking in evolving populations.
Functional specification of time-sensitive communicating systems
Authors: Broy Manfred
Published: July 2002

A formal model and a logical framework for the functional specification of time-sensitive communicating systems and their interacting components are outlined. The specification method is modular with respect to sequential composition, parallel composition, and communication feedback. Nondeterminism is included by underspecification. The application of the specification method to timed communicating functions is demonstrated. Abstractions from time are studied. In particular, a rational is given for the chosen concepts of the functional specification technique. The relationship between system models based on nondeterminism and system models based on explicit time notions is investigated. Forms of reasoning are considered. The alternating bit protocol is used as a running example.
Lightweight recoverable virtual memory
Authors: Satyanarayanan M. , Mashburn Henry H. , Kumar Puneet , Steere David C. , Kistler James J.
Published: July 2002

Recoverable virtual memory
refers to regions of a virtual address space on which transactional guarantees are offered. This article describes RVM, an efficient, portable, and easily used implementation of recoverable virtual memory for Unix environments. A unique characteristic of RVM is that it allows independent control over the transactional properties of atomicity, permanence, and serializability. This leads to considerable flexibility in the use of RVM, potentially enlarging the range of applications that can benefit from transactions. It also simplifies the layering of functionality such as nesting and distribution. The article shows that RVM performs well over its intended range of usage even though it does not benefit from specialized operating system support. It also demonstrates the importance of intra- and inter-transaction optimizations.
Digital inversive pseudorandom numbers
Authors: Eichenauer-Herrmann Jürgen , Niederreiter Harald
Published: July 2002

A new algorithm, the
digital inversive method
, for generating uniform pseudorandom numbers is introduced. This algorithm starts from an inversive recursion in a large finite field and derives pseudorandom numbers from it by the digital method. If the underlying finite field has
q
elements, then the sequences of digital inversive pseudorandom numbers with maximum possible period length
q
can be characterized. Sequences of multiprecision pseudorandom numbers with very large period lengths are easily obtained by this new method. Digital inversive pseudorandom numbers satisfy statistical independence properties that are close to those of truly random numbers in the sense of asymptotic discrepancy. If
q
is a power of 2, then the digital inversive method can be implemented in a very fast manner.
Implications of hierarchical N-body methods for multiprocessor architectures
Authors: Singh Jaswinder Pal , Hennessy John L. , Gupta Anoop
Published: July 2002

To design effective large-scale multiprocessors, designers need to understand the characteristics of the applications that will use the machines. Application characteristics of particular interest include the amount of communication relative to computation, the structure of the communication, and the local cache and memory requirements, as well as how these characteristics scale with larger problems and machines. One important class of applications is based on hierarchical N-body methods, which are used to solve a wide range of scientific and engineering problems efficiently. Important characteristics of these methods include the nonuniform and dynamically changing nature of the domains to which they are applied, and their use of long-range, irregular communication. This article examines the key architectural implications of representative applications that use the two dominant hierarchical N-body methods: the Barnes-Hut Method and the Fast Multipole Method.

We first show that exploiting temporal locality on accesses to communicated data is critical to obtaining good performance on these applications and then argue that coherent caches on shared-address-space machines exploit this locality both automatically and very effectively. Next, we examine the implications of scaling the applications to run on larger machines. We use scaling methods that reflect the concerns of the application scientist and find that this leads to different conclusions about how communication traffic and local cache and memory usage scale than scaling based only on data set size. In particular, we show that under the most realistic form of scaling, both the communication-to-computation ratio as well as the working-set size (and hence the ideal cache size per processor) grow slowly as larger problems are run on larger machines. Finally, we examine the effects of using the two dominant abstractions for interprocessor communication: a shared address space and explicit message passing between private address spaces. We show that the lack of an efficiently supported shared address space will substantially increase the programming complexity and performance overheads for these applications.
Analysis of an importance sampling estimator for tandem queues
Authors: Glasserman Paul , Kou Shing-Gang
Published: July 2002

We analyze the performance of an importance sampling estimator for a rare-event probability in tandem Jackson networks. The rare event we consider corresponds to the network population reaching
K
before returning to ø, starting from ø, with
K
large. The estimator we study is based on interchanging the arrival rate and the smallest service rate and is therefore a generalization of the asymptotically optimal estimator for an M/M/1 queue. We examine its asymptotic performance for large
K
, showing that in certain parameter regions the estimator has an asymptotic efficiency property, but that in other regions it does not. The setting we consider is perhaps the simplest case of a rare-event simulation problem in which boundaries on the state space play a significant role.
Generation of formatters for context-free languages
Authors: van den Brand Mark , Visser Eelco
Published: July 2002

Good documentation is important for the production of reusable and maintainable software. For the production of accurate documentation it is necessary that the original program text is not copied manually to obtain a typeset version. Apart from being tedious, this will invariably introduce errors. The production of tools that support the production of legible and accurate documentation is a software engineering challenge in itself. We present an algebraic approach to the generation of tools that produce typographically effective presentations of computer programs. A specification of a formatter is generated from the context-free grammar of a (programming) language. These generated formatters translate abstract syntax trees of programs into box expressions. Box expressions are translated by language-independent interpreters of the box language into ASCII or T
E
X. The formatting rules that are generated can easily be tuned in order to get the desired formatting of programs. We demonstrate this by means of real-life applications. Furthermore, we give a practical solution for the problem of formatting comments, which occur in the original text. The formatter generation approach proposed in this article can be used to generate formatting programs for arbitrary programming environments. Our formatter generation approach can be used to automatically generate formatters that have to be programmed explicitly in other systems.
Decidability of the purely existential fragment of the theory of term algebras
Authors: Venkataraman K. N.
Published: July 2002

This paper is concerned with the question of the
decidability
and the
complexity
of the decision problem for certain fragments of the theory of free
term algebras
. The existential fragment of the theory of term algebras is shown to be decidable through the presentation of a nondeterministic algorithm, which, given a quantifier-free formula
P
, constructs a solution for
P
if it has one and indicates failure if there are no solutions. It is shown that the decision problem is in NP by proving that, if a quantifier-free formula
P
has a solution, then there is one that can be represented as a dag in space at most cubic in the length of
P
. The decision problem is shown to be complete for NP by reducing 3-SAT to that problem. Thus it is established that the existential fragment of the theory of pure list structures in the language of NIL, CONS, CAR, CDR, =, ≤ (subexpression) is NP-complete. It is further shown that even a slightly more expressive fragment of the theory of term algebras, the one that allows bounded universal quantifiers, is undecidable.
Supporting concurrency, communication, and synchronization in human-computer interaction—the Sassafras UIMS
Authors: Hill Ralph D.
Published: July 2002

Sassafras is a prototype User Interface Management System (UIMS) specifically designed to support a wide range of user interface styles. In particular, it supports the implementation of user interfaces where the user is free to manipulate multiple input devices and perform several (possibly related) tasks concurrently. These interfaces can be compactly represented and efficiently implemented without violating any of the rules of well-structured programming. Sassafras also supports elaborate run-time communication and synchronization among the modules that make up the user interface. This is needed to implement user interfaces that have context-sensitive defaults, and it simplifies recovery from semantic errors.

Sassafras is based on a new language for specifying the syntax of human-computer dialogues known as Event-Response Language (ERL) and a new run-time structure and communication mechanism for UIMSs known as the Local Event Broadcast Method (LEBM). Both ERL and LEBM are described in detail, and implementation techniques are presented. The effectiveness of Sassafras is demonstrated by describing two interfaces that have been implemented with Sassafras.
Disjunctive datalog
Authors: Eiter Thomas , Gottlob Georg , Mannila Heikki
Published: July 2002

We consider disjunctive Datalog, a powerful database query language based on disjunctive logic programming. Briefly, disjunctive Datalog is a variant of Datalog where disjunctions may appear in the rule heads; advanced versions also allow for negation in the bodies which can be handled according to a semantics for negation in disjunctive logic programming. In particular, we investigate three different semantics for disjunctive Datalog: the minimal model semantics the perfect model semantics, and the stable model semantics. For each of these semantics, the expressive power and complexity are studied. We show that the possibility variants of these semantics express the same set of queries. In fact, they precisely capture the complexity class Σ
P
2
. Thus, unless the Polynomial Hierarchy collapses, disjunctive Datalog is more expressive that normal logic programming with negation. These results are not only of theoretical interest; we demonstrate that problems relevant in practice such as computing the optimal tour value in the Traveling Salesman Problem and eigenvector computations can be handled in disjunctive Datalog, but not Datalog with negation (unless the Polynomial Hierarchy collapses). In addition, we study modularity properties of disjunctive Datalog and investigate syntactic restrictions of the formalisms.
Learning to reason
Authors: Khardon Roni , Roth Dan
Published: July 2002

We introduce a new framework for the study of reasoning. The Learning (in order) to Reason approach developed here views learning as an integral part of the inference process, and suggests that learning and reasoning should be studied together.

The Learning to Reason framework combines the interfaces to the world used by known learning models with the reasoning task and a performance criterion suitable for it. In this framework, the intelligent agent is given access to its favorite learning interface, and is also given a grace period in with it can interact with this interface and construct a representation KB of the world
W
. The reasoning performance is measured only after this period, when the agent is presented with queries α from some query language, relevant to the world, and has to answer whether
W
implies α.

The approach is meant to overcome the main computational difficulties in the traditional treatment of reasoning which stem from its separation from the “world”. Since the agent interacts with the world when construction its knowledge representation it can choose a representation that is useful for the task at hand. Moreover, we can now make explicit the dependence of the reasoning performance on the environment the agent interacts with.

We show how previous results from learning theory and reasoning fit into this framwork and illustrate the usefulness of the Learning to Reason approach by exhibiting new results that are not possible in the traditional setting. First, we give Learning to Reason algorithms for classes of propositional languages for which there are no efficient reasoning algorithms, when represented as a traditional (formula-based) knowledge base. Second, we exhibit a Learning to Reason algorithm for a class of propositional languages that is not know to be learnable in the traditional sense.
A new viewpoint on code generation for directed acyclic graphs
Authors: Liao S. , Keutzer K. , Tjiang S. , Devadas S.
Published: July 2002

We present a new viewpoint on code generation for directed acyclic graphs (DAGs). Our formulation is based on
binate covering
, the problem of satisfying, with minimum cost, a set of disjunctive clauses, and can take into account commutativity of operators and of the machine model. An important contribution of this work is a set of necessary and sufficient conditions for a valid schedule to be derived, based on the notion of
worms
and
worm-partitions
. This set of conditions can be compactly expressed with clauses that relate scheduling to code selection. For the case of one-register machines, we can derive clauses that lead to generation of optimal code for the DAG. Recent advances in exact binate covering algorithms allows us to use this strategy to generate optimal code for large basic blocks. The optimal code generated by our algorithm results in significant reductions in overall code size.
Data sharing in group work
Authors: Greif Irene , Sarin Sunil
Published: July 2002

Data sharing is fundamental to computer-supported cooperative work: People share information through explicit communication channels and through their coordinated use of shared databases. This paper examines the data management requirements of group work applications on the basis of experience with three prototype systems and on observations from the literature. Database and object management technologies that support these requirements are briefly surveyed, and unresolved issues in the particular areas of access control and concurrency control are identified for future research.
PELLPACK
Authors: Houstis E. N. , Rice J. R. , Weerawarana S. , Catlin A. C. , Papachiou P. , Wang K.-Y. , Gaitatzes M.
Published: July 2002

The article presents the software architecture and implementation of the problem-solving environment (PSE) PELLPACK for modeling physical objects described by partial differential equations (PDEs). The scope of this PSE is broad, as PELLPACK incorporates many PDE solving systems, and some of these, in turn, include several specific PDE solving methods. Its coverage for 1D, 2D. and 3D elliptic or parabolic problems is quite broad, and it handles some hyperbolic problems, Since a PSE should provided complete support for the problem-solving process, PELLPACK also contains a large amount of code to support graphical user interfaces, analystic tools, user help, domain or mesh partitioning, machine and data selection, visualization, and various other tasks. Its total size is well over 1 million lines code. Its open-ended software architecture consists of several software layers. The top layer is an interactive graphical interface for specifying the PDE model and its solution framework This interface saves that results of the user specification in the form of a very high level PDE language which is an alternative interface to the PELLPACK system. This language also allows a user to specify the PDE problem and its solution framework textually in a natural form. The PELLPACK language preprocessor generates a Fortran control program with the interfaces, calls to specified components and libraries of the PDE solution framework, and functions defining the PDE problem. The PELLPACK program execution is supported by a hign-level tool where the virtual parallel system is defined, where the compilation, loading, and execution are controlled. Finally, the PELLPACK PSE integrates several PDE libraries and PDE systems based on the decomposition of discrete geometric data to map sparse PDE computations to parallel machines. An instance of the system is available as aWeb server(WebPELLPACK) for public use at http://pellpack.cs.purdue.edu.
Bounded-skew clock and Steiner routing
Authors: Cong Jason , Kahng Andrew B. , Koh Cheng-Kok , Tsao C.-W. Albert
Published: July 2002

We study the minimum-cost bounded-skew routing tree problem under the pathlength (linear) and Elmore delay models. This problem captures several engineering tradeoffs in the design of routing topologies with controlled skew. Our bounded-skew routing algorithm, called the BST/DME algorithm, extends the DME algorithm for exact zero-skew trees via the concept of
a merging region
. For a
prescribed topology
, BST/DME constructs a bounded-skew tree (BST) in two phases: (i) a bottom-up phase to construct a binary tree of merging regions which represent the loci of possible embedding points of the internal nodes, and (ii) a top-down phase to determine the exact locations of the internal nodes. We present two approaches to construct the merging regions: (i) the
Boundary Merging and Embedding
(BME) method which utilizes merging points that are restricted to the
boundaries
of merging regions, and (ii) the
Interior Merging and Embedding
(IME) algorithm which employs a sampling strategy and a dynamic programming-based selection technique to consider merging points that are
interior
to, as well as on the boundary of, the merging regions. When the topology is not prescribed, we propose a new
Greedy
-BST/DME algorithm which combines the merging region computation with topology generation. The Greedy-BST/DME algorithm very closely matches the best known heuristics for the zero-skew case and for the unbounded-skew case (i.e., the Steiner minimal tree problem). Experimental results show that our BST algorithms can produce a set of routing solutions with smooth skew and wire length tradeoffs.
Efficient algorithms for geometric optimization
Authors: Agarwal Pankaj K. , Sharir Micha
Published: July 2002

We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric searching, geometric alternatives to parametric searching, prune-and-search techniques for linear programming and related problems, and LP-type problems and their efficient solution. We then describe a wide range of applications of these and other techniques to numerous problems in geometric optimization, including facility location, proximity problems, statistical estimators and metrology, placement and intersection of polygons and polyhedra, and ray shooting and other query-type problems.
A survey of structured and object-oriented software specification methods and techniques
Authors: Wieringa Roel
Published: July 2002

This article surveys techniques used in structured and object-oriented software specification methods. The techniques are classified as techniques for the specification of external interaction and internal decomposition. The external specification techniques are further subdivided into techniques for the specification of functions, behavior, and communication. After surveying the techniques, we summarize the way they are used in structured and object-oriented methods and indicate ways in which they can be combined. This article ends with a plea for simplicity in diagram techniques and for the use of formal semantics to define these techniques. The appendices show how the reviewed techniques are used in 6 structured and 19 object-oriented specification methods.
Parallel algorithms for data compression
Authors: Gonzalez Smith M. E. , Storer J. A.
Published: July 2002

Parallel algorithms for data compression by textual substitution that are suitable for VLSI implementation are studied. Both “static” and “dynamic” dictionary schemes are considered.
Performance estimation of embedded software with instruction cache modeling
Authors: Li Yau-Tsun Steven , Malik Sharad , Wolfe Andrew
Published: July 2002

Embedded systems generally interact in some way with the outside
world. This may involve measuring sensors and controlling actuators, communicating with other systems, or interacting with users. These functions impose real-time constraints on system design. Verification of these specifications requires computing an upper bound on the worst-case execution time (WCET) of a hardware/software system. Furthermore, it is critical to derive a tight upper bound on WCET in order to make efficient use of system resources.

The problem of bounding WCET is particularly difficult on modern processors. These processors use cache-based memory systems that vary memory access time based on the dynamic memory access pattern of the program. This must be accurately modeled in order to tightly bound WCET. Several analysis methods have been proposed to bound WCET on processors with instruction caches. Existing approaches either search all possible program paths, an intractable problem, or they use highly pessimistic assumptions to limit the search space. In this paper we present a more effective method for modeling instruction cache activity and computing a tight bound on WCET. The method uses an integer linear programming formulation and does not require explicit enumeration of program paths. The method is implemented in the program cinderella and we present some experimental results of this implementation.
Efficient algorithms for inverting evolution
Authors: Farach Martin , Kannan Sampath
Published: July 2002

Evolution can be mathematically modelled by a stochastic process that operates on the DNA of species. Such models are based on the established theory that the DNA sequences, or genomes, of all extant species have been derived from the genome of the common ancestor of all species by a process of random mutation and natural selection.

A stochastic model of evolution can be used to construct phylogenies, or evolutionary trees, for a set of species. Maximum Likelihood Estimation (MLE) methods seek the evolutionary tree which is most likely to have produced the DNA under consideration. While these methods are intellectually satisfying, they have not been widely accepted because of their computational intractability.

In this paper, we address the intractability of MLE methods as follows: We introduce a metric on stochastic process models of evolution. We show that this metric is meaningful by proving that in order for any algorithm to distinguish between two stochastic models that are close according to this metric, it needs to be given many observations. We complement this result with a simple and efficient algorithm for inverting the stochastic process of evolution, that is, for building a tree from observations on two-state characters. (We will use the same techniques in a subsequent paper to solve the problem for multistate characters, and hence for building a tree from DNA sequence data.) The tree we build is provably close, in our metric, to the tree generating the data and gets closer as more observations become available.

Though there have been many heuristics suggested for the problem of finding good approximations to the most likely tree, our algorithm is the first one with a guaranteed convergence rate, and further, this rate is within a polynomial of the lower-bound rate we establish. Ours is also the first polynomial-time algorithm that is
proven
to converge at all to the correct tree.