OpenRaiser/Intern-Atlas huggingface dataset:
On Constant Gaps for the Two-way Gaussian Interference Channel
Venue: arXiv cs.IT 2012
Year: 2012

We introduce the two-way Gaussian interference channel in which there are four nodes with four independent messages: two-messages to be transmitted over a Gaussian interference channel in the $\rightarrow$ direction, simultaneously with two-messages to be transmitted over an interference channel (in-band, full-duplex) in the $\leftarrow$ direction. In such a two-way network, all nodes are transmitters and receivers of messages, allowing them to adapt current channel inputs to previously received channel outputs. We propose two new outer bounds on the symmetric sum-rate for the two-way Gaussian interference channel with complex channel gains: one under full adaptation (all 4 nodes are permitted to adapt inputs to previous outputs), and one under partial adaptation (only 2 nodes are permitted to adapt, the other 2 are restricted). We show that simple non-adaptive schemes such as the Han and Kobayashi scheme, where inputs are functions of messages only and not past outputs, utilized in each direction are sufficient to achieve within a constant gap of these fully or partially adaptive outer bounds for all channel regimes.
Multi-frame Signature-cum Anomaly-based Intrusion Detection Systems (MSAIDS) to Protect Privacy of Users over Mobile Collaborative Learning (MCL)
Venue: arXiv cs.CR 2012
Year: 2012

The rogue DHCP is unauthorized server that releases the incorrect IP address to users and sniffs the traffic illegally. The contribution specially provides privacy to users and enhances the security aspects of mobile supported collaborative framework (MSCF) explained in [24].The paper introduces multi-frame signature-cum anomaly-based intrusion detection systems (MSAIDS) supported with novel algorithms and inclusion of new rules in existing IDS. The major target of contribution is to detect the malicious attacks and blocks the illegal activities of rogue DHCP server. This innovative security mechanism reinforces the confidence of users, protects network from illicit intervention and restore the privacy of users. Finally, the paper validates the idea through simulation and compares the findings with known existing techniques.
Network Compression: Memory-Assisted Universal Coding of Sources with Correlated Parameters
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose {\em distributed network compression via memory}. We consider two spatially separated sources with correlated unknown source parameters. We wish to study the universal compression of a sequence of length $n$ from one of the sources provided that the decoder has access to (i.e., memorized) a sequence of length $m$ from the other source. In this setup, the correlation does not arise from symbol-by-symbol dependency of two outputs from the two sources (as in Slepian-Wolf setup). Instead, the two sequences are correlated because they are originated from the two sources with \emph{unknown} correlated parameters. The finite-length nature of the compression problem at hand requires considering a notion of almost lossless source coding, where coding incurs an error probability $p_e(n)$ that vanishes as sequence length $n$ grows to infinity. We obtain bounds on the redundancy of almost lossless codes when the decoder has access to a random memory of length $m$ as a function of the sequence length $n$ and the permissible error probability $p_e(n)$. Our results demonstrate that distributed network compression via memory has the potential to significantly improve over conventional end-to-end compression when sufficiently large memory from previous communications is available to the decoder.
Diagrammatic confluence for Constraint Handling Rules
Venue: arXiv cs.PL 2012
Year: 2012

Confluence is a fundamental property of Constraint Handling Rules (CHR) since, as in other rewriting formalisms, it guarantees that the computations are not dependent on rule application order, and also because it implies the logical consistency of the program declarative view. In this paper we are concerned with proving the confluence of non-terminating CHR programs. For this purpose, we derive from van Oostrom's decreasing diagrams method a novel criterion on CHR critical pairs that generalizes all preexisting criteria. We subsequently improve on a result on the modularity of CHR confluence, which permits modular combinations of possibly non-terminating confluent programs, without loss of confluence.
Mining Permission Request Patterns from Android and Facebook Applications (extended author version)
Venue: arXiv cs.CR 2012
Year: 2012

Android and Facebook provide third-party applications with access to users' private data and the ability to perform potentially sensitive operations (e.g., post to a user's wall or place phone calls). As a security measure, these platforms restrict applications' privileges with permission systems: users must approve the permissions requested by applications before the applications can make privacy- or security-relevant API calls. However, recent studies have shown that users often do not understand permission requests and lack a notion of typicality of requests. As a first step towards simplifying permission systems, we cluster a corpus of 188,389 Android applications and 27,029 Facebook applications to find patterns in permission requests. Using a method for Boolean matrix factorization for finding overlapping clusters, we find that Facebook permission requests follow a clear structure that exhibits high stability when fitted with only five clusters, whereas Android applications demonstrate more complex permission requests. We also find that low-reputation applications often deviate from the permission request patterns that we identified for high-reputation applications suggesting that permission request patterns are indicative for user satisfaction or application quality.
Modelling Implicit Communication in Multi-Agent Systems with Hybrid Input/Output Automata
Venue: arXiv cs.FL 2012
Year: 2012

We propose an extension of Hybrid I/O Automata (HIOAs) to model agent systems and their implicit communication through perturbation of the environment, like localization of objects or radio signals diffusion and detection. To this end we decided to specialize some variables of the HIOAs whose values are functions both of time and space. We call them world variables. Basically they are treated similarly to the other variables of HIOAs, but they have the function of representing the interaction of each automaton with the surrounding environment, hence they can be output, input or internal variables. Since these special variables have the role of simulating implicit communication, their dynamics are specified both in time and space, because they model the perturbations induced by the agent to the environment, and the perturbations of the environment as perceived by the agent. Parallel composition of world variables is slightly different from parallel composition of the other variables, since their signals are summed. The theory is illustrated through a simple example of agents systems.
Automata-based Static Analysis of XML Document Adaptation
Venue: arXiv cs.DB 2012
Year: 2012

The structure of an XML document can be optionally specified by means of XML Schema, thus enabling the exploitation of structural information for efficient document handling. Upon schema evolution, or when exchanging documents among different collections exploiting related but not identical schemas, the need may arise of adapting a document, known to be valid for a given schema S, to a target schema S'. The adaptation may require knowledge of the element semantics and cannot always be automatically derived. In this paper, we present an automata-based method for the static analysis of user-defined XML document adaptations, expressed as sequences of XQuery Update update primitives. The key feature of the method is the use of an automatic inference method for extracting the type, expressed as a Hedge Automaton, of a sequence of document updates. The type is computed starting from the original schema S and from rewriting rules that formally define the operational semantics of a sequence of document updates. Type inclusion can then be used as conformance test w.r.t. the type extracted from the target schema S'.
A Myhill-Nerode theorem for automata with advice
Venue: arXiv cs.FL 2012
Year: 2012

An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.
Satisfiability vs. Finite Satisfiability in Elementary Modal Logics
Venue: arXiv cs.LO 2012
Year: 2012

We study elementary modal logics, i.e. modal logic considered over first-order definable classes of frames. The classical semantics of modal logic allows infinite structures, but often practical applications require to restrict our attention to finite structures. Many decidability and undecidability results for the elementary modal logics were proved separately for general satisfiability and for finite satisfiability [11, 12, 16, 17]. In this paper, we show that there is a reason why we must deal with both kinds of satisfiability separately -- we prove that there is a universal first-order formula that defines an elementary modal logic with decidable (global) satisfiability problem, but undecidable finite satisfiability problem, and, the other way round, that there is a universal formula that defines an elementary modal logic with decidable finite satisfiability problem, but undecidable general satisfiability problem.
Comparison of Certificate Policies for Merging Public Key Infrastructures during Merger and Acquisition of Companies
Venue: arXiv cs.CR 2012
Year: 2012

The Public Key Infrastructure(PKI) provides facilities for data encryption, digital signature and time stamping. It is a system where different authorities verify and authenticate the validity of each participant with the use of digital certificates. A Certificate Policy (CP) is a named set of rules and it indicates the applicability of a certificate in a Public Key Infrastructure. Sometimes two companies or organizations with different PKIs merge. Therefore it would be necessary that their PKIs are also able to merge. Sometimes, the unification of different PKIs is not possible because of the different certificate policies. This paper presents a method to compare and assess certificate policies during merger and acquisition of companies.
A review on routing protocols for application in wireless sensor networks
Venue: arXiv cs.NI 2012
Year: 2012

Wireless sensor networks are harshly restricted by storage capacity, energy and computing power. So it is essential to design effective and energy aware protocol in order to enhance the network lifetime. In this paper, a review on routing protocol in WSNs is carried out which are classified as data-centric, hierarchical and location based depending on the network structure. Then some of the multipath routing protocols which are widely used in WSNs to improve network performance are also discussed. Advantages and disadvantages of each routing algorithm are discussed thereafter. Furthermore, this paper compares and summarizes the performances of routing protocols.
On Walsh code assignment
Venue: arXiv cs.IT 2012
Year: 2012

The paper considers the problem of orthogonal variable spreading Walsh-code assignments. The aim of the paper is to provide assignments that can avoid both complicated signaling from the BS to the users and blind rate and code detection amongst a great number of possible codes. The assignments considered here use a partition of all users into several pools. Each pool can use its own codes that are different for different pools. Each user has only a few codes assigned to it within the pool. We state the problem as a combinatorial one expressed in terms of a binary n x k matrix M where is the number n of users, and k is the number of Walsh codes in the pool. A solution to the problem is given as a construction of M, which has the assignment property defined in the paper. Two constructions of such M are presented under different conditions on n and k. The first construction is optimal in the sense that it gives the minimal number of Walsh codes assigned to each user for given n and k. The optimality follows from a proved necessary condition for the existence of M with the assignment property. In addition, we propose a simple algorithm of optimal assignment for the first construction.
Multi-threaded ASP Solving with clasp
Venue: arXiv cs.LO 2012
Year: 2012

We present the new multi-threaded version of the state-of-the-art answer set solver clasp. We detail its component and communication architecture and illustrate how they support the principal functionalities of clasp. Also, we provide some insights into the data representation used for different constraint types handled by clasp. All this is accompanied by an extensive experimental analysis of the major features related to multi-threading in clasp.
Enhanced Compressed Sensing Recovery with Level Set Normals
Venue: arXiv cs.CV 2012
Year: 2012

We propose a compressive sensing algorithm that exploits geometric properties of images to recover images of high quality from few measurements. The image reconstruction is done by iterating the two following steps: 1) estimation of normal vectors of the image level curves and 2) reconstruction of an image fitting the normal vectors, the compressed sensing measurements and the sparsity constraint. The proposed technique can naturally extend to non local operators and graphs to exploit the repetitive nature of textured images in order to recover fine detail structures. In both cases, the problem is reduced to a series of convex minimization problems that can be efficiently solved with a combination of variable splitting and augmented Lagrangian methods, leading to fast and easy-to-code algorithms. Extended experiments show a clear improvement over related state-of-the-art algorithms in the quality of the reconstructed images and the robustness of the proposed method to noise, different kind of images and reduced measurements.
An Agent-based framework for cooperation in Supply Chain
Venue: arXiv cs.AI 2012
Year: 2012

Supply Chain coordination has become a critical success factor for Supply Chain management (SCM) and effectively improving the performance of organizations in various industries. Companies are increasingly located at the intersection of one or more corporate networks which are designated by "Supply Chain". Managing this chain is mainly based on an 'information sharing' and redeployment activities between the various links that comprise it. Several attempts have been made by industrialists and researchers to educate policymakers about the gains to be made by the implementation of cooperative relationships. The approach presented in this paper here is among the works that aim to propose solutions related to information systems distributed Supply Chains to enable the different actors of the chain to improve their performance. We propose in particular solutions that focus on cooperation between actors in the Supply Chain.
On Multi-rate Sequential Data Transmission
Venue: arXiv cs.IT 2012
Year: 2012

In this report, we investigate the data transmission model in which a sequence of data is broadcasted to a number of receivers. The receivers, which have different channel capacities, wish to decode the data sequentially at different rates. Our results are applicable to a wide range of scenarios. For instance, it can be employed in the broadcast streaming of a video clip through the internet, so that receivers with different bandwidths can play the video at different speed. Receivers with greater bandwidths can provide a smooth playback, while receivers with smaller bandwidths can play the video at a slower speed, or with short pauses or rebuffering.
Stochastic Surveillance Strategies for Spatial Quickest Detection
Venue: arXiv cs.RO 2012
Year: 2012

We design persistent surveillance strategies for the quickest detection of anomalies taking place in an environment of interest. From a set of predefined regions in the environment, a team of autonomous vehicles collects noisy observations, which a control center processes. The overall objective is to minimize detection delay while maintaining the false alarm rate below a desired threshold. We present joint (i) anomaly detection algorithms for the control center and (ii) vehicle routing policies. For the control center, we propose parallel cumulative sum (CUSUM) algorithms (one for each region) to detect anomalies from noisy observations. For the vehicles, we propose a stochastic routing policy, in which the regions to be visited are chosen according to a probability vector. We study stationary routing policy (the probability vector is constant) as well as adaptive routing policies (the probability vector varies in time as a function of the likelihood of regional anomalies). In the context of stationary policies, we design a performance metric and minimize it to design an efficient stationary routing policy. Our adaptive policy improves upon the stationary counterpart by adaptively increasing the selection probability of regions with high likelihood of anomaly. Finally, we show the effectiveness of the proposed algorithms through numerical simulations and a persistent surveillance experiment.
Decidability of All Minimal Models (Revised Version - 2012)
Venue: arXiv cs.LO 2012
Year: 2012

This unpublished note is an alternate, shorter (and hopefully more readable) proof of the decidability of all minimal models. The decidability follows from a proof of the existence of a cellular term in each observational equivalence class of a minimal model.
Optimal Power Allocation Policy over Two Identical Gilbert-Elliott Channels
Venue: arXiv cs.IT 2012
Year: 2012

We study the fundamental problem of optimal power allocation over two identical Gilbert-Elliott (Binary Markov) communication channels. Our goal is to maximize the expected discounted number of bits transmitted over an infinite time span by judiciously choosing one of the four actions for each time slot: 1) allocating power equally to both channels, 2) allocating all the power to channel 1, 3) allocating all the power to channel 2, and 4) allocating no power to any of the channels. As the channel state is unknown when power allocation decision is made, we model this problem as a partially observable Markov decision process(POMDP), and derive the optimal policy which gives the optimal action to take under different possible channel states. Two different structures of the optimal policy are derived analytically and verified by linear programming simulation. We also illustrate how to construct the optimal policy by the combination of threshold calculation and linear programming simulation once system parameters are known.
On the Analysis of a Label Propagation Algorithm for Community Detection
Venue: arXiv cs.DC 2012
Year: 2012

This paper initiates formal analysis of a simple, distributed algorithm for community detection on networks. We analyze an algorithm that we call \textsc{Max-LPA}, both in terms of its convergence time and in terms of the "quality" of the communities detected. \textsc{Max-LPA} is an instance of a class of community detection algorithms called \textit{label propagation} algorithms. As far as we know, most analysis of label propagation algorithms thus far has been empirical in nature and in this paper we seek a theoretical understanding of label propagation algorithms. In our main result, we define a clustered version of \er random graphs with clusters $V_1, V_2,..., V_k$ where the probability $p$, of an edge connecting nodes within a cluster $V_i$ is higher than $p'$, the probability of an edge connecting nodes in distinct clusters. We show that even with fairly general restrictions on $p$ and $p'$ ($p = Ω(\frac{1}{n^{1/4-ε}})$ for any $ε> 0$, $p' = O(p^2)$, where $n$ is the number of nodes), \textsc{Max-LPA} detects the clusters $V_1, V_2,..., V_n$ in just two rounds. Based on this and on empirical results, we conjecture that \textsc{Max-LPA} can correctly and quickly identify communities on clustered \er graphs even when the clusters are much sparser, i.e., with $p = \frac{c\log n}{n}$ for some $c > 1$.
A Conceptual Framework to Analyze Enterprise Business Solutions from a Software Architecture Perspective
Venue: arXiv cs.SE 2012
Year: 2012

The architectural aspects of software systems are not always explicitly exposed to customers when a product is presented to them by software vendors. Therefore, customers might be put at a major risk if new emerging business needs come to light that require modification of some of the core business processes within their organizations. So they might need to replace their existing systems or re-architect old ones to comply with new architectural standards. This paper describes a proposed framework that helps organizations to build a comprehensive view of their system architecture prior to dealing with vendors. Consequently, every organization can have a reference model that facilitates negotiation and communication with software vendors. The paper applies the proposed framework to an organization in the region of Saudi Arabia to validate its applicability and generates an architectural design for their software systems.
Learning Attitudes and Attributes from Multi-Aspect Reviews
Venue: arXiv cs.CL 2012
Year: 2012

The majority of online reviews consist of plain-text feedback together with a single numeric score. However, there are multiple dimensions to products and opinions, and understanding the `aspects' that contribute to users' ratings may help us to better understand their individual preferences. For example, a user's impression of an audiobook presumably depends on aspects such as the story and the narrator, and knowing their opinions on these aspects may help us to recommend better products. In this paper, we build models for rating systems in which such dimensions are explicit, in the sense that users leave separate ratings for each aspect of a product. By introducing new corpora consisting of five million reviews, rated with between three and six aspects, we evaluate our models on three prediction tasks: First, we use our model to uncover which parts of a review discuss which of the rated aspects. Second, we use our model to summarize reviews, which for us means finding the sentences that best explain a user's rating. Finally, since aspect ratings are optional in many of the datasets we consider, we use our model to recover those ratings that are missing from a user's evaluation. Our model matches state-of-the-art approaches on existing small-scale datasets, while scaling to the real-world datasets we introduce. Moreover, our model is able to `disentangle' content and sentiment words: we automatically learn content words that are indicative of a particular aspect as well as the aspect-specific sentiment words that are indicative of a particular rating.
Introduction to the 28th International Conference on Logic Programming Special Issue
Venue: arXiv cs.PL 2012
Year: 2012

We are proud to introduce this special issue of the Journal of Theory and Practice of Logic Programming (TPLP), dedicated to the full papers accepted for the 28th International Conference on Logic Programming (ICLP). The ICLP meetings started in Marseille in 1982 and since then constitute the main venue for presenting and discussing work in the area of logic programming.