OpenRaiser/Intern-Atlas huggingface dataset:
Conflict Detection for Edits on Extended Feature Models using Symbolic Graph Transformation
Venue: arXiv cs.SE 2016
Year: 2016

Feature models are used to specify variability of user-configurable systems as appearing, e.g., in software product lines. Software product lines are supposed to be long-living and, therefore, have to continuously evolve over time to meet ever-changing requirements. Evolution imposes changes to feature models in terms of edit operations. Ensuring consistency of concurrent edits requires appropriate conflict detection techniques. However, recent approaches fail to handle crucial subtleties of extended feature models, namely constraints mixing feature-tree patterns with first-order logic formulas over non-Boolean feature attributes with potentially infinite value domains. In this paper, we propose a novel conflict detection approach based on symbolic graph transformation to facilitate concurrent edits on extended feature models. We describe extended feature models formally with symbolic graphs and edit operations with symbolic graph transformation rules combining graph patterns with first-order logic formulas. The approach is implemented by combining eMoflon with an SMT solver, and evaluated with respect to applicability.
Analysis of Feature Models Using Alloy: A Survey
Venue: arXiv cs.SE 2016
Year: 2016

Feature Models (FMs) are a mechanism to model variability among a family of closely related software products, i.e. a software product line (SPL). Analysis of FMs using formal methods can reveal defects in the specification such as inconsistencies that cause the product line to have no valid products. A popular framework used in research for FM analysis is Alloy, a light-weight formal modeling notation equipped with an efficient model finder. Several works in the literature have proposed different strategies to encode and analyze FMs using Alloy. However, there is little discussion on the relative merits of each proposal, making it difficult to select the most suitable encoding for a specific analysis need. In this paper, we describe and compare those strategies according to various criteria such as the expressivity of the FM notation or the efficiency of the analysis. This survey is the first comparative study of research targeted towards using Alloy for FM analysis. This review aims to identify all the best practices on the use of Alloy, as a part of a framework for the automated extraction and analysis of rich FMs from natural language requirement specifications.
The New Frontier in RAN Heterogeneity: Multi-tier Drone-Cells
Venue: arXiv cs.NI 2016
Year: 2016

In cellular networks, the locations of the radio access network (RAN) elements are determined mainly based on the long-term traffic behaviour. However, when the random and hard-to-predict spatio-temporal distribution of the traffic (load,demand) does not fully match the fixed locations of the RAN elements (supply), some performance degradation becomes inevitable. The concept of multi-tier cells (heterogeneous networks, HetNets) has been introduced in 4G networks to alleviate this mismatch. However, as the traffic distribution deviates more and more from the long-term average, even the HetNet architecture will have difficulty in coping up with the erratic supply-demand mismatch, unless the RAN is grossly over-engineered (which is a financially non-viable solution). In this article, we study the opportunistic utilization of low-altitude unmanned aerial platforms equipped with base stations (BSs), i.e., drone-BSs, in 5G networks. In particular, we envisage a multi-tier drone-cell network complementing the terrestrial HetNets. The variety of equipment, and non-rigid placement options allow utilizing multitier drone-cell networks to serve diversified demands. Hence, drone-cells bring the supply to where the demand is, which sets new frontiers for the heterogeneity in 5G networks. We investigate the advancements promised by drone-cells, and discuss the challenges associated with their operation and management. We propose a drone-cell management framework (DMF) benefiting from the synergy among software defined networking (SDN), network functions virtualization (NFV), and cloud-computing. We demonstrate DMF mechanisms via a case study, and numerically show that it can reduce the cost of utilizing drone-cells in multitenancy cellular networks.
Scalability Model Based on the Concept of Granularity
Venue: arXiv cs.DC 2016
Year: 2016

In the recent years it can be observed increasing popularity of parallel processing using multi-core processors, local clusters, GPU and others. Moreover, currently one of the main requirements the IT users is the reduction of maintaining cost of the computer infrastructure. It causes that the performance evaluation of the parallel applications becomes one of the most important problem. Then obtained results allows efficient use of available resources. In traditional methods of performance evaluation the results are based on wall-clock time measurements. This approach requires consecutive application executions and includes a time-consuming data analysis. In the paper an alternative approach is proposed. The decomposition of parallel application execution time onto computation time and overheads related to parallel execution is use to calculate the granularity of application and then determine its efficiency. Finally the application scalability can be evaluates.
Preferential Attachment Model with Degree Bound and its Application to Key Predistribution in WSN
Venue: arXiv cs.SI 2016
Year: 2016

Preferential attachment models have been widely studied in complex networks, because they can explain the formation of many networks like social networks, citation networks, power grids, and biological networks, to name a few. Motivated by the application of key predistribution in wireless sensor networks (WSN), we initiate the study of preferential attachment with degree bound. Our paper has two important contributions to two different areas. The first is a contribution in the study of complex networks. We propose preferential attachment model with degree bound for the first time. In the normal preferential attachment model, the degree distribution follows a power law, with many nodes of low degree and a few nodes of high degree. In our scheme, the nodes can have a maximum degree $d_{\max}$, where $d_{\max}$ is an integer chosen according to the application. The second is in the security of wireless sensor networks. We propose a new key predistribution scheme based on the above model. The important features of this model are that the network is fully connected, it has fewer keys, has larger size of the giant component and lower average path length compared with traditional key predistribution schemes and comparable resilience to random node attacks. We argue that in many networks like key predistribution and Internet of Things, having nodes of very high degree will be a bottle-neck in communication. Thus, studying preferential attachment model with degree bound will open up new directions in the study of complex networks, and will have many applications in real world scenarios.
On simulating processor schedules and network protocols within CPS using TrueTime
Venue: arXiv cs.SY 2016
Year: 2016

Studying cyber-physical system (CPS) for a given network protocol and processor schedules is a challenging task. This investigation illustrates the role of TrueTime a MATLAB package for simulating CPS encapsulating information on processor schedules, and network protocols. Properties of CPS such as temporal behaviors, performance and stability can be studied using the TrueTime tool. Furthermore, these simulations can be used to benchmark design and propose design alternatives. The procedure to use the toolbox for simulations and instantiate various blocks to study CPS is illustrated in the paper. Finally, an illustrative example has been presented of CPS simulation with wireless network. Our example demonstrates that TrueTime is a useful tool for studying CPS performance, timing behavior, schedulability analysis, and studying suitable network protocols.
A Characterization of the Non-Uniqueness of Nonnegative Matrix Factorizations
Venue: arXiv cs.LG 2016
Year: 2016

Nonnegative matrix factorization (NMF) is a popular dimension reduction technique that produces interpretable decomposition of the data into parts. However, this decompostion is not generally identifiable (even up to permutation and scaling). While other studies have provide criteria under which NMF is identifiable, we present the first (to our knowledge) characterization of the non-identifiability of NMF. We describe exactly when and how non-uniqueness can occur, which has important implications for algorithms to efficiently discover alternate solutions, if they exist.
Energy Efficient Resource Allocation for Time-Varying OFDMA Relay Systems with Hybrid Energy Supplies
Venue: arXiv cs.DC 2016
Year: 2016

This paper investigates the energy efficient resource allocation for orthogonal frequency division multiple access (OFDMA) relay systems, where the system is supplied by the conventional utility grid and a renewable energy generator equipped with a storage device. The optimal usage of radio resource depends on the characteristics of the renewable energy generation and the mobile traffic, which exhibit both temporal and spatial diversities. Lyapunov optimization method is used to decompose the problem into the joint flow control, radio resource allocation and energy management without knowing a priori knowledge of system statistics. It is proven that the proposed algorithm can result in close-to-optimal performance with capacity limited data buffer and storage device. Simulation results show that the flexible tradeoff between the system utility and the conventional energy consumption can be achieved. Compared with other schemes, the proposed algorithm demonstrates better performance.
Relay Selection for Cooperative NOMA
Venue: arXiv cs.IT 2016
Year: 2016

This letter studies the impact of relay selection (RS) on the performance of cooperative non-orthogonal multiple access (NOMA). In particular, a two-stage RS strategy is proposed, and analytical results are developed to demonstrate that this two-stage strategy can achieve the minimal outage probability among all possible RS schemes, and realize the maximal diversity gain. The provided simulation results show that cooperative NOMA with this two-stage RS scheme outperforms that with the conventional max-min approach, and can also yield a significant performance gain over orthogonal multiple access.
In narrative texts punctuation marks obey the same statistics as words
Venue: arXiv cs.CL 2016
Year: 2016

From a grammar point of view, the role of punctuation marks in a sentence is formally defined and well understood. In semantic analysis punctuation plays also a crucial role as a method of avoiding ambiguity of the meaning. A different situation can be observed in the statistical analyses of language samples, where the decision on whether the punctuation marks should be considered or should be neglected is seen rather as arbitrary and at present it belongs to a researcher's preference. An objective of this work is to shed some light onto this problem by providing us with an answer to the question whether the punctuation marks may be treated as ordinary words and whether they should be included in any analysis of the word co-occurences. We already know from our previous study (S.~Drożdż {\it et al.}, Inf. Sci. 331 (2016) 32-44) that full stops that determine the length of sentences are the main carrier of long-range correlations. Now we extend that study and analyze statistical properties of the most common punctuation marks in a few Indo-European languages, investigate their frequencies, and locate them accordingly in the Zipf rank-frequency plots as well as study their role in the word-adjacency networks. We show that, from a statistical viewpoint, the punctuation marks reveal properties that are qualitatively similar to the properties of the most frequent words like articles, conjunctions, pronouns, and prepositions. This refers to both the Zipfian analysis and the network analysis. By adding the punctuation marks to the Zipf plots, we also show that these plots that are normally described by the Zipf-Mandelbrot distribution largely restore the power-law Zipfian behaviour for the most frequent items.
The Influence of Frequency, Recency and Semantic Context on the Reuse of Tags in Social Tagging Systems
Venue: arXiv cs.SI 2016
Year: 2016

In this paper, we study factors that influence tag reuse behavior in social tagging systems. Our work is guided by the activation equation of the cognitive model ACT-R, which states that the usefulness of information in human memory depends on the three factors usage frequency, recency and semantic context. It is our aim to shed light on the influence of these factors on tag reuse. In our experiments, we utilize six datasets from the social tagging systems Flickr, CiteULike, BibSonomy, Delicious, LastFM and MovieLens, covering a range of various tagging settings. Our results confirm that frequency, recency and semantic context positively influence the reuse probability of tags. However, the extent to which each factor individually influences tag reuse strongly depends on the type of folksonomy present in a social tagging system. Our work can serve as guideline for researchers and developers of tag-based recommender systems when designing algorithms for social tagging environments.
Recognition of unipolar and generalised split graphs
Venue: arXiv cs.DS 2016
Year: 2016

A graph is unipolar if it can be partitioned into a clique and a disjoint union of cliques, and a graph is a generalised split graph if it or its complement is unipolar. A unipolar partition of a graph can be used to find efficiently the clique number, the stability number, the chromatic number, and to solve other problems that are hard for general graphs. We present the first $O(n^2)$ time algorithm for recognition of $n$-vertex unipolar and generalised split graphs, improving on previous $O(n^3)$ time algorithms.
Structural Multi-type Sequent Calculus for Inquisitive Logic
Venue: arXiv cs.LO 2016
Year: 2016

In this paper, we define a multi-type calculus for inquisitive logic, which is sound, complete and enjoys Belnap-style cut-elimination and subformula property. Inquisitive logic is the logic of inquisitive semantics, a semantic framework developed by Groenendijk, Roelofsen and Ciardelli which captures both assertions and questions in natural language. Inquisitive logic is sound and complete w.r.t. the so-called state semantics (also known as team semantics). The Hilbert-style presentation of inquisitive logic is not closed under uniform substitution; indeed, some occurrences of formulas are restricted to a certain subclass of formulas, called flat formulas. This and other features make the quest for analytic calculi for this logic not straightforward. We develop a certain algebraic and order-theoretic analysis of the team semantics, which provides the guidelines for the design of a multi-type environment which accounts for two domains of interpretation, for flat and for general formulas, as well as for their interaction. This multi-type environment in its turn provides the semantic environment for the multi-type calculus for inquisitive logic we introduce in this paper.
Capacity Achieving Distributions & Information Lossless Randomized Strategies for Feedback Channels with Memory: The LQG Theory of Directed Information-Part II
Venue: arXiv cs.IT 2016
Year: 2016

A methodology is developed to realized optimal channel input conditional distributions, which maximize the finite-time horizon directed information, for channels with memory and feedback, by information lossless randomized strategies. The methodology is applied to general Time-Varying Multiple Input Multiple Output (MIMO) Gaussian Linear Channel Models (G-LCMs) with memory, subject to average transmission cost constraints of quadratic form. The realizations of optimal distributions by randomized strategies are shown to exhibit a decomposion into a deterministic part and a random part. The decomposition reveals the dual role of randomized strategies, to control the channel output process and to transmit new information over the channels. Moreover, a separation principle is shown between the computation of the optimal deterministic part and the random part of the randomized strategies. The dual role of randomized strategies generalizes the Linear-Quadratic-Gaussian (LQG) stochastic optimal control theory to directed information pay-offs. The characterizations of feedback capacity are obtained from the per unit time limits of finite-time horizon directed information, without imposing á priori assumptions, such as, stability of channel models or ergodicity of channel input and output processes. For time-invariant MIMO G-LCMs with memory, it is shown that whether feedback increases capacity, is directly related to the channel parameters and the transmission cost function, through the solutions of Riccati matrix equations, and moreover for unstable channels, feedback capacity is non-zero, provided the power exceeds a critical level.
Multiparty quantum key agreement protocol secure against collusion attacks
Venue: arXiv cs.CR 2016
Year: 2016

The fairness of a secure multi-party quantum key agreement (MQKA) protocol requires that all involved parties are entirely peer entities and can equally influence the outcome of the protocol to establish a shared key wherein no one can decide the shared key alone. However, it is found that parts of the existing MQKA protocols are sensitive to collusion attacks, i.e., some of the dishonest participants can collaborate to predetermine the final key without being detected. In this paper, a multi-party QKA protocol resisting collusion attacks is proposed. Different from previous QKA protocol resisting $N-1$ coconspirators or resisting $1$ coconspirators, we investigate the general circle-type MQKA protocol which can be secure against $t$ dishonest participants' cooperation. Here, $t < N$. We hope the results of the presented paper will be helpful for further research on fair MQKA protocols.
Layered Uplink Transmission in Clustered Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

The demand for higher data rates and the scarce spectrum resources drive the adoption of collaborative communication techniques. In this work we shown that the existing cluster based collaborative schemes can be greatly improved in terms of both the achievable performance, and complexity, by allowing overlapping across clusters. Further improvement is achieved by incorporating scheduling to the decoding process. Different variants of the improved schemes are considered and are shown to achieve near optimum performance for practical signal-to-noise ratios for the one- and two-dimensional (hexagonal) Wyner-type models.
Online VNF Scaling in Datacenters
Venue: arXiv cs.NI 2016
Year: 2016

Network Function Virtualization (NFV) is a promising technology that promises to significantly reduce the operational costs of network services by deploying virtualized network functions (VNFs) to commodity servers in place of dedicated hardware middleboxes. The VNFs are typically running on virtual machine instances in a cloud infrastructure, where the virtualization technology enables dynamic provisioning of VNF instances, to process the fluctuating traffic that needs to go through the network functions in a network service. In this paper, we target dynamic provisioning of enterprise network services - expressed as one or multiple service chains - in cloud datacenters, and design efficient online algorithms without requiring any information on future traffic rates. The key is to decide the number of instances of each VNF type to provision at each time, taking into consideration the server resource capacities and traffic rates between adjacent VNFs in a service chain. In the case of a single service chain, we discover an elegant structure of the problem and design an efficient randomized algorithm achieving a e/(e-1) competitive ratio. For multiple concurrent service chains, an online heuristic algorithm is proposed, which is O(1)-competitive. We demonstrate the effectiveness of our algorithms using solid theoretical analysis and trace-driven simulations.
Design and Analysis of Transmit Beamforming for Millimetre Wave Base Station Discovery
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we develop an analytical framework for the initial access (a.k.a. Base Station (BS) discovery) in a millimeter-wave (mm-wave) communication system and propose an effective strategy for transmitting the Reference Signals (RSs) used for BS discovery. Specifically, by formulating the problem of BS discovery at User Equipments (UEs) as hypothesis tests, we derive a detector based on the Generalised Likelihood Ratio Test (GLRT) and characterise the statistical behaviour of the detector. The theoretical results obtained allow analysis of the impact of key system parameters on the performance of BS discovery, and show that RS transmission with narrow beams may not be helpful in improving the overall BS discovery performance due to the cost of spatial scanning. Using the method of large deviations, we identify the desirable beam pattern that minimises the average miss-discovery probability of UEs within a targeted detectable region. We then propose to transmit the RS with sequential scanning, using a pre-designed codebook with narrow and/or wide beams to approximate the desirable patterns. The proposed design allows flexible choices of the codebook sizes and the associated beam widths to better approximate the desirable patterns. Numerical results demonstrate the effectiveness of the proposed method.
On the Combinatorial Complexity of Approximating Polytopes
Venue: arXiv cs.CG 2016
Year: 2016

Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body $K$ of diameter $\mathrm{diam}(K)$ is given in Euclidean $d$-dimensional space, where $d$ is a constant. Given an error parameter $\varepsilon > 0$, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from $K$ is at most $\varepsilon \cdot \mathrm{diam}(K)$. By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that $O(1/\varepsilon^{(d-1)/2})$ facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is $\tilde{O}(1/\varepsilon^{(d-1)/2})$, where $\tilde{O}$ conceals a polylogarithmic factor in $1/\varepsilon$. This is a significant improvement upon the best known bound, which is roughly $O(1/\varepsilon^{d-2})$. Our result is based on a novel combination of both old and new ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Bárány and Larman's economical cap covering. Finally, we use a deterministic adaptation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.