OpenRaiser/Intern-Atlas huggingface dataset:
An Efficient Approximation Algorithm for Point Pattern Matching Under Noise
Venue: arXiv cs.CV 2006
Year: 2006

Point pattern matching problems are of fundamental importance in various areas including computer vision and structural bioinformatics. In this paper, we study one of the more general problems, known as LCP (largest common point set problem): Let $\PP$ and $\QQ$ be two point sets in $\mathbb{R}^3$, and let $ε\geq 0$ be a tolerance parameter, the problem is to find a rigid motion $μ$ that maximizes the cardinality of subset $\II$ of $Q$, such that the Hausdorff distance $\distance(\PP,μ(\II)) \leq ε$. We denote the size of the optimal solution to the above problem by $\LCP(P,Q)$. The problem is called exact-LCP for $ε=0$, and \tolerant-LCP when $ε>0$ and the minimum interpoint distance is greater than $2ε$. A $β$-distance-approximation algorithm for tolerant-LCP finds a subset $I \subseteq \QQ$ such that $|I|\geq \LCP(P,Q)$ and $\distance(\PP,μ(\II)) \leq βε$ for some $β\ge 1$. This paper has three main contributions. (1) We introduce a new algorithm, called {\DA}, which gives the fastest known deterministic 4-distance-approximation algorithm for \tolerant-LCP. (2) For the exact-LCP, when the matched set is required to be large, we give a simple sampling strategy that improves the running times of all known deterministic algorithms, yielding the fastest known deterministic algorithm for this problem. (3) We use expander graphs to speed-up the \DA algorithm for \tolerant-LCP when the size of the matched set is required to be large, at the expense of approximation in the matched set size. Our algorithms also work when the transformation $μ$ is allowed to be scaling transformation.
The Geometry of Linear Higher-Order Recursion
Venue: arXiv cs.LO 2006
Year: 2006

Linearity and ramification constraints have been widely used to weaken higher-order (primitive) recursion in such a way that the class of representable functions equals the class of polytime functions. We show that fine-tuning these two constraints leads to different expressive strengths, some of them lying well beyond polynomial time. This is done by introducing a new semantics, called algebraic context semantics. The framework stems from Gonthier's original work and turns out to be a versatile and powerful tool for the quantitative analysis of normalization in presence of constants and higher-order recursion.
An End-to-End Probabilistic Network Calculus with Moment Generating Functions
Venue: arXiv cs.IT 2006
Year: 2006

Network calculus is a min-plus system theory for performance evaluation of queuing networks. Its elegance stems from intuitive convolution formulas for concatenation of deterministic servers. Recent research dispenses with the worst-case assumptions of network calculus to develop a probabilistic equivalent that benefits from statistical multiplexing. Significant achievements have been made, owing for example to the theory of effective bandwidths, however, the outstanding scalability set up by concatenation of deterministic servers has not been shown. This paper establishes a concise, probabilistic network calculus with moment generating functions. The presented work features closed-form, end-to-end, probabilistic performance bounds that achieve the objective of scaling linearly in the number of servers in series. The consistent application of moment generating functions put forth in this paper utilizes independence beyond the scope of current statistical multiplexing of flows. A relevant additional gain is demonstrated for tandem servers with independent cross-traffic.
Real Hypercomputation and Continuity
Venue: arXiv cs.LO 2006
Year: 2006

By the sometimes so-called 'Main Theorem' of Recursive Analysis, every computable real function is necessarily continuous. We wonder whether and which kinds of HYPERcomputation allow for the effective evaluation of also discontinuous f:R->R. More precisely the present work considers the following three super-Turing notions of real function computability: * relativized computation; specifically given oracle access to the Halting Problem 0' or its jump 0''; * encoding real input x and/or output y=f(x) in weaker ways also related to the Arithmetic Hierarchy; * non-deterministic computation. It turns out that any f:R->R computable in the first or second sense is still necessarily continuous whereas the third type of hypercomputation does provide the required power to evaluate for instance the discontinuous sign function.
Performance Analysis and Enhancement of Multiband OFDM for UWB Communications
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, we analyze the frequency-hopping orthogonal frequency-division multiplexing (OFDM) system known as Multiband OFDM for high-rate wireless personal area networks (WPANs) based on ultra-wideband (UWB) transmission. Besides considering the standard, we also propose and study system performance enhancements through the application of Turbo and Repeat-Accumulate (RA) codes, as well as OFDM bit-loading. Our methodology consists of (a) a study of the channel model developed under IEEE 802.15 for UWB from a frequency-domain perspective suited for OFDM transmission, (b) development and quantification of appropriate information-theoretic performance measures, (c) comparison of these measures with simulation results for the Multiband OFDM standard proposal as well as our proposed extensions, and (d) the consideration of the influence of practical, imperfect channel estimation on the performance. We find that the current Multiband OFDM standard sufficiently exploits the frequency selectivity of the UWB channel, and that the system performs in the vicinity of the channel cutoff rate. Turbo codes and a reduced-complexity clustered bit-loading algorithm improve the system power efficiency by over 6 dB at a data rate of 480 Mbps.
On the Expressiveness of the Ambient Logic
Venue: arXiv cs.LO 2006
Year: 2006

The Ambient Logic (AL) has been proposed for expressing properties of process mobility in the calculus of Mobile Ambients (MA), and as a basis for query languages on semistructured data. In this paper, we study the expressiveness of AL. We define formulas for capabilities and for communication in MA. We also derive some formulas that capture finitess of a term, name occurrences and persistence. We study extensions of the calculus involving more complex forms of communications, and we define characteristic formulas for the equivalence induced by the logic on a subcalculus of MA. This subcalculus is defined by imposing an image-finiteness condition on the reducts of a MA process.
A Market Test for the Positivity of Arrow-Debreu Prices
Venue: arXiv cs.CE 2006
Year: 2006

We derive tractable necessary and sufficient conditions for the absence of buy-and-hold arbitrage opportunities in a perfectly liquid, one period market. We formulate the positivity of Arrow-Debreu prices as a generalized moment problem to show that this no arbitrage condition is equivalent to the positive semidefiniteness of matrices formed by the market price of tradeable securities and their products. We apply this result to a market with multiple assets and basket call options.
Precoding for 2x2 Doubly-Dispersive WSSUS Channels
Venue: arXiv cs.IT 2006
Year: 2006

Optimal link adaption to the scattering function of wide sense stationary uncorrelated scattering (WSSUS) mobile communication channels is still an unsolved problem despite its importance for next-generation system design. In multicarrier transmission such link adaption is performed by pulse shaping which in turn is equivalent to precoding with respect to the second order channel statistics. In the present framework a translation of the precoder optimization problem into an optimization problem over trace class operators is used. This problem which is also well-known in the context of quantum information theory is unsolved in general due to its non-convex nature. However in very low dimension the problem formulation reveals an additional analytic structure which again admits the solution to the optimal precoder and multiplexing scheme. Hence, in this contribution the analytic solution of the problem for the 2x2 doubly--dispersive WSSUS channel is presented.
Context Semantics, Linear Logic and Computational Complexity
Venue: arXiv cs.LO 2006
Year: 2006

We show that context semantics can be fruitfully applied to the quantitative analysis of proof normalization in linear logic. In particular, context semantics lets us define the weight of a proof-net as a measure of its inherent complexity: it is both an upper bound to normalization time (modulo a polynomial overhead, independently on the reduction strategy) and a lower bound to the number of steps to normal form (for certain reduction strategies). Weights are then exploited in proving strong soundness theorems for various subsystems of linear logic, namely elementary linear logic, soft linear logic and light linear logic.
Virtual Coordinate Backtracking for Void Traversal in Geographic Routing
Venue: arXiv cs.NI 2006
Year: 2006

Geographical routing protocols have several desirable features for use in ad hoc and sensor networks but are susceptible to voids and localization errors. Virtual coordinate systems are an alternative solution to geographically based routing protocols that works by overlaying a coordinate system on the sensors relative to well chosen reference points. VC is resilient to localization errors; however, we show that it is vulnerable to different forms of the void problem and have no viable complementary approach to overcome them. Specifically, we show that there are instances when packets reach nodes with no viable next hop nodes in the forwarding set. In addition, it is possible for nodes with the same coordinates to arise at different points in the network in the presence of voids. This paper identifies and analyzes these problems. It also compares several existing routing protocols based on Virtual Coordinate systems. Finally, it presents a new routing algorithm that uses backtracking to overcome voids to achieve high connectivity in the greedy phase, higher overall path quality and more resilience to localization errors. We show these properties using extensive simulation analysis.
Ramsey partitions and proximity data structures
Venue: arXiv cs.DS 2006
Year: 2006

This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman). We then proceed to construct optimal Ramsey partitions, and use them to show that for every e\in (0,1), any n-point metric space has a subset of size n^{1-e} which embeds into Hilbert space with distortion O(1/e). This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor, in addition to considerably simplifying its proof. We use our new Ramsey partitions to design the best known approximate distance oracles when the distortion is large, closing a gap left open by Thorup and Zwick. Namely, we show that for any $n$ point metric space X, and k>1, there exists an O(k)-approximate distance oracle whose storage requirement is O(n^{1+1/k}), and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking.
A linear-time algorithm for finding the longest segment which scores above a given threshold
Venue: arXiv cs.DS 2006
Year: 2006

This paper describes a linear-time algorithm that finds the longest stretch in a sequence of real numbers (``scores'') in which the sum exceeds an input parameter. The algorithm also solves the problem of finding the longest interval in which the average of the scores is above a fixed threshold. The problem originates from molecular sequence analysis: for instance, the algorithm can be employed to identify long GC-rich regions in DNA sequences. The algorithm can also be used to trim low-quality ends of shotgun sequences in a preprocessing step of whole-genome assembly.
A System of Interaction and Structure II: The Need for Deep Inference
Venue: arXiv cs.LO 2006
Year: 2006

This paper studies properties of the logic BV, which is an extension of multiplicative linear logic (MLL) with a self-dual non-commutative operator. BV is presented in the calculus of structures, a proof theoretic formalism that supports deep inference, in which inference rules can be applied anywhere inside logical expressions. The use of deep inference results in a simple logical system for MLL extended with the self-dual non-commutative operator, which has been to date not known to be expressible in sequent calculus. In this paper, deep inference is shown to be crucial for the logic BV, that is, any restriction on the ``depth'' of the inference rules of BV would result in a strictly less expressive logical system.
Integration of navigation and action selection functionalities in a computational model of cortico-basal ganglia-thalamo-cortical loops
Venue: arXiv cs.AI 2006
Year: 2006

This article describes a biomimetic control architecture affording an animat both action selection and navigation functionalities. It satisfies the survival constraint of an artificial metabolism and supports several complementary navigation strategies. It builds upon an action selection model based on the basal ganglia of the vertebrate brain, using two interconnected cortico-basal ganglia-thalamo-cortical loops: a ventral one concerned with appetitive actions and a dorsal one dedicated to consummatory actions. The performances of the resulting model are evaluated in simulation. The experiments assess the prolonged survival permitted by the use of high level navigation strategies and the complementarity of navigation strategies in dynamic environments. The correctness of the behavioral choices in situations of antagonistic or synergetic internal states are also tested. Finally, the modelling choices are discussed with regard to their biomimetic plausibility, while the experimental results are estimated in terms of animat adaptivity.
Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics
Venue: arXiv cs.DS 2006
Year: 2006

We study various SDP formulations for {\sc Vertex Cover} by adding different constraints to the standard formulation. We show that {\sc Vertex Cover} cannot be approximated better than $2-o(1)$ even when we add the so called pentagonal inequality constraints to the standard SDP formulation, en route answering an open question of Karakostas~\cite{Karakostas}. We further show the surprising fact that by strengthening the SDP with the (intractable) requirement that the metric interpretation of the solution is an $\ell_1$ metric, we get an exact relaxation (integrality gap is 1), and on the other hand if the solution is arbitrarily close to being $\ell_1$ embeddable, the integrality gap may be as big as $2-o(1)$. Finally, inspired by the above findings, we use ideas from the integrality gap construction of Charikar \cite{Char02} to provide a family of simple examples for negative type metrics that cannot be embedded into $\ell_1$ with distortion better than $8/7-\eps$. To this end we prove a new isoperimetric inequality for the hypercube.
Integration of streaming services and TCP data transmission in the Internet
Venue: arXiv cs.NI 2006
Year: 2006

We study in this paper the integration of elastic and streaming traffic on a same link in an IP network. We are specifically interested in the computation of the mean bit rate obtained by a data transfer. For this purpose, we consider that the bit rate offered by streaming traffic is low, of the order of magnitude of a small parameter \eps \ll 1 and related to an auxiliary stationary Markovian process (X(t)). Under the assumption that data transfers are exponentially distributed, arrive according to a Poisson process, and share the available bandwidth according to the ideal processor sharing discipline, we derive the mean bit rate of a data transfer as a power series expansion in \eps. Since the system can be described by means of an M/M/1 queue with a time-varying server rate, which depends upon the parameter \eps and process (X(t)), the key issue is to compute an expansion of the area swept under the occupation process of this queue in a busy period. We obtain closed formulas for the power series expansion in \eps of the mean bit rate, which allow us to verify the validity of the so-called reduced service rate at the first order. The second order term yields more insight into the negative impact of the variability of streaming flows.
A comparison between two logical formalisms for rewriting
Venue: arXiv cs.LO 2006
Year: 2006

Meseguer's rewriting logic and the rewriting logic CRWL are two well-known approaches to rewriting as logical deduction that, despite some clear similarities, were designed with different objectives. Here we study the relationships between them, both at a syntactic and at a semantic level. Even though it is not possible to establish an entailment system map between them, both can be naturally simulated in each other. Semantically, there is no embedding between the corresponding institutions. Along the way, the notions of entailment and satisfaction in Meseguer's rewriting logic are generalized. We also use the syntactic results to prove reflective properties of CRWL.
Lighting Control using Pressure-Sensitive Touchpads
Venue: arXiv cs.HC 2006
Year: 2006

We introduce a novel approach to control physical lighting parameters by means of a pressure-sensitive touchpad. The two-dimensional area of the touchpad is subdivided into 5 virtual sliders, each controlling the intensity of a color (red, green, blue, yellow, and white). The physical interaction methodology is modeled directly after ubiquitous mechanical sliders and dimmers which tend to be used for intensity/volume control. Our abstraction to a pressure-sensitive touchpad provides advantages and introduces additional benefits over such existing devices.
Sending a Bi-Variate Gaussian Source over a Gaussian MAC
Venue: arXiv cs.IT 2006
Year: 2006

We consider a problem where a memoryless bi-variate Gaussian source is to be transmitted over an additive white Gaussian multiple-access channel with two transmitting terminals and one receiving terminal. The first transmitter only sees the first source component and the second transmitter only sees the second source component. We are interested in the pair of mean squared-error distortions at which the receiving terminal can reproduce each of the source components. It is demonstrated that in the symmetric case, below a certain signal-to-noise ratio (SNR) threshold, which is determined by the source correlation, uncoded communication is optimal. For SNRs above this threshold we present outer and inner bounds on the achievable distortions.
Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning
Venue: arXiv cs.AI 2006
Year: 2006

An original approach, termed Divide-and-Evolve is proposed to hybridize Evolutionary Algorithms (EAs) with Operational Research (OR) methods in the domain of Temporal Planning Problems (TPPs). Whereas standard Memetic Algorithms use local search methods to improve the evolutionary solutions, and thus fail when the local method stops working on the complete problem, the Divide-and-Evolve approach splits the problem at hand into several, hopefully easier, sub-problems, and can thus solve globally problems that are intractable when directly fed into deterministic OR algorithms. But the most prominent advantage of the Divide-and-Evolve approach is that it immediately opens up an avenue for multi-objective optimization, even though the OR method that is used is single-objective. Proof of concept approach on the standard (single-objective) Zeno transportation benchmark is given, and a small original multi-objective benchmark is proposed in the same Zeno framework to assess the multi-objective capabilities of the proposed methodology, a breakthrough in Temporal Planning.
Constraint-based verification of abstract models of multitreaded programs
Venue: arXiv cs.CL 2006
Year: 2006

We present a technique for the automated verification of abstract models of multithreaded programs providing fresh name generation, name mobility, and unbounded control. As high level specification language we adopt here an extension of communication finite-state machines with local variables ranging over an infinite name domain, called TDL programs. Communication machines have been proved very effective for representing communication protocols as well as for representing abstractions of multithreaded software. The verification method that we propose is based on the encoding of TDL programs into a low level language based on multiset rewriting and constraints that can be viewed as an extension of Petri Nets. By means of this encoding, the symbolic verification procedure developed for the low level language in our previous work can now be applied to TDL programs. Furthermore, the encoding allows us to isolate a decidable class of verification problems for TDL programs that still provide fresh name generation, name mobility, and unbounded control. Our syntactic restrictions are in fact defined on the internal structure of threads: In order to obtain a complete and terminating method, threads are only allowed to have at most one local variable (ranging over an infinite domain of names).
Artificial and Biological Intelligence
Venue: arXiv cs.AI 2006
Year: 2006

This article considers evidence from physical and biological sciences to show machines are deficient compared to biological systems at incorporating intelligence. Machines fall short on two counts: firstly, unlike brains, machines do not self-organize in a recursive manner; secondly, machines are based on classical logic, whereas Nature's intelligence may depend on quantum mechanics.
Control of a Lightweight Flexible Robotic Arm Using Sliding Modes
Venue: arXiv cs.RO 2006
Year: 2006

This paper presents a robust control scheme for flexible link robotic manipulators, which is based on considering the flexible mechanical structure as a system with slow (rigid) and fast (flexible) modes that can be controlled separately. The rigid dynamics is controlled by means of a robust sliding-mode approach with wellestablished stability properties while an LQR optimal design is adopted for the flexible dynamics. Experimental results show that this composite approach achieves good closed loop tracking properties both for the rigid and the flexible dynamics.
A Descriptive Model of Robot Team and the Dynamic Evolution of Robot Team Cooperation
Venue: arXiv cs.RO 2006
Year: 2006

At present, the research on robot team cooperation is still in qualitative analysis phase and lacks the description model that can quantitatively describe the dynamical evolution of team cooperative relationships with constantly changeable task demand in Multi-robot field. First this paper whole and static describes organization model HWROM of robot team, then uses Markov course and Bayesian theorem for reference, dynamical describes the team cooperative relationships building. Finally from cooperative entity layer, ability layer and relative layer we research team formation and cooperative mechanism, and discuss how to optimize relative action sets during the evolution. The dynamic evolution model of robot team and cooperative relationships between robot teams proposed and described in this paper can not only generalize the robot team as a whole, but also depict the dynamic evolving process quantitatively. Users can also make the prediction of the cooperative relationship and the action of the robot team encountering new demands based on this model. Journal web page & a lot of robotic related papers www.ars-journal.com