OpenRaiser/Intern-Atlas huggingface dataset:
Subtyping for F-Bounded Quantifiers and Equirecursive Types (Extended Version)
Venue: arXiv cs.PL 2012
Year: 2012

This paper defines a notion of binding trees that provide a suitable model for second-order type systems with F-bounded quantifiers and equirecursive types. It defines a notion of regular binding trees that correspond in the right way to notions of regularity in the first-order case. It defines a notion of subtyping on these trees and proves various properties of the subtyping relation. It defines a mapping from types to trees and shows that types produce regular binding trees. It presents a set of type equality and subtyping rules, and proves them sound and complete with respect to the tree interpretation. It defines a notion of binding-tree automata and how these generate regular binding trees. It gives a polynomial-time algorithm for deciding when two automata's trees are in the subtyping relation.
Evaluation of the Improved XP Software Development Model
Venue: arXiv cs.SE 2012
Year: 2012

The concept of agile process models has attained great popularity in software (SW) development community in last few years. Agile models promote fast development. Fast development has certain drawbacks, such as weak documentation and performance for medium and large development projects. Fast development also promotes use of agile process models in small-scale projects. This paper modifies and evaluates Extreme Programming (XP) process model and proposes a novel process model based on these modifications.
Empirical Evaluation of the Proposed eXScrum Model: Results of a Case Study
Venue: arXiv cs.SE 2012
Year: 2012

Agile models promote fast development. XP and Scrum are the most widely used agile models. This paper investigates the phases of XP and Scrum models in order to identify their potentials and drawbacks. XP model has certain drawbacks, such as not suitable for maintenance projects and poor performance for medium and large-scale development projects. Scrum model has certain limitations, such as lacked in engineering practices. Since, both XP and Scrum models contain good features and strengths but still there are improvement possibilities in these models. Majority of the software development companies are reluctant to switch from traditional methodologies to agile methodologies for development of industrial projects. A fine integration, of software management of the Scrum model and engineering practices of XP model, is very much required to accumulate the strengths and remove the limitations of both models. This is achieved by proposing an eXScrum model. The proposed model is validated by conducting a controlled case study. The results of case study show that the proposed integrated eXScrum model enriches the potentials of both XP and Scrum models and eliminates their drawbacks.
A Simulation Model for Evaluating Distributed Systems Dependability
Venue: arXiv cs.DC 2012
Year: 2012

In this paper we present a new simulation model designed to evaluate the dependability in distributed systems. This model extends the MONARC simulation model with new capabilities for capturing reliability, safety, availability, security, and maintainability requirements. The model has been implemented as an extension of the multithreaded, process oriented simulator MONARC, which allows the realistic simulation of a wide-range of distributed system technologies, with respect to their specific components and characteristics. The extended simulation model includes the necessary components to inject various failure events, and provides the mechanisms to evaluate different strategies for replication, redundancy procedures, and security enforcement mechanisms, as well. The results obtained in simulation experiments presented in this paper probe that the use of discrete-event simulators, such as MONARC, in the design and development of distributed systems is appealing due to their efficiency and scalability.
A Model for Web Page Usage Mining Based on Segmentation
Venue: arXiv cs.IR 2012
Year: 2012

The web page usage mining plays a vital role in enriching the page's content and structure based on the feedbacks received from the user's interactions with the page. This paper proposes a model for micro-managing the tracking activities by fine-tuning the mining from the page level to the segment level. The proposed model enables the web-master to identify the segments which receives more focus from users comparing with others. The segment level analytics of user actions provides an important metric to analyse the factors which facilitate the increase in traffic for the page. The empirical validation of the model is performed through prototype implementation.
Risk Assessment Techniques and Survey Method for COTS Components
Venue: arXiv cs.SE 2012
Year: 2012

The Rational Unified Process a software engineering process is gaining popularity nowadays. RUP delivers best software practices for component software Development life cycle It supports component based software development. Risk is involved in every component development phase .neglecting those risks sometimes hampers the software growth and leads to negative outcome. In Order to provide appropriate security and protection levels, identifying various risks is very vital. Therefore Risk identification plays a very crucial role in the component based software development This report addresses incorporation of component based software development cycle into RUP phases, assess several category of risk encountered in the component based software. It also entails a survey method to identify the risk factor and evaluating the overall severity of the component software development in terms of the risk. Formula for determining risk prevention cost and finding the risk probability is also been included. The overall goal of the paper is to provide a theoretical foundation that facilitates a good understanding of risk in relation to componentbased system development
Multi-Level Error-Resilient Neural Networks with Learning
Venue: arXiv cs.NE 2012
Year: 2012

The problem of neural network association is to retrieve a previously memorized pattern from its noisy version using a network of neurons. An ideal neural network should include three components simultaneously: a learning algorithm, a large pattern retrieval capacity and resilience against noise. Prior works in this area usually improve one or two aspects at the cost of the third. Our work takes a step forward in closing this gap. More specifically, we show that by forcing natural constraints on the set of learning patterns, we can drastically improve the retrieval capacity of our neural network. Moreover, we devise a learning algorithm whose role is to learn those patterns satisfying the above mentioned constraints. Finally we show that our neural network can cope with a fair amount of noise.
Decentralized Multi-agent Plan Repair in Dynamic Environments
Venue: arXiv cs.AI 2012
Year: 2012

Achieving joint objectives by teams of cooperative planning agents requires significant coordination and communication efforts. For a single-agent system facing a plan failure in a dynamic environment, arguably, attempts to repair the failed plan in general do not straightforwardly bring any benefit in terms of time complexity. However, in multi-agent settings the communication complexity might be of a much higher importance, possibly a high communication overhead might be even prohibitive in certain domains. We hypothesize that in decentralized systems, where coordination is enforced to achieve joint objectives, attempts to repair failed multi-agent plans should lead to lower communication overhead than replanning from scratch. The contribution of the presented paper is threefold. Firstly, we formally introduce the multi-agent plan repair problem and formally present the core hypothesis underlying our work. Secondly, we propose three algorithms for multi-agent plan repair reducing the problem to specialized instances of the multi-agent planning problem. Finally, we present results of experimental validation confirming the core hypothesis of the paper.
Geometric Pricing: How Low Dimensionality Helps in Approximability
Venue: arXiv cs.GT 2012
Year: 2012

Consider the following toy problem. There are $m$ rectangles and $n$ points on the plane. Each rectangle $R$ is a consumer with budget $B_R$, who is interested in purchasing the cheapest item (point) inside R, given that she has enough budget. Our job is to price the items to maximize the revenue. This problem can also be defined on higher dimensions. We call this problem the geometric pricing problem. In this paper, we study a new class of problems arising from a geometric aspect of the pricing problem. It intuitively captures typical real-world assumptions that have been widely studied in marketing research, healthcare economics, etc. It also helps classify other well-known pricing problems, such as the highway pricing problem and the graph vertex pricing problem on planar and bipartite graphs. Moreover, this problem turns out to have close connections to other natural geometric problems such as the geometric versions of the unique coverage and maximum feasible subsystem problems. We show that the low dimensionality arising in this pricing problem does lead to improved approximation ratios, by presenting sublinear-approximation algorithms for two central versions of the problem: unit-demand uniform-budget min-buying and single-minded pricing problems. Our algorithm is obtained by combining algorithmic pricing and geometric techniques. These results suggest that considering geometric aspect might be a promising research direction in obtaining improved approximation algorithms for such pricing problems. To the best of our knowledge, this is one of very few problems in the intersection between geometry and algorithmic pricing areas. Thus its study may lead to new algorithmic techniques that could benefit both areas.
Visual definition of procedures for automatic virtual scene generation
Venue: arXiv cs.GR 2012
Year: 2012

With more and more digital media, especially in the field of virtual reality where detailed and convincing scenes are much required, procedural scene generation is a big helping tool for artists. A problem is that defining scene descriptions through these procedures usually requires a knowledge in formal language grammars, programming theory and manually editing textual files using a strict syntax, making it less intuitive to use. Luckily, graphical user interfaces has made a lot of tasks on computers easier to perform and out of the belief that creating computer programs can also be one of them, visual programming languages (VPLs) have emerged. The goal in VPLs is to shift more work from the programmer to the integrated development environment (IDE), making programming an user-friendlier task. In this thesis, an approach of using a VPL for defining procedures that automatically generate virtual scenes is presented. The methods required to build a VPL are presented, including a novel method of generating readable code in a structured programming language. Also, the methods for achieving basic principles of VPLs will be shown -- suitable visual presentation of information and guiding the programmer in the right direction using constraints. On the other hand, procedural generation methods are presented in the context of visual programming -- adapting the application programming interface (API) of these methods to better serve the user. The main focus will be on the methods for urban modeling, such as building, city layout and details generation with random number generation used to create non-deterministic scenes.
On Effectiveness of Backlog Bounds Using Stochastic Network Calculus in 802.11
Venue: arXiv cs.NI 2012
Year: 2012

Network calculus is a powerful methodology of characterizing queueing processes and has wide applications, but few works on applying it to 802.11 by far. In this paper, we take one of the first steps to analyze the backlog bounds of an 802.11 wireless LAN using stochastic network calculus. In particular, we want to address its effectiveness on bounding backlogs. We model a wireless node as a single server with impairment service based on two best-known models in stochastic network calculus: Jiang's and Ciucu's. Interestingly, we find that the two models can derive equivalent stochastic service curves and backlog bounds in our studied case. We prove that the network-calculus bounds imply stable backlogs as long as the average rate of traffic arrival is less than that of service, indicating the theoretical effectiveness of stochastic network calculus in bounding backlogs. From A. Kumar's 802.11 model, we derive the concrete stochastic service curve of an 802.11 node and its backlog bounds. We compare the derived bounds with ns-2 simulations and find that the former are very loose and we discuss the reasons. And we show that the martingale and independent case analysis techniques can improve the bounds significantly. Our work offers a good reference to applying stochastic network calculus to practical scenarios.
Detection of Calendar-Based Periodicities of Interval-Based Temporal Patterns
Venue: arXiv cs.DB 2012
Year: 2012

We present a novel technique to identify calendar-based (annual, monthly and daily) periodicities of an interval-based temporal pattern. An interval-based temporal pattern is a pattern that occurs across a time-interval, then disappears for some time, again recurs across another time-interval and so on and so forth. Given the sequence of time-intervals in which an interval-based temporal pattern has occurred, we propose a method for identifying the extent to which the pattern is periodic with respect to a calendar cycle. In comparison to previous work, our method is asymptotically faster. We also show an interesting relationship between periodicities across different levels of any hierarchical timestamp (year/month/day, hour/minute/second etc.).
The Diffusion of Networking Technologies
Venue: arXiv cs.SI 2012
Year: 2012

There has been significant interest in the networking community on the impact of cascade effects on the diffusion of networking technology upgrades in the Internet. Thinking of the global Internet as a graph, where each node represents an economically-motivated Internet Service Provider (ISP), a key problem is to determine the smallest set of nodes that can trigger a cascade that causes every other node in the graph to adopt the protocol. We design the first approximation algorithm with a provable performance guarantee for this problem, in a model that captures the following key issue: a node's decision to upgrade should be influenced by the decisions of the remote nodes it wishes to communicate with. Given an internetwork G(V,E) and threshold function θ, we assume that node $u$ activates (upgrades to the new technology) when it is adjacent to a connected component of active nodes in G of size exceeding node $u$'s threshold θ(u). Our objective is to choose the smallest set of nodes that can cause the rest of the graph to activate. Our main contribution is an approximation algorithm based on linear programming, which we complement with computational hardness results and a near-optimum integrality gap. Our algorithm, which does not rely on submodular optimization techniques, also highlights the substantial algorithmic difference between our problem and similar questions studied in the context of social networks.
Segmentation of Offline Handwritten Bengali Script
Venue: arXiv cs.CV 2012
Year: 2012

Character segmentation has long been one of the most critical areas of optical character recognition process. Through this operation, an image of a sequence of characters, which may be connected in some cases, is decomposed into sub-images of individual alphabetic symbols. In this paper, segmentation of cursive handwritten script of world's fourth popular language, Bengali, is considered. Unlike English script, Bengali handwritten characters and its components often encircle the main character, making the conventional segmentation methodologies inapplicable. Experimental results, using the proposed segmentation technique, on sample cursive handwritten data containing 218 ideal segmentation points show a success rate of 97.7%. Further feature-analysis on these segments may lead to actual recognition of handwritten cursive Bengali script.
Towards minimax policies for online linear optimization with bandit feedback
Venue: arXiv cs.LG 2012
Year: 2012

We address the online linear optimization problem with bandit feedback. Our contribution is twofold. First, we provide an algorithm (based on exponential weights) with a regret of order $\sqrt{d n \log N}$ for any finite action set with $N$ actions, under the assumption that the instantaneous loss is bounded by 1. This shaves off an extraneous $\sqrt{d}$ factor compared to previous works, and gives a regret bound of order $d \sqrt{n \log n}$ for any compact set of actions. Without further assumptions on the action set, this last bound is minimax optimal up to a logarithmic factor. Interestingly, our result also shows that the minimax regret for bandit linear optimization with expert advice in $d$ dimension is the same as for the basic $d$-armed bandit with expert advice. Our second contribution is to show how to use the Mirror Descent algorithm to obtain computationally efficient strategies with minimax optimal regret bounds in specific examples. More precisely we study two canonical action sets: the hypercube and the Euclidean ball. In the former case, we obtain the first computationally efficient algorithm with a $d \sqrt{n}$ regret, thus improving by a factor $\sqrt{d \log n}$ over the best known result for a computationally efficient algorithm. In the latter case, our approach gives the first algorithm with a $\sqrt{d n \log n}$ regret, again shaving off an extraneous $\sqrt{d}$ compared to previous works.
D-iteration based asynchronous distributed computation
Venue: arXiv cs.DC 2012
Year: 2012

The aim of this paper is to explain how the D-iteration can be used for an efficient asynchronous distributed computation. We present the main ideas of the method and illustrate them through very simple examples.
Lambda-lifting and CPS conversion in an imperative language
Venue: arXiv cs.PL 2012
Year: 2012

This paper is a companion technical report to the article "Continuation-Passing C: from threads to events through continuations". It contains the complete version of the proofs of correctness of lambda-lifting and CPS-conversion presented in the article.
Generalized powerlocales via relation lifting
Venue: arXiv cs.LO 2012
Year: 2012

This paper introduces an endofunctor $\VT$ on the category of frames, parametrized by an endofunctor $\T$ on the category $\Set$ that satisfies certain constraints. This generalizes Johnstone's construction of the Vietoris powerlocale, in the sense that his construction is obtained by taking for $\T$ the finite covariant power set functor. Our construction of the $\T$-powerlocale $\VT \bbL$ out of a frame $\bbL$ is based on ideas from coalgebraic logic and makes explicit the connection between the Vietoris construction and Moss's coalgebraic cover modality. We show how to extend certain natural transformations between set functors to natural transformations between $\T$-powerlocale functors. Finally, we prove that the operation $\VT$ preserves some properties of frames, such as regularity, zero-dimensionality, and the combination of zero-dimensionality and compactness.
Attack on Fully Homomorphic Encryption over the Integers
Venue: arXiv cs.CR 2012
Year: 2012

This paper presents a heuristic attack on the fully homomorphic encryption over the integers by using lattice reduction algorithm. Our result shows that the FHE in [DGHV10] is not secure for some parameter settings. We also present an improvement scheme to avoid the lattice attack in this paper.
They Know Where You Live!
Venue: arXiv cs.SI 2012
Year: 2012

In this paper, we demonstrate the possibility of predicting people's hometowns by using their geotagged photos posted on Flickr website. We employ Kruskal's algorithm to cluster photos taken by a user and predict the user's hometown. Our results prove that using social profiles of photographers allows researchers to predict the locations of their taken photos with higher accuracies. This in return can improve the previous methods which were purely based on visual features of photos \cite{Hays:im2gps}.
Recovering Jointly Sparse Signals via Joint Basis Pursuit
Venue: arXiv cs.IT 2012
Year: 2012

This work considers recovery of signals that are sparse over two bases. For instance, a signal might be sparse in both time and frequency, or a matrix can be low rank and sparse simultaneously. To facilitate recovery, we consider minimizing the sum of the $\ell_1$-norms that correspond to each basis, which is a tractable convex approach. We find novel optimality conditions which indicates a gain over traditional approaches where $\ell_1$ minimization is done over only one basis. Next, we analyze these optimality conditions for the particular case of time-frequency bases. Denoting sparsity in the first and second bases by $k_1,k_2$ respectively, we show that, for a general class of signals, using this approach, one requires as small as $O(\max\{k_1,k_2\}\log\log n)$ measurements for successful recovery hence overcoming the classical requirement of $Θ(\min\{k_1,k_2\}\log(\frac{n}{\min\{k_1,k_2\}}))$ for $\ell_1$ minimization when $k_1\approx k_2$. Extensive simulations show that, our analysis is approximately tight.
On Directly Mapping Relational Databases to RDF and OWL (Extended Version)
Venue: arXiv cs.DB 2012
Year: 2012

Mapping relational databases to RDF is a fundamental problem for the development of the Semantic Web. We present a solution, inspired by draft methods defined by the W3C where relational databases are directly mapped to RDF and OWL. Given a relational database schema and its integrity constraints, this direct mapping produces an OWL ontology, which, provides the basis for generating RDF instances. The semantics of this mapping is defined using Datalog. Two fundamental properties are information preservation and query preservation. We prove that our mapping satisfies both conditions, even for relational databases that contain null values. We also consider two desirable properties: monotonicity and semantics preservation. We prove that our mapping is monotone and also prove that no monotone mapping, including ours, is semantic preserving. We realize that monotonicity is an obstacle for semantic preservation and thus present a non-monotone direct mapping that is semantics preserving.
Filtered Fictitious Play for Perturbed Observation Potential Games and Decentralised POMDPs
Venue: arXiv cs.GT 2012
Year: 2012

Potential games and decentralised partially observable MDPs (Dec-POMDPs) are two commonly used models of multi-agent interaction, for static optimisation and sequential decisionmaking settings, respectively. In this paper we introduce filtered fictitious play for solving repeated potential games in which each player's observations of others' actions are perturbed by random noise, and use this algorithm to construct an online learning method for solving Dec-POMDPs. Specifically, we prove that noise in observations prevents standard fictitious play from converging to Nash equilibrium in potential games, which also makes fictitious play impractical for solving Dec-POMDPs. To combat this, we derive filtered fictitious play, and provide conditions under which it converges to a Nash equilibrium in potential games with noisy observations. We then use filtered fictitious play to construct a solver for Dec-POMDPs, and demonstrate our new algorithm's performance in a box pushing problem. Our results show that we consistently outperform the state-of-the-art Dec-POMDP solver by an average of 100% across the range of noise in the observation function.