CiteSeerX Scientific Literature Digital Library and Search Engine
(2.272.612 recursos)
CiteSeerX is a scientific literature digital library and search engine that focuses primarily on the literature in computer and information science. CiteSeerx aims to improve the dissemination of scientific literature and to provide improvements in functionality, usability, availability, cost, comprehensiveness, efficiency, and timeliness in the access of scientific and scholarly knowledge

Mostrando recursos 1 - 20 de 2.207.002

1.
Communication-Optimal Parallel Minimum Spanning Tree Algorithms - Micah Adler; Wolfgang Dittrich; Ben Juurlink; Miroslaw Kutylowski; Ingo Rieping
Lower and upper bounds for finding a minimum spanning tree (MST) in a weighted undirected graph on the BSP model are presented. We provide the first non-trivial lower bounds on the communication volume required to solve the MST problem. Let p denote the number of processors, n the number of nodes of the input graph, and m the number of edges of the input graph. We show that in the worst case, a total of \Omega\Gamma \Delta min(m; pn)) bits need to be communicated in order to solve the MST problem, where is the number of bits required to represent...

2.
Unified View of Completeness and Compactness for Theory-Based Variants of Resolution - Andrea Formisano
Completeness plays a extremely crucial role in automated theorem proving and it represents an essential desiderata for any calculus one could introduce. As far as a particular calculus is concerned, its Completeness Theorem connects the syntactic aspect of the reasoning activity to its semantic counterpart. For this reason completeness turns out to be strictly related to compactness, since finiteness is an obvious prerequisite for the effectiveness of the calculus. This work emphasizes two, somehow orthogonal, aspects of completeness for first-order calculi. From the syntactic point of view, we single out minimal, albeit sufficient, requirements on the underlying language to ensure...

3.
Model-Checking Real-Time Control Programs - Verifying LEGO MINDSTORMS Systems Using UPPAAL - Torsten K. Iversen; Kare J. Kristoffersen; Kim G. Larsen; Morten Laursen; Rune G. Madsen; Steffen K. Mortensen; Paul Pettersson; Chris B. Thomasen
In this paper, we present a method for automatic verification of real-time control programs running on LEGO RCX bricks using the verification tool UPPAAL. The control programs, consisting of a number of tasks running concurrently, are automatically translated into the timed automata model of UPPAAL. The fixed scheduling algorithm used by the LEGO RCX processor is modeled in UP- PAAL, and supply of similar (sufficient) timed automata models for the environment allows analysis of the overall real-time system using the tools of UPPAAL. To illustrate our techniques we have constructed, modeled and verified a machine for sorting LEGO bricks by...

4.
Inclusive Charm Production at HERA and the Charm Content of the Photon - Manuel Drees University; Manuel Drees; Rohini M. Godbole
We calculate the contribution to inclusive high tranverse momentum (p T ) charm production at HERA from the excitation of charm in the photon. At large values of p T the results of such a calculation, in the structure function language, will be more reliable as it sums the large logs, log(p 2 T =m 2 c ), as opposed to calculating the contribution of the 2 ! 3 subprocess in fixed order of perturbation theory. We find that this contribution is large and comparable to the contribution from flg fusion production of charm. Suitable cuts on the rapidity of...

5.
Event-Based Feedback Control for Deadlock Avoidance in Flexible Production Systems - Maria Pia Fanti; Bruno Maione; Saverio Mascolo; Biagio Turchiano
Modern production facilities (i.e., flexible manufacturing systems) exhibit a high degree of resource sharing, a situation in which deadlocks (circular waits) can arise. Using digraph theoretic concepts we derive necessary and sufficient conditions for a deadlock occurrence and rigorously characterize highly undesirable situations (second level deadlocks), which inevitably evolve to circular waits in the next future. We assume that the system dynamics is described by a discrete event dynamical model, whose state provides the information on the current interactions job-resources. This theoretic material allows us to introduce some control laws (named restriction policies) which use the state knowledge to avoid...

6.
SPH test simulations on a portable parallel environment - T. Bubeck; M. Hipp; S. Hüttemann; S. Kunze; M. Ritt; W. Rosenstiel; H. Ruder; R. Speith
. In this paper we report on the results of a joint eort of astrophysicists and computer scientists to develop and implement a parallel program that enables us to solve large systems of hydrodynamic equations and covers a wide range of applications in astrophysics. We introduce the Distributed Threads System (DTS) as an environment for the development of portable parallel applications. The numerical method Smoothed Particle Hydrodynamics (SPH) is used to simulate the viscous spreading of an accretion disk around a massive compact object as an astrophysical test problem. The SPH code was parallelized using DTS and successfully ported to...

7.
Studying Animals through Artificial Evolution: the Cricket Case - Rens Kortmann; John Hallam
. In this paper we introduce the notion of historical evidence { the ability to replicate biologically realistic evolutionary scenarios { for hypothesised mechanisms for control of sensorimotor behaviour. We apply the idea to the phonotaxis mechanism proposed by Webb and her collaborators to account for the abilities of Gryllus bimaculatus. To do this, we tested whether the proposed control mechanism, when implemented in a robot model of the animal, could account for evolutionary adaptations observed in the natural system. We describe and discuss the experiment and its results, but start by explaining the methodology used, which is an extension...

8.
Generalising Techniques for Type Debugging - Bruce J. Mcadam
Several authors have presented algorithms to help programmers understand the types in their programs and to help debug type errors. Each of these has supplied a different form of information to the programmer --- the types of unbound identifiers and suggestions of where in programs mistakes may lie are examples of such information. This paper presents a means of representing type information as graphs from which we can extract a range of different facts about the types in programs. The graph representation is presented, and we see how it can be used to simulate some of the schemes proposed by...

9.
A Low-Complexity Modeling Approach for Embedded Coding of Wavelet Coefficients - Erik Ordentlich; Marcelo Weinberger; Gadiel Seroussi
We present a new low-complexity method for modeling and coding the bitplanes of a wavelet-transformed image in a fully embedded fashion. The scheme uses a simple ordering model for embedding, based on the principle that coefficient bits that are likely to reduce the distortion the most should be described first in the encoded bitstream. The ordering model is tied to a conditioning model in a way that deinterleaves the conditioned subsequences of coefficient bits, making them amenable to coding with a very simple, adaptive elementary Golomb code. The proposed scheme, without relying on zerotrees or arithmetic coding, attains PSNR vs....

10.
Wavelets in Statistics: Beyond the Standard Assumptions - Bernard Silverman
this paper, attention has been focused on methods that treat coe#cients at least as if they were independent. However, it is intuitively clear that if one coe#cient in the wavelet array is nonzero, then it is more likely #in some appropriate sense# that neighbouring coe#cients will be also. One way of incorporating this notion is by some form of block thresholding, where coe#cients are considered in neighbouring blocks; see for example Hall et al. #1998# and Cai & Silverman #1998#. An obvious question for future consideration is integrate the ideas of block thresholding and related methods within the range of...

11.
The CERFACS experience - M.J. Daydé; I.S. Duff
We consider various aspects of the European Centre, CERFACS, located in Toulouse, SW France. We discuss its history and structure which we believe to be unique among European or indeed world scientific centres. We then describe some of the current research activities of the Parallel Algorithm Group at CERFACS. These include work on computational kernels for linear algebra, the solution of sparse systems by both direct and iterative methods, and the porting of industrial codes to parallel computers. Keywords: CERFACS, parallel algorithms, numerical linear algebra, BLAS kernels, sparse matrices, direct methods, iterative methods, industrial codes, porting. AMS(MOS) subject classifications: 65F05,...

12.
and Eberhard - Schmidt Institut Fr; Hans-joachim Schmid; Eberhard Schmidt
The paper is dealing with the presentations of collecting efficiencies of electrostatic precipitators. Whereas the total separation efficiency and effective migration rates respectively bear some problems in interpretation and discussion an observation of the flux of locally precipitated dust should lead to more clarity and an improved insight of precipitation because it is only based on physical terms. The paper presents model calculations accounting for the size-dependent local particle transport. The local mass flux was calculated for varying median particle size and width of the particle size distribution. One interesting result is the influence of the classification along the duct,...

13.
Belief Functions and Default Reasoning - S. Benferhat; A. Saffiotti; P. Smets
. We present a new approach to dealing with default information based on the theory of belief functions. Our semantic structures, inspired by Adams' e-semantics, are epsilon-belief assignments, where values committed to focal elements are either close to 0 or close to 1. We define two systems based on these structures, and relate them to other nonmonotonic systems presented in the literature. We show that our second system correctly addresses the well-known problems of specificity, irrelevance, blocking of inheritance, ambiguity, and redundancy. 1. Introduction Default reasoning is the process of drawing conclusions from i) a set of general rules which...

14.
Parallel Techniques For Efficient Searching Over Very Large Text Collections - Mamalis Spirakis Tampakas; B. Mamalis; P. Spirakis; B. Tampakas
This paper 1 mainly discusses the efficiency of PFIRE system, a parallel VSM-based text retrieval system running on the GCel3/512 Parsytec machine, as well as the effectiveness of the corresponding pre-existing serial FIRE system. Concerning PFIRE, the use of suitable data sharing and load balancing techniques in combination with specific pipelining techniques and with the capability of building binary and fat-tree virtual topologies over the 2-D mesh physical interconnection network of the parallel machine, leads to very fast interactive searching over the large scale TREC collections. Analytical and experimental evidence is presented to demonstrate the efficiency of our techniques. The...

15.
Metrics and Techniques for Automatic Partitioning and Assignment of Object-based Concurrent Programs - Lonnie R. Welch; Binoy Ravindran; Jorge Henriques; Dieter K. Hammer
The software crisis is defined as the inability to meet the demands for new software systems, due to the slow rate at which systems can be developed. To address the crisis, object-based design techniques and domain models have been developed. Furthermore, languages such as Modula-2, Ada, Smalltalk and C++ have been developed to enable the software realization of object-based designs. However, object-based design and implementation techniques do not address an additional problem that plagues systems engineers --- the effective utilization of distributed and parallel hardware platforms. This problem is partly addressed by program partitioning languages that allow an engineer to...

16.
Visualizing Class Structure of Multidimensional Data - Inderjit S. Dhillon; Dharmendra S. Modha; W. Scott Spangler
We consider the problem of visualizing multidimensional data that has been categorized into classes. Our goal in visualizing is to quickly absorb inter- and intra-class relationships. Towards this end, we introduce class-preserving projections of the multidimensional data onto twodimensional planes which can then be displayed on a computer screen. These class-preserving projections maintain the high-dimensional class structure, and are closely related to Fisher's linear discriminants. By displaying sequences of such two-dimensional projections and by moving continuously from one projection to the next, we can create illusions of smooth motion through a multidimensional display. Such sequences are termed class tours. We...

17.
On Finding Optimal Discretizations for Two Attributes - Bogdan S. Chlebus; Sinh Hoa Nguyen; Instytut Informatyki; Uniwersytet Warszawski
. We show that finding optimal discretization of instances of decision tables with two real value attributes and binary decisions is computationally hard. This is done by abstracting the problem in such a way that it regards partitioning points in the plane into regions, subject to certain minimality restrictions, and proving it to be NP-hard. We also propose a new method to find optimal discretizations. 1 Introduction Discretization of attributes with real values is an important problem in knowledge discovery and data mining. It is an indispensable tool in data analysis and extraction of decision rules from decision tables. A...

18.
The CRISIS Wide Area Security Architecture - Eshwar Belani; Amin Vahdat; Thomas Anderson; Michael Dahlin
This paper presents the design and implementation of a new authentication and access control system, called CRISIS. A goal of CRISIS is to explore the systematic application of a number of design principles to building highly secure systems, including: redundancy to eliminate single points of attack, caching to improve performance and availability over slow and unreliable wide area networks, fine-grained capabilities and roles to enable lightweight control of privilege, and complete local logging of all evidence used to make each access control decision. Measurements of a prototype CRISIS-enabled wide area file system show that in the common case CRISIS adds...

19.
The Level of Nonmultiplicativity of Graphs - Claude Tardif; Xuding Zhu
We introduce a parameter called the level of nonmultiplicativity of a graph, which is related to Hedetniemi's conjecture. We show that this parameter is equal to the number of factors in a factorization of the graph into a product of multiplicative graphs. Apart from the known multiplicative graphs, no graph is known to have a nite level of nonmultiplicativity. We show that the countably innite complete graph K @0 has an innite level of nonmultiplicativity and that there exist Kneser graphs with arbitrarily high levels of nonmultiplicativity. 1 Introduction Given graphs G and H, the categorical product GH of G...

20.
The new Intermediate Polar RX J1238--38: a system below the period gap ? - David Buckley Mark; Gavin Ramsay; Dayal T. Wickramasinghe
We present optical observations of the recently discovered ROSAT source, RX J1238-- 38, which is a new member of the Intermediate Polar class of asynchronous magnetic cataclysmic variables. Optical photometry reveals two coherent periodicities at 1860 s and 2147 s respectively, with similar amplitudes of 8%. Infrared (J-band) intensity variations are detected only at the 1860 s period, at an amplitude of 15%. The initial hypothesis, that these two periods were the spin and synodic (i.e. beat) period respectively, appears not to be supported by the spectroscopic data. The emission lines vary on the longer photometric period, and radial velocity...