OpenRaiser/Intern-Atlas huggingface dataset:
Design, Development and Testing of Underwater Vehicles: ITB Experience
Venue: arXiv cs.RO 2008
Year: 2008

The last decade has witnessed increasing worldwide interest in the research of underwater robotics with particular focus on the area of autonomous underwater vehicles (AUVs). The underwater robotics technology has enabled human to access the depth of the ocean to conduct environmental surveys, resources mapping as well as scientific and military missions. This capability is especially valuable for countries with major water or oceanic resources. As an archipelagic nation with more than 13,000 islands, Indonesia has one of the most abundant living and non-organic oceanic resources. The needs for the mapping, exploration, and environmental preservation of the vast marine resources are therefore imperative. The challenge of the deep water exploration has been the complex issues associated with hazardous and unstructured undersea and sea-bed environments. The paper reports the design, development and testing efforts of underwater vehicle that have been conducted at Institut Teknologi Bandung. Key technology areas have been identified and step-by-step development is presented in conjunction with the need to meet the challenge of underwater vehicle operation. A number of future research directions are also highlighted.
Complexity of Hybrid Logics over Transitive Frames
Venue: arXiv cs.LO 2008
Year: 2008

This paper examines the complexity of hybrid logics over transitive frames, transitive trees, and linear frames. We show that satisfiability over transitive frames for the hybrid language extended with the downarrow operator is NEXPTIME-complete. This is in contrast to undecidability of satisfiability over arbitrary frames for this language (Areces, Blackburn, Marx 1999). It is also shown that adding the @ operator or the past modality leads to undecidability over transitive frames. This is again in contrast to the case of transitive trees and linear frames, where we show these languages to be nonelementarily decidable. Moreover, we establish 2EXPTIME and EXPTIME upper bounds for satisfiability over transitive frames and transitive trees, respectively, for the hybrid Until/Since language. An EXPTIME lower bound is shown to hold for the modal Until language over both frame classes.
An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
Venue: arXiv cs.CG 2008
Year: 2008

For a set P of n points in R^2, the Euclidean 2-center problem computes a pair of congruent disks of the minimal radius that cover P. We extend this to the (2,k)-center problem where we compute the minimal radius pair of congruent disks to cover n-k points of P. We present a randomized algorithm with O(n k^7 log^3 n) expected running time for the (2,k)-center problem. We also study the (p,k)-center problem in R}^2 under the \ell_\infty-metric. We give solutions for p=4 in O(k^{O(1)} n log n) time and for p=5 in O(k^{O(1)} n log^5 n) time.
On Field Size and Success Probability in Network Coding
Venue: arXiv cs.IT 2008
Year: 2008

Using tools from algebraic geometry and Groebner basis theory we solve two problems in network coding. First we present a method to determine the smallest field size for which linear network coding is feasible. Second we derive improved estimates on the success probability of random linear network coding. These estimates take into account which monomials occur in the support of the determinant of the product of Edmonds matrices. Therefore we finally investigate which monomials can occur in the determinant of the Edmonds matrix.
On the Throughput Allocation for Proportional Fairness in Multirate IEEE 802.11 DCF
Venue: arXiv cs.NI 2008
Year: 2008

This paper presents a modified proportional fairness (PF) criterion suitable for mitigating the \textit{rate anomaly} problem of multirate IEEE 802.11 Wireless LANs employing the mandatory Distributed Coordination Function (DCF) option. Compared to the widely adopted assumption of saturated network, the proposed criterion can be applied to general networks whereby the contending stations are characterized by specific packet arrival rates, $λ_s$, and transmission rates $R_d^{s}$. The throughput allocation resulting from the proposed algorithm is able to greatly increase the aggregate throughput of the DCF while ensuring fairness levels among the stations of the same order of the ones available with the classical PF criterion. Put simply, each station is allocated a throughput that depends on a suitable normalization of its packet rate, which, to some extent, measures the frequency by which the station tries to gain access to the channel. Simulation results are presented for some sample scenarios, confirming the effectiveness of the proposed criterion.
Locality and Bounding-Box Quality of Two-Dimensional Space-Filling Curves
Venue: arXiv cs.CG 2008
Year: 2008

Space-filling curves can be used to organise points in the plane into bounding-box hierarchies (such as R-trees). We develop measures of the bounding-box quality of space-filling curves that express how effective different space-filling curves are for this purpose. We give general lower bounds on the bounding-box quality measures and on locality according to Gotsman and Lindenbaum for a large class of space-filling curves. We describe a generic algorithm to approximate these and similar quality measures for any given curve. Using our algorithm we find good approximations of the locality and the bounding-box quality of several known and new space-filling curves. Surprisingly, some curves with relatively bad locality by Gotsman and Lindenbaum's measure, have good bounding-box quality, while the curve with the best-known locality has relatively bad bounding-box quality.
Game Refinement Relations and Metrics
Venue: arXiv cs.LO 2008
Year: 2008

We consider two-player games played over finite state spaces for an infinite number of rounds. At each state, the players simultaneously choose moves; the moves determine a successor state. It is often advantageous for players to choose probability distributions over moves, rather than single moves. Given a goal, for example, reach a target state, the question of winning is thus a probabilistic one: what is the maximal probability of winning from a given state? On these game structures, two fundamental notions are those of equivalences and metrics. Given a set of winning conditions, two states are equivalent if the players can win the same games with the same probability from both states. Metrics provide a bound on the difference in the probabilities of winning across states, capturing a quantitative notion of state similarity. We introduce equivalences and metrics for two-player game structures, and we show that they characterize the difference in probability of winning games whose goals are expressed in the quantitative mu-calculus. The quantitative mu-calculus can express a large set of goals, including reachability, safety, and omega-regular properties. Thus, we claim that our relations and metrics provide the canonical extensions to games, of the classical notion of bisimulation for transition systems. We develop our results both for equivalences and metrics, which generalize bisimulation, and for asymmetrical versions, which generalize simulation.
Research report: State complexity of operations on two-way quantum finite automata
Venue: arXiv cs.DM 2008
Year: 2008

This paper deals with the size complexity of minimal {\it two-way quantum finite automata} (2qfa's) necessary for operations to perform on all inputs of each fixed length. Such a complexity measure, known as state complexity of operations, is useful in measuring how much information is necessary to convert languages. We focus on intersection, union, reversals, and catenation operations and show some upper bounds of state complexity of operations on 2qfa's. Also, we present a number of non-regular languages and prove that these languages can be accepted by 2qfa's with one-sided error probabilities within linear time. Notably, these examples show that our bounds obtained for these operations are not tight, and therefore worth improving. We give an instance to show that the upper bound of the state number for the simulation of one-way deterministic finite automata by two-way reversible finite automata is not tight in general.
Modeling belief systems with scale-free networks
Venue: arXiv cs.AI 2008
Year: 2008

Evolution of belief systems has always been in focus of cognitive research. In this paper we delineate a new model describing belief systems as a network of statements considered true. Testing the model a small number of parameters enabled us to reproduce a variety of well-known mechanisms ranging from opinion changes to development of psychological problems. The self-organizing opinion structure showed a scale-free degree distribution. The novelty of our work lies in applying a convenient set of definitions allowing us to depict opinion network dynamics in a highly favorable way, which resulted in a scale-free belief network. As an additional benefit, we listed several conjectural consequences in a number of areas related to thinking and reasoning.
Decomposition of Multiple Coverings into More Parts
Venue: arXiv cs.CG 2008
Year: 2008

We prove that for every centrally symmetric convex polygon Q, there exists a constant alpha such that any alpha*k-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Toth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery lifetime.
On the Capacity of Pairwise Collaborative Networks
Venue: arXiv cs.IT 2008
Year: 2008

We derive expressions for the achievable rate region of a collaborative coding scheme in a two-transmitter, two-receiver Pairwise Collaborative Network (PCN) where one transmitter and receiver pair, namely relay pair, assists the other pair, namely the source pair, by partially decoding and forwarding the transmitted message to the intended receiver. The relay pair provides such assistance while handling a private message. We assume that users can use the past channel outputs and can transmit and receive at the same time and in the same frequency band. In this collaborative scheme, the transmitter of the source pair splits its information into two independent parts. Ironically, the relay pair employs the decode and forward coding to assist the source pair in delivering a part of its message and re-encodes the decoded message along with private message, which is intended to the receiver of the relay pair, and broadcasts the results. The receiver of the relay pair decodes both messages, retrieves the private message, re-encodes and transmits the decoded massage to the intended destination. We also characterize the achievable rate region for Gaussian PCN. Finally, we provide numerical results to study the rate trade off for the involved pairs. Numerical result shows that the collaboration offers gain when the channel gain between the users of the relay pair are strong. It also shows that if the channel conditions between transmitters or between the receivers of the relay and source pairs are poor, such a collaboration is not beneficial.
Bloomier Filters: A second look
Venue: arXiv cs.DS 2008
Year: 2008

A Bloom filter is a space efficient structure for storing static sets, where the space efficiency is gained at the expense of a small probability of false-positives. A Bloomier filter generalizes a Bloom filter to compactly store a function with a static support. In this article we give a simple construction of a Bloomier filter. The construction is linear in space and requires constant time to evaluate. The creation of our Bloomier filter takes linear time which is faster than the existing construction. We show how one can improve the space utilization further at the cost of increasing the time for creating the data structure.
WCET analysis of multi-level set-associative instruction caches
Venue: arXiv cs.PF 2008
Year: 2008

With the advent of increasingly complex hardware in real-time embedded systems (processors with performance enhancing features such as pipelines, cache hierarchy, multiple cores), many processors now have a set-associative L2 cache. Thus, there is a need for considering cache hierarchies when validating the temporal behavior of real-time systems, in particular when estimating tasks' worst-case execution times (WCETs). To the best of our knowledge, there is only one approach for WCET estimation for systems with cache hierarchies [Mueller, 1997], which turns out to be unsafe for set-associative caches. In this paper, we highlight the conditions under which the approach described in [Mueller, 1997] is unsafe. A safe static instruction cache analysis method is then presented. Contrary to [Mueller, 1997] our method supports set-associative and fully associative caches. The proposed method is experimented on medium-size and large programs. We show that the method is most of the time tight. We further show that in all cases WCET estimations are much tighter when considering the cache hierarchy than when considering only the L1 cache. An evaluation of the analysis time is conducted, demonstrating that analysing the cache hierarchy has a reasonable computation time.
A General Framework for Sound and Complete Floyd-Hoare Logics
Venue: arXiv cs.LO 2008
Year: 2008

This paper presents an abstraction of Hoare logic to traced symmetric monoidal categories, a very general framework for the theory of systems. Our abstraction is based on a traced monoidal functor from an arbitrary traced monoidal category into the category of pre-orders and monotone relations. We give several examples of how our theory generalises usual Hoare logics (partial correctness of while programs, partial correctness of pointer programs), and provide some case studies on how it can be used to develop new Hoare logics (run-time analysis of while programs and stream circuits).
Flux: FunctionaL Updates for XML (extended report)
Venue: arXiv cs.PL 2008
Year: 2008

XML database query languages have been studied extensively, but XML database updates have received relatively little attention, and pose many challenges to language design. We are developing an XML update language called Flux, which stands for FunctionaL Updates for XML, drawing upon ideas from functional programming languages. In prior work, we have introduced a core language for Flux with a clear operational semantics and a sound, decidable static type system based on regular expression types. Our initial proposal had several limitations. First, it lacked support for recursive types or update procedures. Second, although a high-level source language can easily be translated to the core language, it is difficult to propagate meaningful type errors from the core language back to the source. Third, certain updates are well-formed yet contain path errors, or ``dead'' subexpressions which never do any useful work. It would be useful to detect path errors, since they often represent errors or optimization opportunities. In this paper, we address all three limitations. Specifically, we present an improved, sound type system that handles recursion. We also formalize a source update language and give a translation to the core language that preserves and reflects typability. We also develop a path-error analysis (a form of dead-code analysis) for updates.
Quantum Query Complexity of Multilinear Identity Testing
Venue: arXiv cs.CC 2008
Year: 2008

Motivated by the quantum algorithm in \cite{MN05} for testing commutativity of black-box groups, we study the following problem: Given a black-box finite ring $R=\angle{r_1,...,r_k}$ where $\{r_1,r_2,...,r_k\}$ is an additive generating set for $R$ and a multilinear polynomial $f(x_1,...,x_m)$ over $R$ also accessed as a black-box function $f:R^m\to R$ (where we allow the indeterminates $x_1,...,x_m$ to be commuting or noncommuting), we study the problem of testing if $f$ is an \emph{identity} for the ring $R$. More precisely, the problem is to test if $f(a_1,a_2,...,a_m)=0$ for all $a_i\in R$. We give a quantum algorithm with query complexity $O(m(1+α)^{m/2} k^{\frac{m}{m+1}})$ assuming $k\geq (1+1/α)^{m+1}$. Towards a lower bound, we also discuss a reduction from a version of $m$-collision to this problem. We also observe a randomized test with query complexity $4^mmk$ and constant success probability and a deterministic test with $k^m$ query complexity.
Inductive and Coinductive Components of Corecursive Functions in Coq
Venue: arXiv cs.LO 2008
Year: 2008

In Constructive Type Theory, recursive and corecursive definitions are subject to syntactic restrictions which guarantee termination for recursive functions and productivity for corecursive functions. However, many terminating and productive functions do not pass the syntactic tests. Bove proposed in her thesis an elegant reformulation of the method of accessibility predicates that widens the range of terminative recursive functions formalisable in Constructive Type Theory. In this paper, we pursue the same goal for productive corecursive functions. Notably, our method of formalisation of coinductive definitions of productive functions in Coq requires not only the use of ad-hoc predicates, but also a systematic algorithm that separates the inductive and coinductive parts of functions.
Online Scheduling to Minimize the Maximum Delay Factor
Venue: arXiv cs.DS 2008
Year: 2008

In this paper two scheduling models are addressed. First is the standard model (unicast) where requests (or jobs) are independent. The other is the broadcast model where broadcasting a page can satisfy multiple outstanding requests for that page. We consider online scheduling of requests when they have deadlines. Unlike previous models, which mainly consider the objective of maximizing throughput while respecting deadlines, here we focus on scheduling all the given requests with the goal of minimizing the maximum {\em delay factor}.We prove strong lower bounds on the achievable competitive ratios for delay factor scheduling even with unit-time requests.For the unicast model we give algorithms that are $(1 + \eps)$-speed $O({1 \over \eps})$-competitive in both the single machine and multiple machine settings. In the broadcast model we give an algorithm for similar-sized pages that is $(2+ \eps)$-speed $O({1 \over \eps^2})$-competitive. For arbitrary page sizes we give an algorithm that is $(4+\eps)$-speed $O({1 \over \eps^2})$-competitive.
The Five Points Pose Problem : A New and Accurate Solution Adapted to any Geometric Configuration
Venue: arXiv cs.CV 2008
Year: 2008

The goal of this paper is to estimate directly the rotation and translation between two stereoscopic images with the help of five homologous points. The methodology presented does not mix the rotation and translation parameters, which is comparably an important advantage over the methods using the well-known essential matrix. This results in correct behavior and accuracy for situations otherwise known as quite unfavorable, such as planar scenes, or panoramic sets of images (with a null base length), while providing quite comparable results for more "standard" cases. The resolution of the algebraic polynomials resulting from the modeling of the coplanarity constraint is made with the help of powerful algebraic solver tools (the Groebner bases and the Rational Univariate Representation).
Derandomizing the Lovasz Local Lemma more effectively
Venue: arXiv cs.DS 2008
Year: 2008

The famous Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. Kratochvil et al. applied this technique to prove that a k-CNF in which each variable appears at most 2^k/(ek) times is always satisfiable [KST93]. In a breakthrough paper, Beck found that if we lower the occurrences to O(2^(k/48)/k), then a deterministic polynomial-time algorithm can find a satisfying assignment to such an instance [Bec91]. Alon randomized the algorithm and required O(2^(k/8)/k) occurrences [Alo91]. In [Mos06], we exhibited a refinement of his method which copes with O(2^(k/6)/k) of them. The hitherto best known randomized algorithm is due to Srinivasan and is capable of solving O(2^(k/4)/k) occurrence instances [Sri08]. Answering two questions asked by Srinivasan, we shall now present an approach that tolerates O(2^(k/2)/k) occurrences per variable and which can most easily be derandomized. The new algorithm bases on an alternative type of witness tree structure and drops a number of limiting aspects common to all previous methods.
An Efficient Algorithm for a Sharp Approximation of Universally Quantified Inequalities
Venue: arXiv cs.NA 2008
Year: 2008

This paper introduces a new algorithm for solving a sub-class of quantified constraint satisfaction problems (QCSP) where existential quantifiers precede universally quantified inequalities on continuous domains. This class of QCSPs has numerous applications in engineering and design. We propose here a new generic branch and prune algorithm for solving such continuous QCSPs. Standard pruning operators and solution identification operators are specialized for universally quantified inequalities. Special rules are also proposed for handling the parameters of the constraints. First experimentation show that our algorithm outperforms the state of the art methods.
An ESPRIT-based approach for Initial Ranging in OFDMA systems
Venue: arXiv cs.IT 2008
Year: 2008

This work presents a novel Initial Ranging scheme for orthogonal frequency-division multiple-access networks. Users that intend to establish a communication link with the base station (BS) are normally misaligned both in time and frequency and the goal is to jointly estimate their timing errors and carrier frequency offsets with respect to the BS local references. This is accomplished with affordable complexity by resorting to the ESPRIT algorithm. Computer simulations are used to assess the effectiveness of the proposed solution and to make comparisons with existing alternatives.
On Endogenous Reconfiguration in Mobile Robotic Networks
Venue: arXiv cs.RO 2008
Year: 2008

In this paper, our focus is on certain applications for mobile robotic networks, where reconfiguration is driven by factors intrinsic to the network rather than changes in the external environment. In particular, we study a version of the coverage problem useful for surveillance applications, where the objective is to position the robots in order to minimize the average distance from a random point in a given environment to the closest robot. This problem has been well-studied for omni-directional robots and it is shown that optimal configuration for the network is a centroidal Voronoi configuration and that the coverage cost belongs to $Θ(m^{-1/2})$, where $m$ is the number of robots in the network. In this paper, we study this problem for more realistic models of robots, namely the double integrator (DI) model and the differential drive (DD) model. We observe that the introduction of these motion constraints in the algorithm design problem gives rise to an interesting behavior. For a \emph{sparser} network, the optimal algorithm for these models of robots mimics that for omni-directional robots. We propose novel algorithms whose performances are within a constant factor of the optimal asymptotically (i.e., as $m \to +\infty$). In particular, we prove that the coverage cost for the DI and DD models of robots is of order $m^{-1/3}$. Additionally, we show that, as the network grows, these novel algorithms outperform the conventional algorithm; hence necessitating a reconfiguration in the network in order to maintain optimal quality of service.
The rank convergence of HITS can be slow
Venue: arXiv cs.DS 2008
Year: 2008

We prove that HITS, to "get right" h of the top k ranked nodes of an N>=2k node graph, can require h^(Omega(N h/k)) iterations (i.e. a substantial Omega(N h log(h)/k) matrix multiplications even with a "squaring trick"). Our proof requires no algebraic tools and is entirely self-contained.