OpenRaiser/Intern-Atlas huggingface dataset:
Leader Election and Gathering for Asynchronous Transparent Fat Robots without Chirality
Venue: arXiv cs.DC 2012
Year: 2012

This paper proposes a distributed algorithm which deterministically gathers n (n > 4) asynchronous, fat robots. The robots are assumed to be transparent and they have full visibility. The robots are initially considered to be stationary. A robot is visible in its motion. The robots do not store past actions. They are anonymous and can not be distinguished by their appearances and do not have common coordinate system or chirality. The robots do not communicate through message passing. In the proposed gathering algorithm one robot moves at a time towards its destination. The robot which moves, is selected in such a way that, it will be the only robot eligible to move, until it reaches its destination. In case of a tie, this paper proposes a leader election algorithm which produces an ordering of the robots and the first robot in the ordering becomes the leader. The ordering is unique in the sense that, each robot, characterized by its location, agrees on the same ordering. We show that if a set of robots can be ordered then they can gather deterministically. The paper also characterizes the cases, where ordering is not possible. This paper also presents an important fact that, if leader election is possible then gathering pattern formation is possible even with no chirality.
Forward Analysis for WSTS, Part II: Complete WSTS
Venue: arXiv cs.LO 2012
Year: 2012

We describe a simple, conceptual forward analysis procedure for infinity-complete WSTS S. This computes the so-called clover of a state. When S is the completion of a WSTS X, the clover in S is a finite description of the downward closure of the reachability set. We show that such completions are infinity-complete exactly when X is an omega-2-WSTS, a new robust class of WSTS. We show that our procedure terminates in more cases than the generalized Karp-Miller procedure on extensions of Petri nets and on lossy channel systems. We characterize the WSTS where our procedure terminates as those that are clover-flattable. Finally, we apply this to well-structured counter systems.
Throughput Maximization for an Energy Harvesting Communication System with Processing Cost
Venue: arXiv cs.IT 2012
Year: 2012

In wireless networks, energy consumed for communication includes both the transmission and the processing energy. In this paper, point-to-point communication over a fading channel with an energy harvesting transmitter is studied considering jointly the energy costs of transmission and processing. Under the assumption of known energy arrival and fading profiles, optimal transmission policy for throughput maximization is investigated. Assuming that the transmitter has sufficient amount of data in its buffer at the beginning of the transmission period, the average throughput by a given deadline is maximized. Furthermore, a "directional glue pouring algorithm" that computes the optimal transmission policy is described.
Power Controlled Adaptive Sum-Capacity of Fading MACs with Distributed CSI
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of finding optimal, fair and distributed power-rate strategies to achieve the sum capacity of the Gaussian multiple-access block-fading channel. In here, the transmitters have access to only their own fading coefficients, while the receiver has global access to all the fading coefficients. Outage is not permitted in any communication block. The resulting average sum-throughput is also known as `power-controlled adaptive sum-capacity', which appears as an open problem in literature. This paper presents the power-controlled adaptive sum-capacity of a wide-class of popular MAC models. In particular, we propose a power-rate strategy in the presence of distributed channel state information (CSI), which is throughput optimal when all the users have identical channel statistics. The proposed scheme also has an efficient implementation using successive cancellation and rate-splitting. We propose an upperbound when the channel laws are not identical. Furthermore, the optimal schemes are extended to situations in which each transmitter has additional finite-rate partial CSI on the link quality of others.
Performance Analysis of Dual-User Macrodiversity MIMO Systems with Linear Receivers in Flat Rayleigh Fading
Venue: arXiv cs.IT 2012
Year: 2012

The performance of linear receivers in the presence of co-channel interference in Rayleigh channels is a fundamental problem in wireless communications. Performance evaluation for these systems is well-known for receive arrays where the antennas are close enough to experience equal average SNRs from a source. In contrast, almost no analytical results are available for macrodiversity systems where both the sources and receive antennas are widely separated. Here, receive antennas experience unequal average SNRs from a source and a single receive antenna receives a different average SNR from each source. Although this is an extremely difficult problem, progress is possible for the two-user scenario. In this paper, we derive closed form results for the probability density function (pdf) and cumulative distribution function (cdf) of the output signal to interference plus noise ratio (SINR) and signal to noise ratio (SNR) of minimum mean squared error (MMSE) and zero forcing (ZF) receivers in independent Rayleigh channels with arbitrary numbers of receive antennas. The results are verified by Monte Carlo simulations and high SNR approximations are also derived. The results enable further system analysis such as the evaluation of outage probability, bit error rate (BER) and capacity.
Defense against SYN-Flood Denial of Service Attacks Based on Learning Automata
Venue: arXiv cs.NI 2012
Year: 2012

SYN-flooding attack uses the weakness available in TCP's three-way handshake process to keep it from handling legitimate requests. This attack causes the victim host to populate its backlog queue with forged TCP connections. In other words it increases Ploss (probability of loss) and Pa (buffer occupancy percentage of attack requests) and decreases Pr (buffer occupancy percentage of regular requests) in the victim host and results to decreased performance of the host. This paper proposes a self-managing approach, in which the host defends against SYN-flooding attack by dynamically tuning of its own two parameters, that is, m (maximum number of half-open connections) and h (hold time for each half-open connection). In this way, it formulates the defense problem to an optimization problem and then employs the learning automata (LA) algorithm to solve it. The simulation results show that the proposed defense strategy improves performance of the under attack system in terms of Ploss, Pa and Pr.
On the existence of a neutral region
Venue: arXiv cs.CG 2012
Year: 2012

Consider a given space, e.g., the Euclidean plane, and its decomposition into Voronoi regions induced by given sites. It seems intuitively clear that each point in the space belongs to at least one of the regions, i.e., no neutral region can exist. As simple counterexamples show this is not true in general, but we present a simple necessary and sufficient condition ensuring the non-existence of a neutral region. We discuss a similar phenomenon concerning recent variations of Voronoi diagrams called zone diagrams, double zone diagrams, and (double) territory diagrams. These objects are defined in a somewhat implicit way and they also induce a decomposition of the space into regions. In several works it was claimed without providing a proof that some of these objects induce a decomposition in which a neutral region must exist. We show that this assertion is true in a wide class of cases but not in general. We also discuss other properties related to the neutral region, among them a one related to the concentration of measure phenomenon.
Decreasing defect rate of test cases by designing and analysis for recursive modules of a program structure: Improvement in test cases
Venue: arXiv cs.SE 2012
Year: 2012

Designing and analysis of test cases is a challenging tasks for tester roles especially those who are related to test the structure of program. Recently, Programmers are showing valuable trend towards the implementation of recursive modules in a program structure. In testing phase of software development life cycle, test cases help the tester to test the structure and flow of program. The implementation of well designed test cases for a program leads to reduce the defect rate and efforts needed for corrective maintenance. In this paper, author proposed a strategy to design and analyze the test cases for a program structure of recursive modules. This strategy will definitely leads to validation of program structure besides reducing the defect rate and corrective maintenance efforts.
A Theory of Pricing Private Data
Venue: arXiv cs.CR 2012
Year: 2012

Personal data has value to both its owner and to institutions who would like to analyze it. Privacy mechanisms protect the owner's data while releasing to analysts noisy versions of aggregate query results. But such strict protections of individual's data have not yet found wide use in practice. Instead, Internet companies, for example, commonly provide free services in return for valuable sensitive information from users, which they exploit and sometimes sell to third parties. As the awareness of the value of the personal data increases, so has the drive to compensate the end user for her private information. The idea of monetizing private data can improve over the narrower view of hiding private data, since it empowers individuals to control their data through financial means. In this paper we propose a theoretical framework for assigning prices to noisy query answers, as a function of their accuracy, and for dividing the price amongst data owners who deserve compensation for their loss of privacy. Our framework adopts and extends key principles from both differential privacy and query pricing in data markets. We identify essential properties of the price function and micro-payments, and characterize valid solutions.
The Effects of Limited Channel Knowledge on Cognitive Radio System Capacity
Venue: arXiv cs.IT 2012
Year: 2012

We examine the impact of limited channel knowledge on the secondary user (SU) in a cognitive radio system. Under a minimum signal-to-interference-and-noise ratio (SINR) constraint for the primary user (PU) receiver, we determine the SU capacity under five channel knowledge scenarios. We derive analytical expressions for the capacity cumulative distribution functions and the probability of SU blocking as a function of allowable interference. We show that imperfect knowledge of the PU-PU channel gain by the SU-Tx often prohibits SU transmission or necessitates a high interference level at the PU. We also show that errored knowledge of the PU-PU channel is more beneficial than statistical channel knowledge and imperfect knowledge of the SU-Tx to PU-Rx link has a limited impact on SU capacity.
Expected Supremum of a Random Linear Combination of Shifted Kernels
Venue: arXiv cs.IT 2012
Year: 2012

We address the expected supremum of a linear combination of shifts of the sinc kernel with random coefficients. When the coefficients are Gaussian, the expected supremum is of order \sqrt{\log n}, where n is the number of shifts. When the coefficients are uniformly bounded, the expected supremum is of order \log\log n. This is a noteworthy difference to orthonormal functions on the unit interval, where the expected supremum is of order \sqrt{n\log n} for all reasonable coefficient statistics.
Generating All Minimal Edge Dominating Sets with Incremental-Polynomial Delay
Venue: arXiv cs.DS 2012
Year: 2012

For an arbitrary undirected simple graph G with m edges, we give an algorithm with running time O(m^4 |L|^2) to generate the set L of all minimal edge dominating sets of G. For bipartite graphs we obtain a better result; we show that their minimal edge dominating sets can be enumerated in time O(m^4 |L|). In fact our results are stronger; both algorithms generate the next minimal edge dominating set with incremental-polynomial delay O(m^5 |L|) and O(m^4 |L|) respectively, when L is the set of already generated minimal edge dominating sets. Our algorithms are tailored for and solve the equivalent problems of enumerating minimal (vertex) dominating sets of line graphs and line graphs of bipartite graphs, with incremental-polynomial delay, and consequently in output-polynomial time. Enumeration of minimal dominating sets in graphs has very recently been shown to be equivalent to enumeration of minimal transversals in hypergraphs. The question whether the minimal transversals of a hypergraph can be enumerated in output-polynomial time is a fundamental and challenging question in Output-Sensitive Enumeration; it has been open for several decades and has triggered extensive research in the field.
Planning Random path distributions for ambush games in unstructured environments
Venue: arXiv cs.RO 2012
Year: 2012

Operating vehicles in adversarial environments require non-conventional planning techniques. A two-player, zero-sum non-cooperative game is introduced, which is solved via a linear program. An extension is proposed to construct networks displaying good representations of the environment characteristics, while offering acceptable results for the technique used. Sensitivity of the solution to the LP solver algorithm is identified. The performances of the planner are finally assessed by comparison with those of conventional planners. Results are used to formulate secondary objectives to the problem.
CRAW: Combination of Re-Keying and Authentication in Wireless Networks for Secure Multicast Increasing Efficiency of Member Join/Leave and Movement
Venue: arXiv cs.CR 2012
Year: 2012

Recently, the number of requests for multicast services through the wireless networks has been increased. However, for successful deployment, security and efficiency of content delivery must be provided at first. This paper presents a new approach for secure multicast in wireless networks. This approach, CRAW (Combination of Re-keying and Authentication in Wireless networks) combines member authentication procedure with group key management protocol to provide an efficient group re-keying process. One-time password is proposed for member authentication and CKC (Code for Key Calculation) is suggested for group key management in wireless networks. In fact, the combination of authentication with group key management in wireless networks results in a simple and secure mechanism both for authentication and group key management while mobile members join/leave a group or move inter-area. Simulation results show that CRAW reduces re-keying overhead at join from O(log2 n+1) to O(1) while security requirements are saved. Also, CRAW introduces storing a main list to manage mobile members' location while they move intra-group inter-area.
Dynamic Pricing of Power in Smart-Grid Networks
Venue: arXiv cs.SY 2012
Year: 2012

In this paper we introduce the problem of dynamic pricing of power for smart-grid networks. This is studied within a network utility maximization (NUM) framework in a deterministic setting with a single provider, multiple users and a finite horizon. The provider produces power or buys power in a (deterministic) spot market, and determines a dynamic price to charge the users. The users then adjust their demand in response to the time-varying prices. This is typically categorized as the demand response problem, and we study a progression of related models by focusing on two aspects: 1) the characterization of the structure of the optimal dynamic prices in the Smart Grid and the optimal demand and supply under various interaction with a spot market; 2) a greedy approach to facilitate the solution process of the aggregate NUM problem and the optimality gap between the greedy solution and the optimal one.
Distance Measures for Sequences
Venue: arXiv cs.IT 2012
Year: 2012

Given a set of sequences, the distance between pairs of them helps us to find their similarity and derive structural relationship amongst them. For genomic sequences such measures make it possible to construct the evolution tree of organisms. In this paper we compare several distance measures and examine a method that involves circular shifting one sequence against the other for finding good alignment to minimize Hamming distance. We also use run-length encoding together with LZ77 to characterize information in a binary sequence.
Efficient Construction of Dominating Set in Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

Considering a communication topology of a wireless network modeled by a graph where an edge exists between two nodes if they are within each other's communication range. A subset $U$ of nodes is a dominating set if each node is either in $U$ or adjacent to some node in $U$. Assume each node has a disparate communication range and is associated with a positive weight, we present a randomized algorithm to find a min-weight dominating set. Considering any orientation of the graph where an arc $\overrightarrow{uv}$ exists if the node $v$ lies in $u$'s communication range. A subset $U$ of nodes is a strongly dominating set if every node except $U$ has both in-neighbor(s) and out-neighbor(s) in $U$. We present a polynomial-time algorithm to find a strongly dominating set of size at most $(2+ε)$ times of the optimum. We also investigate another related problem called $K$-Coverage. Given are a set ${\cal D}$ of disks with positive weight and a set ${\cal P}$ of nodes. Assume all input nodes lie below a horizontal line $l$ and all input disks lie above this line $l$ in the plane. The objective is to find a min-weight subset ${\cal D}'\subseteq {\cal D}$ of disks such that each node is covered at least $K$ disks in ${\cal D}'$. We propose a novel two-approximation algorithm for this problem.
Sequence Randomization Using Convolutional Codes and Probability Functions
Venue: arXiv cs.CR 2012
Year: 2012

This paper investigates the use of different transformations for improving the randomness of sequences. In particular, convolutional codes are used for increasing the size of a given sequence and then a random mapping function is used for further randomization. We have shown how such a method can convert highly correlated sequences into random ones.
In the Maze of Data Languages
Venue: arXiv cs.FL 2012
Year: 2012

In data languages the positions of strings and trees carry a label from a finite alphabet and a data value from an infinite alphabet. Extensions of automata and logics over finite alphabets have been defined to recognize data languages, both in the string and tree cases. In this paper we describe and compare the complexity and expressiveness of such models to understand which ones are better candidates as regular models.
Wreath Products of Forest Algebras, with Applications to Tree Logics
Venue: arXiv cs.LO 2012
Year: 2012

We use the recently developed theory of forest algebras to find algebraic characterizations of the languages of unranked trees and forests definable in various logics. These include the temporal logics CTL and EF, and first-order logic over the ancestor relation. While the characterizations are in general non-effective, we are able to use them to formulate necessary conditions for definability and provide new proofs that a number of languages are not definable in these logics.
Graph Symmetry Detection and Canonical Labeling: Differences and Synergies
Venue: arXiv cs.DS 2012
Year: 2012

Symmetries of combinatorial objects are known to complicate search algorithms, but such obstacles can often be removed by detecting symmetries early and discarding symmetric subproblems. Canonical labeling of combinatorial objects facilitates easy equivalence checking through quick matching. All existing canonical labeling software also finds symmetries, but the fastest symmetry-finding software does not perform canonical labeling. In this work, we contrast the two problems and dissect typical algorithms to identify their similarities and differences. We then develop a novel approach to canonical labeling where symmetries are found first and then used to speed up the canonical labeling algorithms. Empirical results show that this approach outperforms state-of-the-art canonical labelers.
Automated Marble Plate Classification System Based On Different Neural Network Input Training Sets and PLC Implementation
Venue: arXiv cs.NE 2012
Year: 2012

The process of sorting marble plates according to their surface texture is an important task in the automated marble plate production. Nowadays some inspection systems in marble industry that automate the classification tasks are too expensive and are compatible only with specific technological equipment in the plant. In this paper a new approach to the design of an Automated Marble Plate Classification System (AMPCS),based on different neural network input training sets is proposed, aiming at high classification accuracy using simple processing and application of only standard devices. It is based on training a classification MLP neural network with three different input training sets: extracted texture histograms, Discrete Cosine and Wavelet Transform over the histograms. The algorithm is implemented in a PLC for real-time operation. The performance of the system is assessed with each one of the input training sets. The experimental test results regarding classification accuracy and quick operation are represented and discussed.
A Widely Applicable Bayesian Information Criterion
Venue: arXiv cs.LG 2012
Year: 2012

A statistical model or a learning machine is called regular if the map taking a parameter to a probability distribution is one-to-one and if its Fisher information matrix is always positive definite. If otherwise, it is called singular. In regular statistical models, the Bayes free energy, which is defined by the minus logarithm of Bayes marginal likelihood, can be asymptotically approximated by the Schwarz Bayes information criterion (BIC), whereas in singular models such approximation does not hold. Recently, it was proved that the Bayes free energy of a singular model is asymptotically given by a generalized formula using a birational invariant, the real log canonical threshold (RLCT), instead of half the number of parameters in BIC. Theoretical values of RLCTs in several statistical models are now being discovered based on algebraic geometrical methodology. However, it has been difficult to estimate the Bayes free energy using only training samples, because an RLCT depends on an unknown true distribution. In the present paper, we define a widely applicable Bayesian information criterion (WBIC) by the average log likelihood function over the posterior distribution with the inverse temperature $1/\log n$, where $n$ is the number of training samples. We mathematically prove that WBIC has the same asymptotic expansion as the Bayes free energy, even if a statistical model is singular for and unrealizable by a statistical model. Since WBIC can be numerically calculated without any information about a true distribution, it is a generalized version of BIC onto singular statistical models.
Is Wolfram and Cook's (2,5) Turing machine really universal?
Venue: arXiv cs.FL 2012
Year: 2012

Wolfram [2, p. 707] and Cook [1, p. 3] claim to prove that a (2,5) Turing machine (2 states, 5 symbols) is universal, via a universal cellular automaton known as Rule 110. The first part of this paper points out a critical gap in their argument. The second part bridges the gap, thereby giving what appears to be the first proof of universality.