arXiv
(422,153 recursos)
This is one of the most extensive subject based repositories in the world in the field of physics, mathematics, astronomy, computer sciences and quantitative biology. This is the principal site with almost 20 mirror versions around the globe. The site is supported by an extensive collection of information and background documentation. An RSS feed is available for anyone interested in keeping up-to-date with newly added materials.
Mostrando recursos 141 - 160 de 9,277
141.
Optimality in Goal-Dependent Analysis of Sharing - Amato, Gianluca; Scozzari, Francesca
In the context of abstract interpretation based static analysis, we face the
problem of correctness and optimality for logic program analysis. We propose a
new framework equipped with a denotational, goal-dependent semantics which
refines many goal-driven frameworks appeared in the literature. The key point
is the introduction of two specialized concrete operators for forward and
backward unification. We prove that our goal-dependent semantics is correct
w.r.t. computed answers and we provide the best correct approximations of all
the operators involved in the semantics for set-sharing analysis. We show that
the precision of the overall analysis is strictly improved and that, in some
cases, we gain precision w.r.t. more complex...
142.
Exact and Approximation Algorithms for DNA Tag Set Design - Mandoiu, Ion I.; Trinca, Dragos
In this paper we propose new solution methods for designing tag sets for use
in universal DNA arrays. First, we give integer linear programming formulations
for two previous formalizations of the tag set design problem, and show that
these formulations can be solved to optimality for instance sizes of practical
interest by using general purpose optimization packages. Second, we note the
benefits of periodic tags, and establish an interesting connection between the
tag design problem and the problem of packing the maximum number of
vertex-disjoint directed cycles in a given graph. We show that combining a
simple greedy cycle packing algorithm with a previously proposed alphabetic
tree search strategy...
143.
Randomly Spread CDMA: Asymptotics via Statistical Physics - Guo, Dongning; Verdu, Sergio
This paper studies randomly spread code-division multiple access (CDMA) and
multiuser detection in the large-system limit using the replica method
developed in statistical physics. Arbitrary input distributions and flat fading
are considered. A generic multiuser detector in the form of the posterior mean
estimator is applied before single-user decoding. The generic detector can be
particularized to the matched filter, decorrelator, linear MMSE detector, the
jointly or the individually optimal detector, and others. It is found that the
detection output for each user, although in general asymptotically non-Gaussian
conditioned on the transmitted symbol, converges as the number of users go to
infinity to a deterministic function of a "hidden" Gaussian...
144.
A Survey of Reverse Engineering and Program Comprehension - Nelson, Michael L.
Reverse engineering has been a standard practice in the hardware community
for some time. It has only been within the last ten years that reverse
engineering, or "program comprehension", has grown into the current
sub-discipline of software engineering. Traditional software engineering is
primarily focused on the development and design of new software. However, most
programmers work on software that other people have designed and developed. Up
to 50% of a software maintainers time can be spent determining the intent of
source code. The growing demand to reevaluate and reimplement legacy software
systems, brought on by the proliferation of clientserver and World Wide Web
technologies, has underscored the need for...
145.
Geometric Models of Rolling-Shutter Cameras - Meingast, Marci; Geyer, Christopher; Sastry, Shankar
Cameras with rolling shutters are becoming more common as low-power, low-cost
CMOS sensors are being used more frequently in cameras. The rolling shutter
means that not all scanlines are exposed over the same time interval. The
effects of a rolling shutter are noticeable when either the camera or objects
in the scene are moving and can lead to systematic biases in projection
estimation. We develop a general projection equation for a rolling shutter
camera and show how it is affected by different types of camera motion. In the
case of fronto-parallel motion, we show how that camera can be modeled as an
X-slit camera. We also develop approximate...
146.
Space-time databases modeling global semantic networks - Prikhod'ko, A. A.; Prikhod'ko, N. A.
This paper represents an approach to creating global knowledge systems, using
new philosophy and infrastructure of global distributed semantic network (frame
knowledge representation system) based on the space-time database construction.
The main idea of the space-time database environment introduced in the paper is
to bind a document (an information frame, a knowledge) to a special kind of
entity, that we call permanent entity, -- an object without history and
evolution, described by a "point" in the generalized, informational space-time
(not an evolving object in the real space having history). For documents
(information) it means that document content is unchangeable, and documents are
absolutely persistent. This approach leads to new...
147.
An Optimization Model for Outlier Detection in Categorical Data - He, Zengyou; Xu, Xiaofei; Deng, Shengchun
The task of outlier detection is to find small groups of data objects that
are exceptional when compared with rest large amount of data. Detection of such
outliers is important for many applications such as fraud detection and
customer migration. Most existing methods are designed for numeric data. They
will encounter problems with real-life applications that contain categorical
data. In this paper, we formally define the problem of outlier detection in
categorical data as an optimization problem from a global viewpoint. Moreover,
we present a local-search heuristic based algorithm for efficiently finding
feasible solutions. Experimental results on real datasets and large synthetic
datasets demonstrate the superiority of our model...
148.
Resource Bounded Unprovability of Computational Lower Bounds - Okamoto, Tatsuaki; Kashima, Ryo
This paper introduces new notions of asymptotic proofs,
PT(polynomial-time)-extensions, PTM(polynomial-time Turing
machine)-omega-consistency, etc. on formal theories of arithmetic including PA
(Peano Arithmetic). This paper shows that P not= NP (more generally, any
super-polynomial-time lower bound in PSPACE) is unprovable in a
PTM-omega-consistent theory T, where T is a consistent PT-extension of PA. This
result gives a unified view to the existing two major negative results on
proving P not= NP, Natural Proofs and relativizable proofs, through the two
manners of characterization of PTM-omega-consistency. We also show that the
PTM-omega-consistency of T cannot be proven in any PTM-omega-consistent theory
S, where S is a consistent PT-extension of T.
149.
Monotonic and Nonmonotonic Preference Revision - Chomicki, Jan; Song, Joyce
We study here preference revision, considering both the monotonic case where
the original preferences are preserved and the nonmonotonic case where the new
preferences may override the original ones. We use a relational framework in
which preferences are represented using binary relations (not necessarily
finite). We identify several classes of revisions that preserve order axioms,
for example the axioms of strict partial or weak orders. We consider
applications of our results to preference querying in relational databases.
150.
Probabilistic and Team PFIN-type Learning: General Properties - Ambainis, Andris
We consider the probability hierarchy for Popperian FINite learning and study
the general properties of this hierarchy. We prove that the probability
hierarchy is decidable, i.e. there exists an algorithm that receives p_1 and
p_2 and answers whether PFIN-type learning with the probability of success p_1
is equivalent to PFIN-type learning with the probability of success p_2.
To prove our result, we analyze the topological structure of the probability
hierarchy. We prove that it is well-ordered in descending ordering and
order-equivalent to ordinal epsilon_0. This shows that the structure of the
hierarchy is very complicated.
Using similar methods, we also prove that, for PFIN-type learning, team
learning and...
151.
On the Effect of Fading on Ad hoc Networking - Han, Seon-Yeong; Abu-Ghazaleh, Nael
Most MANET (Mobile Ad hoc NETwork) research assumes idealized propagation
models. Experimental results have shown significant divergence from simulation
results due to the effect of signal fading in realistic wireless communication
channels. In this paper, we characterize the impact of fading on protocol
performance. We first study the effect of fading on MAC performance and show
that its effect can be dominating. One of our important conclusions is that
eliminating RTS/CTS packets results in more effective operation under fading.
We also identify an unfairness problem that arises due to backoffs in the
presence of fading. Moreover, fading results in several subtle interactions
between the MAC and routing layers. We...
152.
Multiple Description Quantization via Gram-Schmidt Orthogonalization - Chen, Jun; Tian, Chao; Berger, Toby; Hemami, Sheila
The multiple description (MD) problem has received considerable attention as
a model of information transmission over unreliable channels. A general
framework for designing efficient multiple description quantization schemes is
proposed in this paper. We provide a systematic treatment of the El Gamal-Cover
(EGC) achievable MD rate-distortion region, and show that any point in the EGC
region can be achieved via a successive quantization scheme along with
quantization splitting. For the quadratic Gaussian case, the proposed scheme
has an intrinsic connection with the Gram-Schmidt orthogonalization, which
implies that the whole Gaussian MD rate-distortion region is achievable with a
sequential dithered lattice-based quantization scheme as the dimension of the
(optimal) lattice quantizers...
153.
Statistical analysis of quality measures for mobile ad hoc networks - Bostelmann, Henning
How can the quality of a mobile ad hoc network (MANET) be quantified? This
work aims at an answer based on the lower network layers, i.e. on connectivity
between the wireless nodes, using statistical methods. A number of different
quality measures are introduced and classified according to their scaling
behaviour. They are analysed in a statistical model of a 1-dimensional MANET
system (corresponding e.g. to cars on a road). Neglecting boundary effects, the
model turns out to be exactly solvable, so that explicit analytical results for
the quality levels can be obtained both at fixed system size and in the limit
of large systems. In particular, this improves...
154.
Fast Codes for Large Alphabets - Ryabko, Boris; Astola, Jaakko; Egiazarian, Karen
We address the problem of constructing a fast lossless code in the case when
the source alphabet is large. The main idea of the new scheme may be described
as follows. We group letters with small probabilities in subsets (acting as
super letters) and use time consuming coding for these subsets only, whereas
letters in the subsets have the same code length and therefore can be coded
fast. The described scheme can be applied to sources with known and unknown
statistics.
155.
Using Information Theory Approach to Randomness Testing - Ryabko, B. Ya.; Monarev, V. A.
We address the problem of detecting deviations of binary sequence from
randomness,which is very important for random number (RNG) and pseudorandom
number generators (PRNG). Namely, we consider a null hypothesis $H_0$ that a
given bit sequence is generated by Bernoulli source with equal probabilities of
0 and 1 and the alternative hypothesis $H_1$ that the sequence is generated by
a stationary and ergodic source which differs from the source under $H_0$. We
show that data compression methods can be used as a basis for such testing and
describe two new tests for randomness, which are based on ideas of universal
coding. Known statistical tests and suggested ones are...
156.
The Bandwidth Exchange Architecture - Turner, David Michael; Prevelakis, Vassilis; Keromytis, Angelos D.
New applications for the Internet such as video on demand, grid computing
etc. depend on the availability of high bandwidth connections with acceptable
Quality of Service (QoS). There appears to be, therefore, a requirement for a
market where bandwidth-related transactions can take place. For this market to
be effective, it must be efficient for both the provider (seller) and the user
(buyer) of the bandwidth. This implies that: (a) the buyer must have a wide
choice of providers that operate in a competitive environment, (b) the seller
must be assured that a QoS transaction will be paid by the customer, and (c)
the QoS transaction establishment must have...
157.
Correlation Clustering with a Fixed Number of Clusters - Giotis, Ioannis; Guruswami, Venkatesan
We continue the investigation of problems concerning correlation clustering
or clustering with qualitative information, which is a clustering formulation
that has been studied recently. The basic setup here is that we are given as
input a complete graph on n nodes (which correspond to nodes to be clustered)
whose edges are labeled + (for similar pairs of items) and - (for dissimilar
pairs of items). Thus we have only as input qualitative information on
similarity and no quantitative distance measure between items. The quality of a
clustering is measured in terms of its number of agreements, which is simply
the number of edges it correctly classifies, that is...
158.
Constraint-Based Qualitative Simulation - Apt, Krzysztof R.; Brand, Sebastian
We consider qualitative simulation involving a finite set of qualitative
relations in presence of complete knowledge about their interrelationship. We
show how it can be naturally captured by means of constraints expressed in
temporal logic and constraint satisfaction problems. The constraints relate at
each stage the 'past' of a simulation with its 'future'. The benefit of this
approach is that it readily leads to an implementation based on constraint
technology that can be used to generate simulations and to answer queries about
them.
160.
Linear Datalog and Bounded Path Duality of Relational Structures - Dalmau, Victor
In this paper we systematically investigate the connections between logics
with a finite number of variables, structures of bounded pathwidth, and linear
Datalog Programs. We prove that, in the context of Constraint Satisfaction
Problems, all these concepts correspond to different mathematical embodiments
of a unique robust notion that we call bounded path duality. We also study the
computational complexity implications of the notion of bounded path duality. We
show that every constraint satisfaction problem $\csp(\best)$ with bounded path
duality is solvable in NL and that this notion explains in a uniform way all
families of CSPs known to be in NL. Finally, we use the results developed in
the...
141.
