OpenRaiser/Intern-Atlas huggingface dataset:
Arithmetic Algorithms for Hereditarily Binary Natural Numbers
Venue: arXiv cs.DS 2013
Year: 2013

We study some essential arithmetic properties of a new tree-based number representation, {\em hereditarily binary numbers}, defined by applying recursively run-length encoding of bijective base-2 digits. Our representation expresses giant numbers like the largest known prime number and its related perfect number as well as the largest known Woodall, Cullen, Proth, Sophie Germain and twin primes as trees of small sizes. More importantly, our number representation supports novel algorithms that, in the best case, collapse the complexity of various computations by super-exponential factors and in the worse case are within a constant factor of their traditional counterparts. As a result, it opens the door to a new world, where arithmetic operations are limited by the structural complexity of their operands, rather than their bitsizes.
Decentralized Data Reduction with Quantization Constraints
Venue: arXiv cs.IT 2013
Year: 2013

A guiding principle for data reduction in statistical inference is the sufficiency principle. This paper extends the classical sufficiency principle to decentralized inference, i.e., data reduction needs to be achieved in a decentralized manner. We examine the notions of local and global sufficient statistics and the relationship between the two for decentralized inference under different observation models. We then consider the impacts of quantization on decentralized data reduction which is often needed when communications among sensors are subject to finite capacity constraints. The central question we intend to ask is: if each node in a decentralized inference system has to summarize its data using a finite number of bits, is it still optimal to implement data reduction using global sufficient statistics prior to quantization? We show that the answer is negative using a simple example and proceed to identify conditions under which sufficiency based data reduction followed by quantization is indeed optimal. They include the well known case when the data at decentralized nodes are conditionally independent as well as a class of problems with conditionally dependent observations that admit conditional independence structure through the introduction of an appropriately chosen hidden variable.
Recognition of Indian Sign Language in Live Video
Venue: arXiv cs.CV 2013
Year: 2013

Sign Language Recognition has emerged as one of the important area of research in Computer Vision. The difficulty faced by the researchers is that the instances of signs vary with both motion and appearance. Thus, in this paper a novel approach for recognizing various alphabets of Indian Sign Language is proposed where continuous video sequences of the signs have been considered. The proposed system comprises of three stages: Preprocessing stage, Feature Extraction and Classification. Preprocessing stage includes skin filtering, histogram matching. Eigen values and Eigen Vectors were considered for feature extraction stage and finally Eigen value weighted Euclidean distance is used to recognize the sign. It deals with bare hands, thus allowing the user to interact with the system in natural way. We have considered 24 different alphabets in the video sequences and attained a success rate of 96.25%.
Designing Run-Time Environments to Have Predefined Global Dynamics
Venue: arXiv cs.SE 2013
Year: 2013

The stability and the predictability of a computer network algorithm's performance are as important as the main functional purpose of networking software. However, asserting or deriving such properties from the finite state machine implementations of protocols is hard and, except for singular cases like TCP, is not done today. In this paper, we propose to design and study run-time environments for networking protocols which inherently enforce desirable, predictable global dynamics. To this end we merge two complementary design approaches: (i) A design-time and bottom up approach that enables us to engineer algorithms based on an analyzable (reaction) flow model. (ii) A run-time and top-down approach based on an autonomous stack composition framework, which switches among implementation alternatives to find optimal operation configurations. We demonstrate the feasibility of our self-optimizing system in both simulations and real-world Internet setups.
Partitioned scheduling of multimode multiprocessor real-time systems with temporal isolation
Venue: arXiv cs.OS 2013
Year: 2013

We consider the partitioned scheduling problem of multimode real-time systems upon identical multiprocessor platforms. During the execution of a multimode system, the system can change from one mode to another such that the current task set is replaced with a new one. In this paper, we consider a synchronous transition protocol in order to take into account mode-independent tasks, i.e., tasks of which the execution pattern must not be jeopardized by the mode changes. We propose two methods for handling mode changes in partitioned scheduling. The first method is offline/optimal and computes a static allocation of tasks schedulable and respecting both tasks and transition deadlines (if any). The second approach is subject to a sufficient condition in order to ensure online First Fit based allocation to satisfy the timing constraints.
Sorting suffixes of a text via its Lyndon Factorization
Venue: arXiv cs.DS 2013
Year: 2013

The process of sorting the suffixes of a text plays a fundamental role in Text Algorithms. They are used for instance in the constructions of the Burrows-Wheeler transform and the suffix array, widely used in several fields of Computer Science. For this reason, several recent researches have been devoted to finding new strategies to obtain effective methods for such a sorting. In this paper we introduce a new methodology in which an important role is played by the Lyndon factorization, so that the local suffixes inside factors detected by this factorization keep their mutual order when extended to the suffixes of the whole word. This property suggests a versatile technique that easily can be adapted to different implementative scenarios.
K-Algorithm A Modified Technique for Noise Removal in Handwritten Documents
Venue: arXiv cs.CV 2013
Year: 2013

OCR has been an active research area since last few decades. OCR performs the recognition of the text in the scanned document image and converts it into editable form. The OCR process can have several stages like pre-processing, segmentation, recognition and post processing. The pre-processing stage is a crucial stage for the success of OCR, which mainly deals with noise removal. In the present paper, a modified technique for noise removal named as K-Algorithm has been proposed, which has two stages as filtering and binarization. The proposed technique shows improvised results in comparison to median filtering technique.
Lattice Gas Symmetric Cryptography
Venue: arXiv cs.CR 2013
Year: 2013

Lattice gas cellular automata (Lgca) are particular cellular automata that imitate the behavior of par- ticles moving on a lattice. We used a particular set of Lgca rules, called hpp, to mix bits in data blocks and obtain a symmetric cryptographic algorithm. The encryption and decryption keys are the positions of perturbation sites on the lattice (walls). Basically, this paper presents an original way to perform cryp- tographic operations, based on cellular automata. In this paper, we show several characteristics about our algorithm: typical block size (2^(2n-1) ), key-length (2^n ), number of rounds (2^(n+1) ). We also evaluate avalanche and strict avalanche properties with respect to key and plain text. Finally, we highlight the underbellies of our method and give clues to solve them.
Policy Search: Any Local Optimum Enjoys a Global Performance Guarantee
Venue: arXiv cs.LG 2013
Year: 2013

Local Policy Search is a popular reinforcement learning approach for handling large state spaces. Formally, it searches locally in a paramet erized policy space in order to maximize the associated value function averaged over some predefined distribution. It is probably commonly b elieved that the best one can hope in general from such an approach is to get a local optimum of this criterion. In this article, we show th e following surprising result: \emph{any} (approximate) \emph{local optimum} enjoys a \emph{global performance guarantee}. We compare this g uarantee with the one that is satisfied by Direct Policy Iteration, an approximate dynamic programming algorithm that does some form of Poli cy Search: if the approximation error of Local Policy Search may generally be bigger (because local search requires to consider a space of s tochastic policies), we argue that the concentrability coefficient that appears in the performance bound is much nicer. Finally, we discuss several practical and theoretical consequences of our analysis.
Direct Uncertainty Estimation in Reinforcement Learning
Venue: arXiv cs.AI 2013
Year: 2013

Optimal probabilistic approach in reinforcement learning is computationally infeasible. Its simplification consisting in neglecting difference between true environment and its model estimated using limited number of observations causes exploration vs exploitation problem. Uncertainty can be expressed in terms of a probability distribution over the space of environment models, and this uncertainty can be propagated to the action-value function via Bellman iterations, which are computationally insufficiently efficient though. We consider possibility of directly measuring uncertainty of the action-value function, and analyze sufficiency of this facilitated approach.
Diversity Polynomials for the Analysis of Temporal Correlations in Wireless Networks
Venue: arXiv cs.IT 2013
Year: 2013

The interference in wireless networks is temporally correlated, since the node or user locations are correlated over time and the interfering transmitters are a subset of these nodes. For a wireless network where (potential) interferers form a Poisson point process and use ALOHA for channel access, we calculate the joint success and outage probabilities of n transmissions over a reference link. The results are based on the diversity polynomial, which captures the temporal interference correlation. The joint outage probability is used to determine the diversity gain (as the SIR goes to infinity), and it turns out that there is no diversity gain in simple retransmission schemes, even with independent Rayleigh fading over all links. We also determine the complete joint SIR distribution for two transmissions and the distribution of the local delay, which is the time until a repeated transmission over the reference link succeeds.
Verification of Query Completeness over Processes [Extended Version]
Venue: arXiv cs.DB 2013
Year: 2013

Data completeness is an essential aspect of data quality, and has in turn a huge impact on the effective management of companies. For example, statistics are computed and audits are conducted in companies by implicitly placing the strong assumption that the analysed data are complete. In this work, we are interested in studying the problem of completeness of data produced by business processes, to the aim of automatically assessing whether a given database query can be answered with complete information in a certain state of the process. We formalize so-called quality-aware processes that create data in the real world and store it in the company's information system possibly at a later point.
Condition Driven Adaptive Music Generation for Computer Games
Venue: arXiv cs.HC 2013
Year: 2013

The video game industry has grown to a multi-billion dollar, worldwide industry. The background music tends adaptively in reference to the specific game content during the game length of the play. Adaptive music should be further explored by looking at the particular condition in the game; such condition is driven by generating a specific music in the background which best fits in with the active game content throughout the length of the gameplay. This research paper outlines the use of condition driven adaptive music generation for audio and video to dynamically incorporate adaptively.
Making Sense out of a Jungle of JavaScript Frameworks: towards a Practitioner-friendly Comparative Analysis
Venue: arXiv cs.SE 2013
Year: 2013

The field of Web development is entering the HTML5 and CSS3 era and JavaScript is becoming increasingly influential. A large number of JavaScript frameworks have been recently promoted. Practitioners applying the latest technologies need to choose a suitable JavaScript framework (JSF) in order to abstract the frustrating and complicated coding steps and to provide a cross-browser compatibility. Apart from benchmark suites and recommendation from experts, there is little research helping practitioners to select the most suitable JSF to a given situation. The few proposals employ software metrics on the JSF, but practitioners are driven by different concerns when choosing a JSF. As an answer to the critical needs, this paper is a call for action. It proposes a re-search design towards a comparative analysis framework of JSF, which merges researcher needs and practitioner needs.
Artificial Ant Species on Solving Optimization Problems
Venue: arXiv cs.MA 2013
Year: 2013

During the last years several ant-based techniques were involved to solve hard and complex optimization problems. The current paper is a short study about the influence of artificial ant species in solving optimization problems. There are studied the artificial Pharaoh Ants, Lasius Niger and also artificial ants with no special specificity used commonly in Ant Colony Optimization.
An Improved Structure Of Reversible Adder And Subtractor
Venue: arXiv cs.AR 2013
Year: 2013

In today's world everyday a new technology which is faster, smaller and more complex than its predecessor is being developed. The increased number of transistors packed onto a chip of a conventional system results in increased power consumption that is why Reversible logic has drawn attention of Researchers due to its less heat dissipating characteristics. Reversible logic can be imposed over applications such as quantum computing, optical computing, quantum dot cellular automata, low power VLSI circuits, DNA computing. This paper presents the reversible combinational circuit of adder, subtractor and parity preserving subtractor. The suggested circuit in this paper are designed using Feynman, Double Feynman and MUX gates which are better than the existing one in literature in terms of Quantum cost, Garbage output and Total logical calculations.
Eventual Linear Ranking Functions
Venue: arXiv cs.PL 2013
Year: 2013

Program termination is a hot research topic in program analysis. The last few years have witnessed the development of termination analyzers for programming languages such as C and Java with remarkable precision and performance. These systems are largely based on techniques and tools coming from the field of declarative constraint programming. In this paper, we first recall an algorithm based on Farkas' Lemma for discovering linear ranking functions proving termination of a certain class of loops. Then we propose an extension of this method for showing the existence of eventual linear ranking functions, i.e., linear functions that become ranking functions after a finite unrolling of the loop. We show correctness and completeness of this algorithm.
Analytical Coexistence Benchmark for Assessing the Utmost Interference Tolerated by IEEE 802.20
Venue: arXiv cs.IT 2013
Year: 2013

Whether it is crosstalk, harmonics, or in-band operation of wireless technologies, interference between a reference system and a host of offenders is virtually unavoidable. In past contributions, a benchmark has been established and considered for coexistence analysis with a number of technologies including FWA, UMTS, and WiMAX. However, the previously presented model does not take into account the mobility factor of the reference node in addition to a number of interdependent requirements regarding the link direction, channel state, data rate and system factors; hence limiting its applicability for the MBWA (IEEE 802.20) standard. Thus, over diverse modes, in this correspondence we analytically derived the greatest aggregate interference level tolerated for high-fidelity transmission tailored specifically for the MBWA standard. Our results, in the form of benchmark indicators, should be of particular interest to peers analyzing and researching RF coexistence scenarios with this new protocol.
Practical Inlining of Functions with Free Variables
Venue: arXiv cs.PL 2013
Year: 2013

A long-standing practical challenge in the optimization of higher-order languages is inlining functions with free variables. Inlining code statically at a function call site is safe if the compiler can guarantee that the free variables have the same bindings at the inlining point as they do at the point where the function is bound as a closure (code and free variables). There have been many attempts to create a heuristic to check this correctness condition, from Shivers' kCFA-based reflow analysis to Might's Delta-CFA and anodization, but all of those have performance unsuitable for practical compiler implementations. In practice, modern language implementations rely on a series of tricks to capture some common cases (e.g., closures whose free variables are only top-level identifiers such as +) and rely on hand-inlining by the programmer for anything more complicated. This work provides the first practical, general approach for inlining functions with free variables. We also provide a proof of correctness, an evaluation of both the execution time and performance impact of this optimization, and some tips and tricks for implementing an efficient and precise control-flow analysis.
Rendezvous of Two Robots with Constant Memory
Venue: arXiv cs.MA 2013
Year: 2013

We study the impact that persistent memory has on the classical rendezvous problem of two mobile computational entities, called robots, in the plane. It is well known that, without additional assumptions, rendezvous is impossible if the entities are oblivious (i.e., have no persistent memory) even if the system is semi-synchronous (SSynch). It has been recently shown that rendezvous is possible even if the system is asynchronous (ASynch) if each robot is endowed with O(1) bits of persistent memory, can transmit O(1) bits in each cycle, and can remember (i.e., can persistently store) the last received transmission. This setting is overly powerful. In this paper we weaken that setting in two different ways: (1) by maintaining the O(1) bits of persistent memory but removing the communication capabilities; and (2) by maintaining the O(1) transmission capability and the ability to remember the last received transmission, but removing the ability of an agent to remember its previous activities. We call the former setting finite-state (FState) and the latter finite-communication (FComm). Note that, even though its use is very different, in both settings, the amount of persistent memory of a robot is constant. We investigate the rendezvous problem in these two weaker settings. We model both settings as a system of robots endowed with visible lights: in FState, a robot can only see its own light, while in FComm a robot can only see the other robot's light. We prove, among other things, that finite-state robots can rendezvous in SSynch, and that finite-communication robots are able to rendezvous even in ASynch. All proofs are constructive: in each setting, we present a protocol that allows the two robots to rendezvous in finite time.
(c-)AND: A new graph model
Venue: arXiv cs.DM 2013
Year: 2013

In this document, we study the scope of the following graph model: each vertex is assigned to a box in a metric space and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our study on the case where boxes (and therefore representative elements) associated to vertices are spread in the Euclidean line. We give both, a combinatorial and an intersection characterization of the model. Based on these characterizations, we determine graph families that contain the model (e. g., boxicity 2 graphs) and others that the new model contains (e. g., rooted directed path). We also study the particular case where each representative element is the center of its respective box. In this particular case, we provide constructive representations for interval, block and outerplanar graphs. Finally, we show that the general and the particular model are not equivalent by constructing a graph family that separates the two cases.
CSMA over Time-varying Channels: Optimality, Uniqueness and Limited Backoff Rate
Venue: arXiv cs.NI 2013
Year: 2013

Recent studies on MAC scheduling have shown that carrier sense multiple access (CSMA) algo- rithms can be throughput optimal for arbitrary wireless network topology. However, these results are highly sensitive to the underlying assumption on 'static' or 'fixed' system conditions. For example, if channel conditions are time-varying, it is unclear how each node can adjust its CSMA parameters, so-called backoff and channel holding times, using its local channel information for the desired high performance. In this paper, we study 'channel-aware' CSMA (A-CSMA) algorithms in time-varying channels, where they adjust their parameters as some function of the current channel capacity. First, we show that the achievable rate region of A-CSMA equals to the maximum rate region if and only if the function is exponential. Furthermore, given an exponential function in A-CSMA, we design updating rules for their parameters, which achieve throughput optimality for an arbitrary wireless network topology. They are the first CSMA algorithms in the literature which are proved to be throughput optimal under time-varying channels. Moreover, we also consider the case when back-off rates of A- CSMA are highly restricted compared to the speed of channel variations, and characterize the throughput performance of A-CSMA in terms of the underlying wireless network topology. Our results not only guide a high-performance design on MAC scheduling under highly time-varying scenarios, but also provide new insights on the performance of CSMA algorithms in relation to their backoff rates and the network topology.
Flexibly-bounded Rationality and Marginalization of Irrationality Theories for Decision Making
Venue: arXiv cs.AI 2013
Year: 2013

In this paper the theory of flexibly-bounded rationality which is an extension to the theory of bounded rationality is revisited. Rational decision making involves using information which is almost always imperfect and incomplete together with some intelligent machine which if it is a human being is inconsistent to make decisions. In bounded rationality, this decision is made irrespective of the fact that the information to be used is incomplete and imperfect and that the human brain is inconsistent and thus this decision that is to be made is taken within the bounds of these limitations. In the theory of flexibly-bounded rationality, advanced information analysis is used, the correlation machine is applied to complete missing information and artificial intelligence is used to make more consistent decisions. Therefore flexibly-bounded rationality expands the bounds within which rationality is exercised. Because human decision making is essentially irrational, this paper proposes the theory of marginalization of irrationality in decision making to deal with the problem of satisficing in the presence of irrationality.