OpenRaiser/Intern-Atlas huggingface dataset:
Unlocking Blocked Communicating Processes
Venue: arXiv cs.PL 2015
Year: 2015

We study the problem of disentangling locked processes via code refactoring. We identify and characterise a class of processes that is not lock-free; then we formalise an algorithm that statically detects potential locks and propose refactoring procedures that disentangle detected locks. Our development is cast within a simple setting of a finite linear CCS variant â although it suffices to illustrate the main concepts, we also discuss how our work extends to other language extensions.
On Properties of Policy-Based Specifications
Venue: arXiv cs.SE 2015
Year: 2015

The advent of large-scale, complex computing systems has dramatically increased the difficulties of securing accesses to systems' resources. To ensure confidentiality and integrity, the exploitation of access control mechanisms has thus become a crucial issue in the design of modern computing systems. Among the different access control approaches proposed in the last decades, the policy-based one permits to capture, by resorting to the concept of attribute, all systems' security-relevant information and to be, at the same time, sufficiently flexible and expressive to represent the other approaches. In this paper, we move a step further to understand the effectiveness of policy-based specifications by studying how they permit to enforce traditional security properties. To support system designers in developing and maintaining policy-based specifications, we formalise also some relevant properties regarding the structure of policies. By means of a case study from the banking domain, we present real instances of such properties and outline an approach towards their automatised verification.
Semantics-based Automated Web Testing
Venue: arXiv cs.SE 2015
Year: 2015

We present TAO, a software testing tool performing automated test and oracle generation based on a semantic approach. TAO entangles grammar-based test generation with automated semantics evaluation using a denotational semantics framework. We show how TAO can be incorporated with the Selenium automation tool for automated web testing, and how TAO can be further extended to support automated delta debugging, where a failing web test script can be systematically reduced based on grammar-directed strategies. A real-life parking website is adopted throughout the paper to demonstrate the effectivity of our semantics-based web testing approach.
In Quest of Significance: Identifying Types of Twitter Sentiment Events that Predict Spikes in Sales
Venue: arXiv cs.SI 2015
Year: 2015

We study the power of Twitter events to predict consumer sales events by analysing sales for 75 companies from the retail sector and over 150 million tweets mentioning those companies along with their sentiment. We suggest an approach for events identification on Twitter extending existing methodologies of event study. We also propose a robust method for clustering Twitter events into different types based on their shape, which captures the varying dynamics of information propagation through the social network. We provide empirical evidence that through events differentiation based on their shape we can clearly identify types of Twitter events that have a more significant power to predict spikes in sales than the aggregated Twitter signal.
Locality-preserving allocations Problems and coloured Bin Packing
Venue: arXiv cs.DS 2015
Year: 2015

We study the following problem, introduced by Chung et al. in 2006. We are given, online or offline, a set of coloured items of different sizes, and wish to pack them into bins of equal size so that we use few bins in total (at most $α$ times optimal), and that the items of each colour span few bins (at most $β$ times optimal). We call such allocations $(α, β)$-approximate. As usual in bin packing problems, we allow additive constants and consider $(α,β)$ as the asymptotic performance ratios. We prove that for $\eps>0$, if we desire small $α$, no scheme can beat $(1+\eps, Ω(1/\eps))$-approximate allocations and similarly as we desire small $β$, no scheme can beat $(1.69103, 1+\eps)$-approximate allocations. We give offline schemes that come very close to achieving these lower bounds. For the online case, we prove that no scheme can even achieve $(O(1),O(1))$-approximate allocations. However, a small restriction on item sizes permits a simple online scheme that computes $(2+\eps, 1.7)$-approximate allocations.
Entropy bounds on abelian groups and the Ruzsa divergence
Venue: arXiv cs.IT 2015
Year: 2015

Over the past few years, a family of interesting new inequalities for the entropies of sums and differences of random variables has been developed by Ruzsa, Tao and others, motivated by analogous results in additive combinatorics. The present work extends these earlier results to the case of random variables taking values in $\mathbb{R}^n$ or, more generally, in arbitrary locally compact and Polish abelian groups. We isolate and study a key quantity, the Ruzsa divergence between two probability distributions, and we show that its properties can be used to extend the earlier inequalities to the present general setting. The new results established include several variations on the theme that the entropies of the sum and the difference of two independent random variables severely constrain each other. Although the setting is quite general, the result are already of interest (and new) for random vectors in $\mathbb{R}^n$. In that special case, quantitative bounds are provided for the stability of the equality conditions in the entropy power inequality; a reverse entropy power inequality for log-concave random vectors is proved; an information-theoretic analog of the Rogers-Shephard inequality for convex bodies is established; and it is observed that some of these results lead to new inequalities for the determinants of positive-definite matrices. Moreover, by considering the multiplicative subgroups of the complex plane, one obtains new inequalities for the differential entropies of products and ratios of nonzero, complex-valued random variables.
Action Recognition based on Subdivision-Fusion Model
Venue: arXiv cs.CV 2015
Year: 2015

This paper proposes a novel Subdivision-Fusion Model (SFM) to recognize human actions. In most action recognition tasks, overlapping feature distribution is a common problem leading to overfitting. In the subdivision stage of the proposed SFM, samples in each category are clustered. Then, such samples are grouped into multiple more concentrated subcategories. Boundaries for the subcategories are easier to find and as consequence overfitting is avoided. In the subsequent fusion stage, the multi-subcategories classification results are converted back to the original category recognition problem. Two methods to determine the number of clusters are provided. The proposed model has been thoroughly tested with four popular datasets. In the Hollywood2 dataset, an accuracy of 79.4% is achieved, outperforming the state-of-the-art accuracy of 64.3%. The performance on the YouTube Action dataset has been improved from 75.8% to 82.5%, while considerably improvements are also observed on the KTH and UCF50 datasets.
Coordinated Shared Spectrum Precoding with Distributed CSIT
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, the operation of a Licensed Shared Access (LSA) system is investigated, considering downlink communication. The system comprises of a Multiple-Input-Single-Output (MISO) incumbent transmitter (TX) - receiver (RX) pair, which offers a spectrum sharing opportunity to a MISO licensee TX-RX pair. Our main contribution is the design of a coordinated transmission scheme, inspired by the underlay Cognitive Radio (CR) approach, with the aim of maximizing the average rate of the licensee, subject to an average rate constraint for the incumbent. In contrast to most prior works on underlay CR, the coordination of the two TXs takes place under a realistic Channel State Information (CSI) scenario, where each TX has sole access to the instantaneous direct channel of its served terminal. Such a CSI knowledge setting brings about a formulation based on the theory of Team Decisions, whereby the TXs aim at optimizing a common objective given the same constraint set, on the basis of individual channel information. Consequently, a novel set of applicable precoding schemes is proposed. Relying on statistical coordination criteria, the two TXs cooperate in the lack of any instantaneous CSI exchange. We verify by simulations that our novel coordinated precoding scheme outperforms the standard underlay CR approach.
Stabilization of discrete-time piecewise affine systems with quantized signals
Venue: arXiv cs.SY 2015
Year: 2015

This paper studies quantized control for discrete-time piecewise affine systems. For given stabilizing feedback controllers, we propose an encoding strategy for local stability. If the quantized state is near the boundaries of quantization regions, then the controller can recompute a better quantization value. For the design of quantized feedback controllers, we also consider the stabilization of piecewise affine systems with bounded disturbances. In order to derive a less conservative design method with low computational cost, we investigate a region to which the state belong in the next step.
Topological representation of intuitionistic and distributive abstract logics
Venue: arXiv cs.LO 2015
Year: 2015

We continue work of our earlier paper (Lewitzka and Brunner: Minimally generated abstract logics, Logica Universalis 3(2), 2009), where abstract logics and particularly intuitionistic abstract logics are studied. Abstract logics can be topologized in a direct and natural way. This facilitates a topological study of classes of concrete logics whenever they are given in abstract form. Moreover, such a direct topological approach avoids the often complex algebraic and lattice-theoretic machinery usually applied to represent logics. Motivated by that point of view, we define in this paper the category of intuitionistic abstract logics with stable logic maps as morphisms, and the category of implicative spectral spaces with spectral maps as morphisms. We show the equivalence of these categories and conclude that the larger categories of distributive abstract logics and distributive sober spaces are equivalent, too.
Generation of Synthetic Spatially Embedded Power Grid Networks
Venue: arXiv cs.SY 2015
Year: 2015

The development of algorithms for enhancing the resilience and efficiency of the power grid requires performance evaluation with real topologies of power transmission networks. However, due to security reasons, such topologies and particularly the locations of the substations and the lines are usually not publicly available. Therefore, we study the structural properties of the North American grids and present an algorithm for generating synthetic spatially embedded networks with similar properties to a given grid. The algorithm uses the Gaussian Mixture Model (GMM) for density estimation of the node positions and generates a set of nodes with similar spatial distribution to the nodes in a given network. Then, it uses two procedures, which are inspired by the historical evolution of the grids, to connect the nodes. The algorithm has several tunable parameters that allow generating grids similar to any given grid. Particularly, we apply it to the Western Interconnection (WI) and to grids that operate under the SERC Reliability Corporation (SERC) and the Florida Reliability Coordinating Council (FRCC), and show that it generates grids with similar structural and spatial properties to these grids. To the best of our knowledge, this is the first attempt to consider the spatial distribution of the nodes and lines and its importance in generating synthetic power grids.
Multiresolution Approach to Acceleration of Iterative Image Reconstruction for X-Ray Imaging for Security Applications
Venue: arXiv cs.CV 2015
Year: 2015

Three-dimensional x-ray CT image reconstruction in baggage scanning in security applications is an important research field. The variety of materials to be reconstructed is broader than medical x-ray imaging. Presence of high attenuating materials such as metal may cause artifacts if analytical reconstruction methods are used. Statistical modeling and the resultant iterative algorithms are known to reduce these artifacts and present good quantitative accuracy in estimates of linear attenuation coefficients. However, iterative algorithms may require computations in order to achieve quantitatively accurate results. For the case of baggage scanning, in order to provide fast accurate inspection throughput, they must be accelerated drastically. There are many approaches proposed in the literature to increase speed of convergence. This paper presents a new method that estimates the wavelet coefficients of the images in the discrete wavelet transform domain instead of the image space itself. Initially, surrogate functions are created around approximation coefficients only. As the iterations proceed, the wavelet tree on which the updates are made is expanded based on a criterion and detail coefficients at each level are updated and the tree is expanded this way. For example, in the smooth regions of the image the detail coefficients are not updated while the coefficients that represent the high-frequency component around edges are being updated, thus saving time by focusing computations where they are needed. This approach is implemented on real data from a SureScan (TM) x1000 Explosive Detection System and compared to straightforward implementation of the unregularized alternating minimization of O'Sullivan and Benac [1].
On Designing and Testing Distributed Virtual Environments
Venue: arXiv cs.SE 2015
Year: 2015

Distributed Real-Time (DRT) systems are among the most complex software systems to design, test, maintain and evolve. The existence of components distributed over a network often conflicts with real-time requirements, leading to design strategies that depend on domain- and even application-specific knowledge. Distributed Virtual Environment (DVE) systems are DRT systems that connect multiple users instantly with each other and with a shared virtual space over a network. DVE systems deviate from traditional DRT systems in the importance of the quality of the end user experience. We present an analysis of important, but challenging, issues in the design, testing and evaluation of DVE systems through the lens of experiments with a concrete DVE, OpenSimulator. We frame our observations within six dimensions of well-known design concerns: correctness, fault tolerance/prevention, scalability, time sensitivity, consistency, and overhead of distribution. Furthermore, we place our experimental work in a broader historical context, showing that these challenges are intrinsic to DVEs and suggesting lines of future research.
Introduction to Cross-Entropy Clustering The R Package CEC
Venue: arXiv cs.LG 2015
Year: 2015

The R Package CEC performs clustering based on the cross-entropy clustering (CEC) method, which was recently developed with the use of information theory. The main advantage of CEC is that it combines the speed and simplicity of $k$-means with the ability to use various Gaussian mixture models and reduce unnecessary clusters. In this work we present a practical tutorial to CEC based on the R Package CEC. Functions are provided to encompass the whole process of clustering.
A note on the avoidability of binary patterns with variables and reversals
Venue: arXiv cs.FL 2015
Year: 2015

In this note we present a characterisation of all unary and binary patterns that do not only contain variables, but also reversals of their instances. These types of variables were studied recently in either more general or particular cases. We show that the results are not surprising at all in the general case, and extend the avoidability of these patterns to enforce aperiodic words.
A Lower Bound on the per Soliton Capacity of the Nonlinear Optical Fibre Channel
Venue: arXiv cs.IT 2015
Year: 2015

A closed-form expression for a lower bound on the per soliton capacity of the nonlinear optical fibre channel in the presence of (optical) amplifier spontaneous emission (ASE) noise is derived. This bound is based on a non-Gaussian conditional probability density function for the soliton amplitude jitter induced by the ASE noise and is proven to grow logarithmically as the signal-to-noise ratio increases.
Fault Diagnosis of Helical Gear Box using Large Margin K-Nearest Neighbors Classifier using Sound Signals
Venue: arXiv cs.LG 2015
Year: 2015

Gear drives are one of the most widely used transmission system in many machinery. Sound signals of a rotating machine contain the dynamic information about its health conditions. Not much information available in the literature reporting suitability of sound signals for fault diagnosis applications. Maximum numbers of literature are based on FFT (Fast Fourier Transform) analysis and have its own limitations with non-stationary signals like the ones from gears. In this paper, attempt has been made in using sound signals acquired from gears in good and simulated faulty conditions for the purpose of fault diagnosis through a machine learning approach. The descriptive statistical features were extracted from the acquired sound signals and the predominant features were selected using J48 decision tree technique. The selected features were then used for classification using Large Margin K-nearest neighbor approach. The paper also discusses the effect of various parameters on classification accuracy.
Who are the Devils Wearing Prada in New York City?
Venue: arXiv cs.CV 2015
Year: 2015

Fashion is a perpetual topic in human social life, and the mass has the penchant to emulate what large city residents and celebrities wear. Undeniably, New York City is such a bellwether large city with all kinds of fashion leadership. Consequently, to study what the fashion trends are during this year, it is very helpful to learn the fashion trends of New York City. Discovering fashion trends in New York City could boost many applications such as clothing recommendation and advertising. Does the fashion trend in the New York Fashion Show actually influence the clothing styles on the public? To answer this question, we design a novel system that consists of three major components: (1) constructing a large dataset from the New York Fashion Shows and New York street chic in order to understand the likely clothing fashion trends in New York, (2) utilizing a learning-based approach to discover fashion attributes as the representative characteristics of fashion trends, and (3) comparing the analysis results from the New York Fashion Shows and street-chic images to verify whether the fashion shows have actual influence on the people in New York City. Through the preliminary experiments over a large clothing dataset, we demonstrate the effectiveness of our proposed system, and obtain useful insights on fashion trends and fashion influence.
Analysis of Petri Nets and Transition Systems
Venue: arXiv cs.LO 2015
Year: 2015

This paper describes a stand-alone, no-frills tool supporting the analysis of (labelled) place/transition Petri nets and the synthesis of labelled transition systems into Petri nets. It is implemented as a collection of independent, dedicated algorithms which have been designed to operate modularly, portably, extensibly, and efficiently.
The LTS WorkBench
Venue: arXiv cs.LO 2015
Year: 2015

Labelled Transition Systems (LTSs) are a fundamental semantic model in many areas of informatics, especially concurrency theory. Yet, reasoning on LTSs and relations between their states can be difficult and elusive: very simple process algebra terms can give rise to a large (possibly infinite) number of intricate transitions and interactions. To ease this kind of study, we present LTSwb, a flexible and extensible LTS toolbox: this tutorial paper discusses its design and functionalities.
Difference Constraints: An adequate Abstraction for Complexity Analysis of Imperative Programs
Venue: arXiv cs.PL 2015
Year: 2015

Difference constraints have been used for termination analysis in the literature, where they denote relational inequalities of the form x' <= y + c, and describe that the value of x in the current state is at most the value of y in the previous state plus some integer constant c. In this paper, we argue that the complexity of imperative programs typically arises from counter increments and resets, which can be modeled naturally by difference constraints. We present the first practical algorithm for the analysis of difference constraint programs and describe how C programs can be abstracted to difference constraint programs. Our approach contributes to the field of automated complexity and (resource) bound analysis by enabling automated amortized complexity analysis for a new class of programs and providing a conceptually simple program model that relates invariant- and bound analysis. We demonstrate the effectiveness of our approach through a thorough experimental comparison on real world C code: our tool Loopus computes the complexity for considerably more functions in less time than related tools from the literature.
InstaCluster: Building A Big Data Cluster in Minutes
Venue: arXiv cs.DC 2015
Year: 2015

Deploying, configuring, and managing large clusters is very a demanding and cumbersome task due to the complexity of such systems and the variety of skills needed. One needs to perform low-level configuration of the cluster nodes to ensure their interoperability and connectivity, as well as install, configure and provision the needed services. In this paper we address this problem and demonstrate how to build a Big Data analytic platform on Amazon EC2 in a matter of minutes. Moreover, to use our tool, embedded into a public Amazon Machine Image, the user does not need to be an expert in system administration or Big Data service configuration. Our tool dramatically reduces the time needed to provision clusters, as well as the cost of the infrastructure. Researchers enjoy an additional benefit of having a simple way to specify the experimental environments they use, so that their experiments can be easily reproduced by anyone using our tool.
Opinion Dynamics in Social Networks with Hostile Camps: Consensus vs. Polarization
Venue: arXiv cs.SY 2015
Year: 2015

Most of the distributed protocols for multi-agent consensus assume that the agents are mutually cooperative and "trustful," and so the couplings among the agents bring the values of their states closer. Opinion dynamics in social groups, however, require beyond these conventional models due to ubiquitous competition and distrust between some pairs of agents, which are usually characterized by repulsive couplings and may lead to clustering of the opinions. A simple yet insightful model of opinion dynamics with both attractive and repulsive couplings was proposed recently by C. Altafini, who examined first-order consensus algorithms over static signed graphs. This protocol establishes modulus consensus, where the opinions become the same in modulus but may differ in signs. In this paper, we extend the modulus consensus model to the case where the network topology is an arbitrary time-varying signed graph and prove reaching modulus consensus under mild sufficient conditions of uniform connectivity of the graph. For cut-balanced graphs, not only sufficient, but also necessary conditions for modulus consensus are given.