OpenRaiser/Intern-Atlas huggingface dataset:
Chaining Test Cases for Reactive System Testing (extended version)
Venue: arXiv cs.SE 2013
Year: 2013

Testing of synchronous reactive systems is challenging because long input sequences are often needed to drive them into a state at which a desired feature can be tested. This is particularly problematic in on-target testing, where a system is tested in its real-life application environment and the time required for resetting is high. This paper presents an approach to discovering a test case chain---a single software execution that covers a group of test goals and minimises overall test execution time. Our technique targets the scenario in which test goals for the requirements are given as safety properties. We give conditions for the existence and minimality of a single test case chain and minimise the number of test chains if a single test chain is infeasible. We report experimental results with a prototype tool for C code generated from Simulink models and compare it to state-of-the-art test suite generators.
Generalized rank weights : a duality statement
Venue: arXiv cs.IT 2013
Year: 2013

We consider linear codes over some fixed finite field extension over an arbitrary finite field. Gabidulin introduced rank metric codes, by endowing linear codes over the extension field with a rank weight over the base field and studied their basic properties in analogy with linear codes and the classical Hamming distance. Inspired by the characterization of wiretap II codes in terms of generalized Hamming weights by Wei, Kurihara et al. defined some generalized rank weights and showed their relevance for secure network coding. In this paper, we derive a statement for generalized rank weights of the dual code, completely analogous to Wei's one for generalized Hamming weights and we characterize the equality case of the r-generalized Singleton bound for the generalized rank weights, in terms of the rank weight of the dual code.
Discriminating word senses with tourist walks in complex networks
Venue: arXiv cs.CL 2013
Year: 2013

Patterns of topological arrangement are widely used for both animal and human brains in the learning process. Nevertheless, automatic learning techniques frequently overlook these patterns. In this paper, we apply a learning technique based on the structural organization of the data in the attribute space to the problem of discriminating the senses of 10 polysemous words. Using two types of characterization of meanings, namely semantical and topological approaches, we have observed significative accuracy rates in identifying the suitable meanings in both techniques. Most importantly, we have found that the characterization based on the deterministic tourist walk improves the disambiguation process when one compares with the discrimination achieved with traditional complex networks measurements such as assortativity and clustering coefficient. To our knowledge, this is the first time that such deterministic walk has been applied to such a kind of problem. Therefore, our finding suggests that the tourist walk characterization may be useful in other related applications.
On the Asymptotic Performance of Bit-Wise Decoders for Coded Modulation
Venue: arXiv cs.IT 2013
Year: 2013

Two decoder structures for coded modulation over the Gaussian and flat fading channels are studied: the maximum likelihood symbol-wise decoder, and the (suboptimal) bit-wise decoder based on the bit-interleaved coded modulation paradigm. We consider a 16-ary quadrature amplitude constellation labeled by a Gray labeling. It is shown that the asymptotic loss in terms of pairwise error probability, for any two codewords caused by the bit-wise decoder, is bounded by 1.25 dB. The analysis also shows that for the Gaussian channel the asymptotic loss is zero for a wide range of linear codes, including all rate-1/2 convolutional codes.
Drawing Permutations with Few Corners
Venue: arXiv cs.DM 2013
Year: 2013

A permutation may be represented by a collection of paths in the plane. We consider a natural class of such representations, which we call tangles, in which the paths consist of straight segments at 45 degree angles, and the permutation is decomposed into nearest-neighbour transpositions. We address the problem of minimizing the number of crossings together with the number of corners of the paths, focusing on classes of permutations in which both can be minimized simultaneously. We give algorithms for computing such tangles for several classes of permutations.
A Microcontroller Based Device to Reduce Phanthom Power
Venue: arXiv cs.SY 2013
Year: 2013

In this paper we concern ourselves with the problem of minimizing the standby power consumption in some of the house hold appliances. Here we propose a remote controlled device through which we could reduce the amount of standby power consumed by the electrical appliances connected to it. This device provides an option of controlling each of the appliances connected to it individually or as a whole when required. The device has got number of plug points each of which could be controlled through the remote and also has a provision of switching off all the points at once.
Multidimensional User Data Model for Web Personalization
Venue: arXiv cs.IR 2013
Year: 2013

Personalization is being applied to great extend in many systems. This paper presents a multi-dimensional user data model and its application in web search. Online and Offline activities of the user are tracked for creating the user model. The main phases are identification of relevant documents and the representation of relevance and similarity of the documents. The concepts Keywords, Topics, URLs and clusters are used in the implementation. The algorithms for profiling, grading and clustering the concepts in the user model and algorithm for determining the personalized search results by re-ranking the results in a search bank are presented in this paper. Simple experiments for evaluation of the model and their results are described.
Hacking Smart Machines with Smarter Ones: How to Extract Meaningful Data from Machine Learning Classifiers
Venue: arXiv cs.CR 2013
Year: 2013

Machine Learning (ML) algorithms are used to train computers to perform a variety of complex tasks and improve with experience. Computers learn how to recognize patterns, make unintended decisions, or react to a dynamic environment. Certain trained machines may be more effective than others because they are based on more suitable ML algorithms or because they were trained through superior training sets. Although ML algorithms are known and publicly released, training sets may not be reasonably ascertainable and, indeed, may be guarded as trade secrets. While much research has been performed about the privacy of the elements of training sets, in this paper we focus our attention on ML classifiers and on the statistical information that can be unconsciously or maliciously revealed from them. We show that it is possible to infer unexpected but useful information from ML classifiers. In particular, we build a novel meta-classifier and train it to hack other classifiers, obtaining meaningful information about their training sets. This kind of information leakage can be exploited, for example, by a vendor to build more effective classifiers or to simply acquire trade secrets from a competitor's apparatus, potentially violating its intellectual property rights.
A temporal logic approach to modular design of synthetic biological circuits
Venue: arXiv cs.LO 2013
Year: 2013

We present a new approach for the design of a synthetic biological circuit whose behaviour is specified in terms of signal temporal logic (STL) formulae. We first show how to characterise with STL formulae the input/output behaviour of biological modules miming the classical logical gates (AND, NOT, OR). Hence, we provide the regions of the parameter space for which these specifications are satisfied. Given a STL specification of the target circuit to be designed and the networks of its constituent components, we propose a methodology to constrain the behaviour of each module, then identifying the subset of the parameter space in which those constraints are satisfied, providing also a measure of the robustness for the target circuit design. This approach, which leverages recent results on the quantitative semantics of Signal Temporal Logic, is illustrated by synthesising a biological implementation of an half-adder.
CSMA/ECA in Non-Saturation
Venue: arXiv cs.NI 2013
Year: 2013

During the past month we have been trying to understand both the behavior of CSMA/ECA and how our simulator works. In this report I try to asses some of those doubts and provide a groundwork for discussion of past and new ideas for further develop the MAC protocol.
Analysis of roles and groups in blogosphere
Venue: arXiv cs.SI 2013
Year: 2013

In the paper different roles of users in social media, taking into consideration their strength of influence and different degrees of cooperativeness, are introduced. Such identified roles are used for the analysis of characteristics of groups of strongly connected entities. The different classes of groups, considering the distribution of roles of users belonging to them, are presented and discussed.
Non-Correlated Character Recognition using Artificial Neural Network
Venue: arXiv cs.NE 2013
Year: 2013

This paper investigates a method of Handwritten English Character Recognition using Artificial Neural Network (ANN). This work has been done in offline Environment for non correlated characters, which do not possess any linear relationships among them. We test that whether the particular tested character belongs to a cluster or not. The implementation is carried out in Matlab environment and successfully tested. Fifty-two sets of English alphabets are used to train the ANN and test the network. The algorithms are tested with 26 capital letters and 26 small letters. The testing result showed that the proposed ANN based algorithm showed a maximum recognition rate of 85%.
A Fuzzy Based Approach to Text Mining and Document Clustering
Venue: arXiv cs.LG 2013
Year: 2013

Fuzzy logic deals with degrees of truth. In this paper, we have shown how to apply fuzzy logic in text mining in order to perform document clustering. We took an example of document clustering where the documents had to be clustered into two categories. The method involved cleaning up the text and stemming of words. Then, we chose m number of features which differ significantly in their word frequencies (WF), normalized by document length, between documents belonging to these two clusters. The documents to be clustered were represented as a collection of m normalized WF values. Fuzzy c-means (FCM) algorithm was used to cluster these documents into two clusters. After the FCM execution finished, the documents in the two clusters were analysed for the values of their respective m features. It was known that documents belonging to a document type, say X, tend to have higher WF values for some particular features. If the documents belonging to a cluster had higher WF values for those same features, then that cluster was said to represent X. By fuzzy logic, we not only get the cluster name, but also the degree to which a document belongs to a cluster.
Finding and Solving Contradictions of False Positives in Virus Scanning
Venue: arXiv cs.CR 2013
Year: 2013

False positives are equally dangerous as false negatives. Ideally the false positive rate should remain 0 or very close to 0. Even a slightest increase in false positive rate is considered as undesirable. Although the specific methods provide very accurate scanning by comparing viruses with their exact signatures, they fail to detect the new and unknown viruses. On the other hand the generic methods can detect even new viruses without using virus signatures. But these methods are more likely to generate false positives. There is a positive correlation between the capability to detect new and unknown viruses and false positive rate. While a traditional approach tries to achieve a right balance between false positives and false negatives a TRIZ approach looks forward to achieve the Ideal Final Result. The Ideal final result is to 'detect and prevent viruses with full certainty. The chances of error should be nil and the method should not raise any false positive or false negative.' The article shows many contradictions relating to false positives and their solutions.
Contradictions in Improving Speed of Virus Scanning
Venue: arXiv cs.CR 2013
Year: 2013

Although everything in computing industry moves faster including the processor, memory speed, memory size, storage space etc. there is no improvement in virus scanning time. Although the processing speed has substantially increased, a typical full scanning is still taking several hours for an average computer. There is a serious need to improve the scanning time. Contradiction is a stage of problem solving where the nature of the actual problem is clearly explained in terms of at least two parameters, one improving and another worsening. While emphasizing one parameter strengthens the system position emphasizing another parameter weakens the system. In conventional methods a problem solver has to make a perfect balance between these conflicting parameters, where the situation is neither too much on one side nor too much on the other. The results of those methods, although increase the speed of virus scanning, results in disadvantages like load on processor, increase in false positives and compromise on security. The objective of TRIZ is not to accept a tradeoff between the speed of scanning and those other difficulties but to resolve the contradictions so that the speed of scanning increases without compromising with security and other harmful results.
Computer simulation based parameter selection for resistance exercise
Venue: arXiv cs.CV 2013
Year: 2013

In contrast to most scientific disciplines, sports science research has been characterized by comparatively little effort investment in the development of relevant phenomenological models. Scarcer yet is the application of said models in practice. We present a framework which allows resistance training practitioners to employ a recently proposed neuromuscular model in actual training program design. The first novelty concerns the monitoring aspect of coaching. A method for extracting training performance characteristics from loosely constrained video sequences, effortlessly and with minimal human input, using computer vision is described. The extracted data is subsequently used to fit the underlying neuromuscular model. This is achieved by solving an inverse dynamics problem corresponding to a particular exercise. Lastly, a computer simulation of hypothetical training bouts, using athlete-specific capability parameters, is used to predict the effected adaptation and changes in performance. The software described here allows the practitioner to manipulate hypothetical training parameters and immediately see their effect on predicted adaptation for a specific athlete. Thus, this work presents a holistic view of the monitoring-assessment-adjustment loop.
On the second Hamming weight of some Reed-Muller type codes
Venue: arXiv cs.IT 2013
Year: 2013

We study affine cartesian codes, which are a Reed-Muller type of evaluation codes, where polynomials are evaluated at the cartesian product of n subsets of a finite field F_q. These codes appeared recently in a work by H. Lopez, C. Renteria-Marquez and R. Villareal and, in a generalized form, in a work by O. Geil and C. Thomsen. Using methods from Gröbner basis theory we determine the second Hamming weight (also called next-to-minimal weight) for particular cases of affine cartesian codes and also some higher Hamming weights of this type of code.
Analysing Word Importance for Image Annotation
Venue: arXiv cs.IR 2013
Year: 2013

Image annotation provides several keywords automatically for a given image based on various tags to describe its contents which is useful in Image retrieval. Various researchers are working on text based and content based image annotations [7,9]. It is seen, in traditional Image annotation approaches, annotation words are treated equally without considering the importance of each word in real world. In context of this, in this work, images are annotated with keywords based on their frequency count and word correlation. Moreover this work proposes an approach to compute importance score of candidate keywords, having same frequency count.
Performance Bounds for Multiclass FIFO in Communication Networks: A Deterministic Case
Venue: arXiv cs.PF 2013
Year: 2013

Multiclass FIFO is used in communication networks such as in input-queueing routers/switches and in wireless networks. For the concern of providing service guarantees in such networks, it is crucial to have analytical results, e.g. bounds, on the performance of multi-class FIFO. Surprisingly, there are few such results in the literature. This paper is devoted to filling the gap. Specifically, a single hop deterministic case is studied, for which, delay and backlog bounds are derived, in addition to guaranteed rate and service curve characterizations that may be exploited to extend the analysis to network cases.
Scheduling unit processing time arc shutdown jobs to maximize network flow over time: complexity results
Venue: arXiv cs.DM 2013
Year: 2013

We study the problem of scheduling maintenance on arcs of a capacitated network so as to maximize the total flow from a source node to a sink node over a set of time periods. Maintenance on an arc shuts down the arc for the duration of the period in which its maintenance is scheduled, making its capacity zero for that period. A set of arcs is designated to have maintenance during the planning period, which will require each to be shut down for exactly one time period. In general this problem is known to be NP-hard. Here we identify a number of characteristics that are relevant for the complexity of instance classes. In particular, we discuss instances with restrictions on the set of arcs that have maintenance to be scheduled; series parallel networks; capacities that are balanced, in the sense that the total capacity of arcs entering a (non-terminal) node equals the total capacity of arcs leaving the node; and identical capacities on all arcs.
Computing the Greedy Spanner in Linear Space
Venue: arXiv cs.CG 2013
Year: 2013

The greedy spanner is a high-quality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner of n points use Omega(n^2) space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices. We present a O(n)-space algorithm that computes the same spanner for points in R^d running in O(n^2 log^2 n) time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a near-quadratic running time guarantee that has actually been implemented.
Towards Tree Automata-based Success Types
Venue: arXiv cs.PL 2013
Year: 2013

Error detection facilities for dynamic languages are often based on unit testing. Thus, the advantage of rapid prototyping and flexibility must be weighed against cumbersome and time consuming test suite development. Lindahl and Sagonas' success typings provide a means of static must-fail detection in Erlang. Due to the constraint-based nature of the approach, some errors involving nested tuples and recursion cannot be detected. We propose an approach that uses an extension of model checking for pattern-matching recursion schemes with context-aware ranked tree automata to provide improved success typings for a constructor-based first-order prototype language.
Complex Morlet Wavelet Analysis of the DNA Frequency Chaos Game Signal and Revealing Specific Motifs of Introns in C.elegans
Venue: arXiv cs.SY 2013
Year: 2013

Nowadays, studying introns is becoming a very promising field in the genomics. Even though they play a role in the dynamic regulation of gene and in the organism's evolution, introns have not attracted enough attention like exons did; especially of digital signal processing researchers. Thus, we focus on analysis of the C.elegans introns. In this paper, we propose the complex Morlet wavelet analysis to investigate introns' characterization in the C.elegans genes. However, catching the change in frequency response with respect to time of the gene sequences is hindered by their presence in the form of strings of characters. This can only be counteracted by assigning numerical values to each of the DNA characters. This operation defines the so called "DNA coding approach". In this context, we propose a new coding technique based on the Frequency Chaos Game Representation (FCGR) that we name the "Frequency Chaos Game Signal" (FCGS). Results of the complex Morlet wavelet Analysis applied to the Celegans FCGS are showing a very distinguished texture. The visual interpretation of the colour scalograms is proved to be an efficient tool for revealing significant information about intronic sequences.
Scenario Analysis, Decision Trees and Simulation for Cost Benefit Analysis of the Cargo Screening Process
Venue: arXiv cs.CE 2013
Year: 2013

In this paper we present our ideas for conducting a cost benefit analysis by using three different methods: scenario analysis, decision trees and simulation. Then we introduce our case study and examine these methods in a real world situation. We show how these tools can be used and what the results are for each of them. Our aim is to conduct a comparison of these different probabilistic methods of estimating costs for port security risk assessment studies. Methodologically, we are trying to understand the limits of all the tools mentioned above by focusing on rare events.
A variant of the multi-agent rendezvous problem
Venue: arXiv cs.MA 2013
Year: 2013

The classical multi-agent rendezvous problem asks for a deterministic algorithm by which $n$ points scattered in a plane can move about at constant speed and merge at a single point, assuming each point can use only the locations of the others it sees when making decisions and that the visibility graph as a whole is connected. In time complexity analyses of such algorithms, only the number of rounds of computation required are usually considered, not the amount of computation done per round. In this paper, we consider $Ω(n^2 \log n)$ points distributed independently and uniformly at random in a disc of radius $n$ and, assuming each point can not only see but also, in principle, communicate with others within unit distance, seek a randomised merging algorithm which asymptotically almost surely (a.a.s.) runs in time O(n), in other words in time linear in the radius of the disc rather than in the number of points. Under a precise set of assumptions concerning the communication capabilities of neighboring points, we describe an algorithm which a.a.s. runs in time O(n) provided the number of points is $o(n^3)$. Several questions are posed for future work.