OpenRaiser/Intern-Atlas huggingface dataset:
More Compact Oracles for Approximate Distances in Planar Graphs
Venue: arXiv cs.DS 2011
Year: 2011

Distance oracles are data structures that provide fast (possibly approximate) answers to shortest-path and distance queries in graphs. The tradeoff between the space requirements and the query time of distance oracles is of particular interest and the main focus of this paper. In FOCS'01, Thorup introduced approximate distance oracles for planar graphs. He proved that, for any eps>0 and for any planar graph on n nodes, there exists a (1+eps)-approximate distance oracle using space O(n eps^{-1} log n) such that approximate distance queries can be answered in time O(1/eps). Ten years later, we give the first improvements on the space-querytime tradeoff for planar graphs. * We give the first oracle having a space-time product with subquadratic dependency on 1/eps. For space ~O(n log n) we obtain query time ~O(1/eps) (assuming polynomial edge weights). The space shows a doubly logarithmic dependency on 1/eps only. We believe that the dependency on eps may be almost optimal. * For the case of moderate edge weights (average bounded by polylog(n), which appears to be the case for many real-world road networks), we hit a "sweet spot," improving upon Thorup's oracle both in terms of eps and n. Our oracle uses space ~O(n log log n) and it has query time ~O(log log log n + 1/eps). (Asymptotic notation in this abstract hides low-degree polynomials in log(1/eps) and log*(n).)
A Software Tool for Legal Drafting
Venue: arXiv cs.CY 2011
Year: 2011

Although many attempts at automated aids for legal drafting have been made, they were based on the construction of a new tool, completely from scratch. This is at least curious, considering that a strong parallelism can be established between a normative document and a software specification: both describe what an entity should or should not do, can or cannot do. In this article we compare normative documents and software specifications to find out their similarities and differences. The comparison shows that there are distinctive particularities, but they are restricted to a very specific subclass of normative propositions. The rest, we postulate, can be dealt with software tools. For such an enterprise the \FormaLex tool set was devised: an LTL-based language and companion tools that utilize model checking to find out normative incoherences in regulations, contracts and other legal documents. A feature-rich case study is analyzed with the presented tools.
Selection of Model in Developing Information Security Criteria for Smart Grid Security System
Venue: arXiv cs.CR 2011
Year: 2011

At present, the "Smart Grid" has emerged as one of the best advanced energy supply chains. This paper looks into the security system of smart grid via the smart planet system. The scope focused on information security criteria that impact on consumer trust and satisfaction. The importance of information security criteria is perceived as the main aspect to impact on customer trust throughout the entire smart grid system. On one hand, this paper also focuses on the selection of the model for developing information security criteria on a smart grid.
Two Classes of Broadcast Channels With Side-Information: Capacity Outer Bounds
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we derive outer bounds on the capacity region of two classes of the general two-user discrete memoryless broadcast channels with side-information at the transmitter. The first class comprises the classical broadcast channel where a sender transmits two independent messages to two receivers. A constraint that each message must be kept confidential from the unintended receiver constitutes the second class. For both classes, the conditional distribution characterizing the channel depends on a state process and the encoder has side-information provided to it in a noncausal manner. For the first class of channels, an outer bound is derived employing techniques used to prove the converse theorem for the Gel'fand-Pinsker's channel with random parameters; the bounds are tight for individual rate constraints, but can be improved upon for the sum rate. The technique for deriving outer bounds for the second class of channels hinges on the confidentiality requirements; we also derive a genie-aided outer bound, where a hypothetical genie gives the unintended message to a receiver which treats it as side-information during equivocation computation. For both classes of channels, Csiszár's sum identity plays a central role in establishing the capacity outer bounds.
Design and Performance Evaluation of A New Proposed Fittest Job First Dynamic Round Robin(FJFDRR) Scheduling Algorithm
Venue: arXiv cs.OS 2011
Year: 2011

In this paper, we have proposed a new variant of Round Robin scheduling algorithm by executing the processes according to the new calculated Fit Factor f and using the concept of dynamic time quantum. We have compared the performance of our proposed Fittest Job First Dynamic Round Robin(FJFDRR) algorithm with the Priority Based Static Round Robin(PBSRR) algorithm. Experimental results show that our proposed algorithm performs better than PBSRR in terms of reducing the number of context switches, average waiting time and average turnaround time.
Approximation of Löwdin Orthogonalization to a Spectrally Efficient Orthogonal Overlapping PPM Design for UWB Impulse Radio
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we consider the design of spectrally efficient time-limited pulses for ultrawideband (UWB) systems using an overlapping pulse position modulation scheme. For this we investigate an orthogonalization method, which was developed in 1950 by Per-Olov Löwdin. Our objective is to obtain a set of N orthogonal (Löwdin) pulses, which remain time-limited and spectrally efficient for UWB systems, from a set of N equidistant translates of a time-limited optimal spectral designed UWB pulse. We derive an approximate Löwdin orthogonalization (ALO) by using circulant approximations for the Gram matrix to obtain a practical filter implementation. We show that the centered ALO and Löwdin pulses converge pointwise to the same Nyquist pulse as N tends to infinity. The set of translates of the Nyquist pulse forms an orthonormal basis or the shift-invariant space generated by the initial spectral optimal pulse. The ALO transform provides a closed-form approximation of the Löwdin transform, which can be implemented in an analog fashion without the need of analog to digital conversions. Furthermore, we investigate the interplay between the optimization and the orthogonalization procedure by using methods from the theory of shift-invariant spaces. Finally we develop a connection between our results and wavelet and frame theory.
A Non-Iterative Solution to the Four-Point Three-Views Pose Problem in Case of Collinear Cameras
Venue: arXiv cs.CV 2011
Year: 2011

We give a non-iterative solution to a particular case of the four-point three-views pose problem when three camera centers are collinear. Using the well-known Cayley representation of orthogonal matrices, we derive from the epipolar constraints a system of three polynomial equations in three variables. The eliminant of that system is a multiple of a 36th degree univariate polynomial. The true (unique) solution to the problem can be expressed in terms of one of real roots of that polynomial. Experiments on synthetic data confirm that our method is robust enough even in case of planar configurations.
Effectively Nonblocking Consensus Procedures Can Execute Forever - a Constructive Version of FLP
Venue: arXiv cs.LO 2011
Year: 2011

The Fischer-Lynch-Paterson theorem (FLP) says that it is impossible for processes in an asynchronous distributed system to achieve consensus on a binary value when a single process can fail; it is a widely cited theoretical result about network computing. All proofs that I know depend essentially on classical (nonconstructive) logic, although they use the hypothetical construction of a nonterminating execution as a main lemma. FLP is also a guide for protocol designers, and in that role there is a connection to an important property of consensus procedures, namely that they should not block, i.e. reach a global state in which no process can decide. A deterministic fault-tolerant consensus protocol is effectively nonblocking if from any reachable global state we can find an execution path that decides. In this article we effectively construct a nonterminating execution of any such protocol. That is, given any effectively nonblocking protocol P and a natural number n, we show how to compute the n-th step of an infinitely indecisive computation of P. From this fully constructive result, the classical FLP follows as a corollary as well as a stronger classical result, called here Strong FLP. Moreover, the construction focuses attention on the important role of nonblocking in protocol design. An interesting consequence of the constructive proof is that we can, in principle, build an undefeatable attacker for a consensus protocol that is provably correct, indeed because it is provably correct. We can do this in practice on certain kinds of networks.
Universal adaptive self-stabilizing traversal scheme: random walk and reloading wave
Venue: arXiv cs.DC 2011
Year: 2011

In this paper, we investigate random walk based token circulation in dynamic environments subject to failures. We describe hypotheses on the dynamic environment that allow random walks to meet the important property that the token visits any node infinitely often. The randomness of this scheme allows it to work on any topology, and require no adaptation after a topological change, which is a desirable property for applications to dynamic systems. For random walks to be a traversal scheme and to answer the concurrence problem, one needs to guarantee that exactly one token circulates in the system. In the presence of transient failures, configurations with multiple tokens or with no token can occur. The meeting property of random walks solves the cases with multiple tokens. The reloading wave mechanism we propose, together with timeouts, allows to detect and solve cases with no token. This traversal scheme is self-stabilizing, and universal, meaning that it needs no assumption on the system topology. We describe conditions on the dynamicity (with a local detection criterion) under which the algorithm is tolerant to dynamic reconfigurations. We conclude by a study on the time between two visits of the token to a node, which we use to tune the parameters of the reloading wave mechanism according to some system characteristics.
IR-based Communication and Perception in Microrobotic Swarms
Venue: arXiv cs.RO 2011
Year: 2011

In this work we consider development of IR-based communication and perception mechanisms for real microrobotic systems. It is demonstrated that a specific combination of hardware and software elements provides capabilities for navigation, objects recognition, directional and unidirectional communication. We discuss open issues and their resolution based on the experiments in the swarm of microrobots "Jasmine".
Learning where to Attend with Deep Architectures for Image Tracking
Venue: arXiv cs.AI 2011
Year: 2011

We discuss an attentional model for simultaneous object tracking and recognition that is driven by gaze data. Motivated by theories of perception, the model consists of two interacting pathways: identity and control, intended to mirror the what and where pathways in neuroscience models. The identity pathway models object appearance and performs classification using deep (factored)-Restricted Boltzmann Machines. At each point in time the observations consist of foveated images, with decaying resolution toward the periphery of the gaze. The control pathway models the location, orientation, scale and speed of the attended object. The posterior distribution of these states is estimated with particle filtering. Deeper in the control pathway, we encounter an attentional mechanism that learns to select gazes so as to minimize tracking uncertainty. Unlike in our previous work, we introduce gaze selection strategies which operate in the presence of partial information and on a continuous action space. We show that a straightforward extension of the existing approach to the partial information setting results in poor performance, and we propose an alternative method based on modeling the reward surface as a Gaussian Process. This approach gives good performance in the presence of partial information and allows us to expand the action space from a small, discrete set of fixation points to a continuous domain.
Two-Dimensional Tail-Biting Convolutional Codes
Venue: arXiv cs.IT 2011
Year: 2011

The multidimensional convolutional codes are an extension of the notion of convolutional codes (CCs) to several dimensions of time. This paper explores the class of two-dimensional convolutional codes (2D CCs) and 2D tail-biting convolutional codes (2D TBCCs), in particular, from several aspects. First, we derive several basic algebraic properties of these codes, applying algebraic methods in order to find bijective encoders, create parity check matrices and to inverse encoders. Next, we discuss the minimum distance and weight distribution properties of these codes. Extending an existing tree-search algorithm to two dimensions, we apply it to find codes with high minimum distance. Word-error probability asymptotes for sample codes are given and compared with other codes. The results of this approach suggest that 2D TBCCs can perform better than comparable 1D TBCCs or other codes. We then present several novel iterative suboptimal algorithms for soft decoding 2D CCs, which are based on belief propagation. Two main approaches to decoding are considered. We first focus on a decoder which extends the concept of trellis decoding to two dimensions. Second, we investigate algorithms which use the code's parity check matrices. We apply conventional BP in the parity domain, but improve it with a novel modification. Next, we test the generalized belief propagation (GBP) algorithm. Performance results are presented and compared with optimum decoding techniques and bounds. The results show that our suboptimal algorithms achieve respectable results, in some cases coming as close as 0.2dB from optimal (maximum-likelihood) decoding. However for some of the codes there is still a large gap from the optimal decoder.
On-Demand Multicasting in Ad-hoc Networks: Performance Evaluation of AODV, ODMRP and FSR
Venue: arXiv cs.NI 2011
Year: 2011

Adhoc networks are characterized by connectivity through a collection of wireless nodes and fast changing network topology. Wireless nodes are free to move independent of each other which makes routing much difficult. This calls for the need of an efficient dynamic routing protocol. Mesh-based multicast routing technique establishes communications between mobile nodes of wireless adhoc networks in a faster and efficient way. In this article the performance of prominent on-demand routing protocols for mobile adhoc networks such as ODMRP (On Demand Multicast Routing Protocol), AODV (Adhoc on Demand Distance Vector) and FSR (Fisheye State Routing protocol) was studied. The parameters viz., average throughput, packet delivery ration and end-to-end delay were evaluated. From the simulation results and analysis, a suitable routing protocol can be chosen for a specified network. The results show that the ODMRP protocol performance is remarkably superior as compared with AODV and FSR routing protocols. Keywords: MANET, Multicast Routing, ODMRP, AODV, FSR.
Tying up the loose ends in fully LZW-compressed pattern matching
Venue: arXiv cs.DS 2011
Year: 2011

We consider a natural generalization of the classical pattern matching problem: given compressed representations of a pattern p[1..M] and a text t[1..N] of sizes m and n, respectively, does p occur in t? We develop an optimal linear time solution for the case when both p and t are compressed using the LZW method. This improves the previously known O((n+m)log(n+m)) time solution of Gasieniec and Rytter, and essentially closes the line of research devoted to studying LZW-compressed exact pattern matching.
Implementing Continuation based language in GCC
Venue: arXiv cs.PL 2011
Year: 2011

We have implemented C like Continuation based programming language. Continuation based C, CbC was implemented using micro-C on various architecture, and we have tried several CbC programming experiments. Here we report new implementation of CbC compiler based on GCC 4.2.3. Since it contains full C capability, we can use CbC and C in a mixture.
Secure Multiplex Coding Over Interference Channel with Confidential Messages
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, inner and outer bounds on the capacity region of two-user interference channels with two confidential messages have been proposed. By adding secure multiplex coding to the error correction method in [15] which achieves the best achievable capacity region for interference channel up to now, we have shown that the improved secure capacity region compared with [2] now is the whole Han-Kobayashi region. In addition, this construction not only removes the rate loss incurred by adding dummy messages to achieve security, but also change the original weak security condition in [2] to strong security. Then the equivocation rate for a collection of secret messages has also been evaluated, when the length of the message is finite or the information rate is high, our result provides a good approximation for bounding the worst case equivocation rate. Our results can be readily extended to the Gaussian interference channel with little efforts.
Three Cases of Connectivity and Global Information Transfer in Robot Swarms
Venue: arXiv cs.RO 2011
Year: 2011

In this work we consider three different cases of robot-robot interactions and resulting global information transfer in robot swarms. These mechanisms define cooperative properties of the system and can be used for designing collective behavior. These three cases are demonstrated and discussed based on experiments in a swarm of microrobots "Jasmine".
Pushdown Abstractions of JavaScript
Venue: arXiv cs.PL 2011
Year: 2011

We design a family of program analyses for JavaScript that make no approximation in matching calls with returns, exceptions with handlers, and breaks with labels. We do so by starting from an established reduction semantics for JavaScript and systematically deriving its intensional abstract interpretation. Our first step is to transform the semantics into an equivalent low-level abstract machine: the JavaScript Abstract Machine (JAM). We then give an infinite-state yet decidable pushdown machine whose stack precisely models the structure of the concrete program stack. The precise model of stack structure in turn confers precise control-flow analysis even in the presence of control effects, such as exceptions and finally blocks. We give pushdown generalizations of traditional forms of analysis such as k-CFA, and prove the pushdown framework for abstract interpretation is sound and computable.
Empirical study of sensor observation services server instances
Venue: arXiv cs.NI 2011
Year: 2011

The number of Sensor Observation Service (SOS) instances available online has been increasing in the last few years. The SOS specification standardises interfaces and data formats for exchanging sensor-related in-formation between information providers and consumers. SOS in conjunction with other specifications in the Sensor Web Enablement initiative, at-tempts to realise the Sensor Web vision, a worldwide system where sensor networks of any kind are interconnected. In this paper we present an empirical study of actual instances of servers implementing SOS. The study focuses mostly in which parts of the specification are more frequently included in real implementations, and how exchanged messages follows the structure defined by XML Schema files. Our findings can be of practical use when implementing servers and clients based on the SOS specification, as they can be optimized for common scenarios.
From X to Pi; Representing the Classical Sequent Calculus in the Pi-calculus
Venue: arXiv cs.LO 2011
Year: 2011

We study the Pi-calculus, enriched with pairing and non-blocking input, and define a notion of type assignment that uses the type constructor "arrow". We encode the circuits of the calculus X into this variant of Pi, and show that all reduction (cut-elimination) and assignable types are preserved. Since X enjoys the Curry-Howard isomorphism for Gentzen's calculus LK, this implies that all proofs in LK have a representation in Pi.
Note on a simple type system for non-interference
Venue: arXiv cs.LO 2011
Year: 2011

We consider CCS with value passing and elaborate a notion of noninterference for the process calculi, which matches closely that of the programming language. The idea is to view channels as information carriers rather than as "events", so that emitting a secret on output channel can be considered safe, while inputting a secret may lead to some kind of leakage. This is in contrast with the standard notion of noninterference for the process calculi where any causal dependency of low-level action from any high-level action is forbidden.
An O(n^2) Time Algorithm for Alternating Büchi Games
Venue: arXiv cs.GT 2011
Year: 2011

Computing the winning set for B{ü}chi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is $\tilde{O}(n \cdot m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph. We are the first to break the $\tilde{O}(n\cdot m)$ bound by presenting a new technique that reduces the running time to $O(n^2)$. This bound also leads to an $O(n^2)$ algorithm time for computing the set of almost-sure winning vertices in alternating games with probabilistic transitions (improving an earlier bound of $\tilde{O}(n\cdot m)$) and in concurrent graph games with constant actions (improving an earlier bound of $O(n^3)$). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time $O(n^2)$. Finally, we show how to maintain the winning set for B{ü}chi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.
A Complexity Separation Between the Cache-Coherent and Distributed Shared Memory Models
Venue: arXiv cs.DC 2011
Year: 2011

We consider asynchronous multiprocessor systems where processes communicate by accessing shared memory. Exchange of information among processes in such a multiprocessor necessitates costly memory accesses called \emph{remote memory references} (RMRs), which generate communication on the interconnect joining processors and main memory. In this paper we compare two popular shared memory architecture models, namely the \emph{cache-coherent} (CC) and \emph{distributed shared memory} (DSM) models, in terms of their power for solving synchronization problems efficiently with respect to RMRs. The particular problem we consider entails one process sending a "signal" to a subset of other processes. We show that a variant of this problem can be solved very efficiently with respect to RMRs in the CC model, but not so in the DSM model, even when we consider amortized RMR complexity. To our knowledge, this is the first separation in terms of amortized RMR complexity between the CC and DSM models. It is also the first separation in terms of RMR complexity (for asynchronous systems) that does not rely in any way on wait-freedom---the requirement that a process makes progress in a bounded number of its own steps.