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 121 - 140 de 9,277
121.
Limits of Rush Hour Logic Complexity - Tromp, John; Cilibrasi, Rudi
Rush Hour Logic was introduced in [Flake&Baum99] as a model of computation
inspired by the ``Rush Hour'' toy puzzle, in which cars can move horizontally
or vertically within a parking lot. The authors show how the model supports
polynomial space computation, using certain car configurations as building
blocks to construct boolean circuits for a cpu and memory. They consider the
use of cars of length 3 crucial to their construction, and conjecture that cars
of size 2 only, which we'll call `Size 2 Rush Hour', do not support polynomial
space computation. We settle this conjecture by showing that the required
building blocks are constructible in Size 2 Rush...
122.
Bidimensionality, Map Graphs, and Grid Minors - Demaine, Erik D.; Hajiaghayi, MohammadTaghi
In this paper we extend the theory of bidimensionality to two families of
graphs that do not exclude fixed minors: map graphs and power graphs. In both
cases we prove a polynomial relation between the treewidth of a graph in the
family and the size of the largest grid minor. These bounds improve the running
times of a broad class of fixed-parameter algorithms. Our novel technique of
using approximate max-min relations between treewidth and size of grid minors
is powerful, and we show how it can also be used, e.g., to prove a linear
relation between the treewidth of a bounded-genus graph and the treewidth of
its dual.
123.
Graphs and colorings for answer set programming - Konczak, Kathrin; Linke, Thomas; Schaub, Torsten
We investigate the usage of rule dependency graphs and their colorings for
characterizing and computing answer sets of logic programs. This approach
provides us with insights into the interplay between rules when inducing answer
sets. We start with different characterizations of answer sets in terms of
totally colored dependency graphs that differ in graph-theoretical aspects. We
then develop a series of operational characterizations of answer sets in terms
of operators on partial colorings. In analogy to the notion of a derivation in
proof theory, our operational characterizations are expressed as
(non-deterministically formed) sequences of colorings, turning an uncolored
graph into a totally colored one. In this way, we obtain...
124.
Towards a Systematic Account of Different Semantics for Logic Programs - Hitzler, Pascal
In [Hitzler and Wendt 2002, 2005], a new methodology has been proposed which
allows to derive uniform characterizations of different declarative semantics
for logic programs with negation. One result from this work is that the
well-founded semantics can formally be understood as a stratified version of
the Fitting (or Kripke-Kleene) semantics. The constructions leading to this
result, however, show a certain asymmetry which is not readily understood. We
will study this situation here with the result that we will obtain a coherent
picture of relations between different semantics for normal logic programs.
125.
An Audit Logic for Accountability - Cederquist, J. G.; Corin, R.; Dekker, M. A. C.; Etalle, S.; Hartog, J. I. den
We describe and implement a policy language. In our system, agents can
distribute data along with usage policies in a decentralized architecture. Our
language supports the specification of conditions and obligations, and also the
possibility to refine policies. In our framework, the compliance with usage
policies is not actively enforced. However, agents are accountable for their
actions, and may be audited by an authority requiring justifications.
126.
Divergence-free Wavelets for Navier-Stokes - Deriaz, Erwan; Perrier, Valérie
In this paper, we investigate the use of compactly supported divergence-free
wavelets for the representation of the Navier-Stokes solution. After reminding
the theoretical construction of divergence-free wavelet vectors, we present in
detail the bases and corresponding fast algorithms for 2D and 3D incompressible
flows. In order to compute the nonlinear term, we propose a new method which
provides in practice with the Hodge decomposition of any flow: this
decomposition enables us to separate the incompressible part of the flow from
its orthogonal complement, which corresponds to the gradient component of the
flow. Finally we show numerical tests to validate our approach.
127.
Online Permutation Routing in Partitioned Optical Passive Star Networks - Mei, Alessandro; Rizzi, Romeo
This paper establishes the state of the art in both deterministic and
randomized online permutation routing in the POPS network. Indeed, we show that
any permutation can be routed online on a POPS network either with
$O(\frac{d}{g}\log g)$ deterministic slots, or, with high probability, with
$5c\lceil d/g\rceil+o(d/g)+O(\log\log g)$ randomized slots, where constant
$c=\exp (1+e^{-1})\approx 3.927$. When $d=\Theta(g)$, that we claim to be the
"interesting" case, the randomized algorithm is exponentially faster than any
other algorithm in the literature, both deterministic and randomized ones. This
is true in practice as well. Indeed, experiments show that it outperforms its
rivals even starting from as small a network as a POPS(2,2), and...
128.
Gradient Vector Flow Models for Boundary Extraction in 2D Images - Giraldi, Gilson A.; Marturelli, Leandro S.; Rodrigues, Paulo S.
The Gradient Vector Flow (GVF) is a vector diffusion approach based on
Partial Differential Equations (PDEs). This method has been applied together
with snake models for boundary extraction medical images segmentation. The key
idea is to use a diffusion-reaction PDE to generate a new external force field
that makes snake models less sensitivity to initialization as well as improves
the snake's ability to move into boundary concavities. In this paper, we
firstly review basic results about convergence and numerical analysis of usual
GVF schemes. We point out that GVF presents numerical problems due to
discontinuities image intensity. This point is considered from a practical
viewpoint from which the GVF...
129.
Duality Bounds on the Cut-Off Rate with Applications to Ricean Fading - Lapidoth, Amos; Miliou, Natalia
We propose a technique to derive upper bounds on Gallager's cost-constrained
random coding exponent function. Applying this technique to the non-coherent
peak-power or average-power limited discrete time memoryless Ricean fading
channel, we obtain the high signal-to-noise ratio (SNR) expansion of this
channel's cut-off rate. At high SNR the gap between channel capacity and the
cut-off rate approaches a finite limit. This limit is approximately 0.26 nats
per channel-use for zero specular component (Rayleigh) fading and approaches
0.39 nats per channel-use for very large specular components.
We also compute the asymptotic cut-off rate of a Rayleigh fading channel when
the receiver has access to some partial side information concerning...
130.
Earlier Web Usage Statistics as Predictors of Later Citation Impact - Brody, Tim; Harnad, Stevan
The use of citation counts to assess the impact of research articles is well
established. However, the citation impact of an article can only be measured
several years after it has been published. As research articles are
increasingly accessed through the Web, the number of times an article is
downloaded can be instantly recorded and counted. One would expect the number
of times an article is read to be related both to the number of times it is
cited and to how old the article is. This paper analyses how short-term Web
usage impact predicts medium-term citation impact. The physics e-print archive
(arXiv.org) is used to test this.
131.
Theory and Practice of Transactional Method Caching - Pfeifer, Daniel; Lockemann, Peter C.
Nowadays, tiered architectures are widely accepted for constructing large
scale information systems. In this context application servers often form the
bottleneck for a system's efficiency. An application server exposes an object
oriented interface consisting of set of methods which are accessed by
potentially remote clients. The idea of method caching is to store results of
read-only method invocations with respect to the application server's interface
on the client side. If the client invokes the same method with the same
arguments again, the corresponding result can be taken from the cache without
contacting the server. It has been shown that this approach can considerably
improve a real world system's efficiency....
132.
Authentication with Distortion Criteria - Martinian, Emin; Wornell, Gregory W.; Chen, Brian
In a variety of applications, there is a need to authenticate content that
has experienced legitimate editing in addition to potential tampering attacks.
We develop one formulation of this problem based on a strict notion of
security, and characterize and interpret the associated information-theoretic
performance limits. The results can be viewed as a natural generalization of
classical approaches to traditional authentication. Additional insights into
the structure of such systems and their behavior are obtained by further
specializing the results to Bernoulli and Gaussian cases. The associated
systems are shown to be substantially better in terms of performance and/or
security than commonly advocated approaches based on data hiding and digital
watermarking....
133.
Comment on "Some non-conventional ideas about algorithmic complexity" - Poulin, David; Touchette, Hugo
We comment on a recent paper by D'Abramo [Chaos, Solitons & Fractals, 25
(2005) 29], focusing on the author's statement that an algorithm can produce a
list of strings containing at least one string whose algorithmic complexity is
greater than that of the entire list. We show that this statement, although
perplexing, is not as paradoxical as it seems when the definition of
algorithmic complexity is applied correctly.
134.
The egalitarian sharing rule in provision of public projects - Bogomolnaia, Anna; Breton, Michel Le; Savvateev, Alexei; Weber, Shlomo
In this note we consider a society that partitions itself into disjoint
jurisdictions, each choosing a location of its public project and a taxation
scheme to finance it. The set of public project is multi-dimensional, and their
costs could vary from jurisdiction to jurisdiction. We impose two principles,
egalitarianism, that requires the equalization of the total cost for all agents
in the same jurisdiction, and efficiency, that implies the minimization of the
aggregate total cost within jurisdiction. We show that these two principles
always yield a core-stable partition but a Nash stable partition may fail to
exist.
135.
Mining Top-k Approximate Frequent Patterns - He, Zengyou
Frequent pattern (itemset) mining in transactional databases is one of the
most well-studied problems in data mining. One obstacle that limits the
practical usage of frequent pattern mining is the extremely large number of
patterns generated. Such a large size of the output collection makes it
difficult for users to understand and use in practice. Even restricting the
output to the border of the frequent itemset collection does not help much in
alleviating the problem. In this paper we address the issue of overwhelmingly
large output size by introducing and studying the following problem: mining
top-k approximate frequent patterns. The union of the power sets of these k
sets...
136.
On a Kronecker products sum distance bounds - Grigoryants, Armen
A binary linear error correcting codes represented by two code families
Kronecker products sum are considered. The dimension and distance of new code
is investigated. Upper and lower bounds of distance are obtained. Some examples
are given. It is shown that some classic constructions are the private cases of
considered one. The subclass of codes with equal lower and upper distance
bounds is allocated.
138.
Zeta-Dimension - Doty, David; Gu, Xiaoyang; Lutz, Jack H.; Mayordomo, Elvira; Moser, Philippe
The zeta-dimension of a set A of positive integers is the infimum s such that
the sum of the reciprocals of the s-th powers of the elements of A is finite.
Zeta-dimension serves as a fractal dimension on the positive integers that
extends naturally usefully to discrete lattices such as the set of all integer
lattice points in d-dimensional space.
This paper reviews the origins of zeta-dimension (which date to the
eighteenth and nineteenth centuries) and develops its basic theory, with
particular attention to its relationship with algorithmic information theory.
New results presented include extended connections between zeta-dimension and
classical fractal dimensions, a gale characterization of zeta-dimension,...
139.
A hybrid MLP-PNN architecture for fast image superresolution - Miravet, Carlos; Rodriguez, Francisco B.
Image superresolution methods process an input image sequence of a scene to
obtain a still image with increased resolution. Classical approaches to this
problem involve complex iterative minimization procedures, typically with high
computational costs. In this paper is proposed a novel algorithm for
super-resolution that enables a substantial decrease in computer load. First, a
probabilistic neural network architecture is used to perform a scattered-point
interpolation of the image sequence data. The network kernel function is
optimally determined for this problem by a multi-layer perceptron trained on
synthetic data. Network parameters dependence on sequence noise level is
quantitatively analyzed. This super-sampled image is spatially filtered to
correct finite pixel size effects,...
140.
Analytic Definition of Curves and Surfaces by Parabolic Blending - Overhauser, A. W.
A procedure for interpolating between specified points of a curve or surface
is described. The method guarantees slope continuity at all junctions. A
surface panel divided into p x q contiguous patches is completely specified by
the coordinates of (p+1) x (q+1) points. Each individual patch, however,
depends parametrically on the coordinates of 16 points, allowing shape
flexibility and global conformity.
121.
