OpenRaiser/Intern-Atlas huggingface dataset:
Feed drive modelling for the simulation of tool path tracking in multi-axis High Speed Machining
Venue: arXiv cs.OH 2011
Year: 2011

Within the context of High Speed Machining, it is essential to manage the trajectory generation to achieve both high surface quality and high productivity. As feed drives are one part of the set Machine tool - Numerical Controller, it is necessary to improve their performances to optimize feed drive dynamics during trajectory follow up. Hence, this paper deals with the modelling of the feed drive in the case of multi axis machining. This model can be used for the simulation of axis dynamics and tool-path tracking to tune parameters and optimize new frameworks of command strategies. A procedure of identification based on modern NC capabilities is presented and applied to industrial HSM centres. Efficiency of this modelling is assessed by experimental verifications on various representative trajectories. After implementing a Generalized Predictive Control, reliable simulations are performed thanks to the model. These simulations can then be used to tune parameters of this new framework according to the tool-path geometry.
Spatially-Coupled Codes and Threshold Saturation on Intersymbol-Interference Channels
Venue: arXiv cs.IT 2011
Year: 2011

Recently, it has been observed that terminated low-density-parity-check (LDPC) convolutional codes (or spatially-coupled codes) appear to approach capacity universally across the class of binary memoryless channels. This is facilitated by the "threshold saturation" effect whereby the belief-propagation (BP) threshold of the spatially-coupled ensemble is boosted to the maximum a-posteriori (MAP) threshold of the underlying constituent ensemble. In this paper, we consider the universality of spatially-coupled codes over intersymbol-interference (ISI) channels under joint iterative decoding. More specifically, we empirically show that threshold saturation also occurs for the considered problem. This can be observed by first identifying the EXIT curve for erasure noise and the GEXIT curve for general noise that naturally obey the general area theorem. From these curves, the corresponding MAP and the BP thresholds are then numerically obtained. With the fact that regular LDPC codes can achieve the symmetric information rate (SIR) under MAP decoding, spatially-coupled codes with joint iterative decoding can universally approach the SIR of ISI channels. For the dicode erasure channel, Kudekar and Kasai recently reported very similar results based on EXIT-like curves.
On the Simulation of Adaptive Measurements via Postselection
Venue: arXiv cs.CC 2011
Year: 2011

In this note we address the question of whether any any quantum computational model that allows adaptive measurements can be simulated by a model that allows postselected measurements. We argue in the favor of this question and prove that adaptive measurements can be simulated by postselection. We also discuss some potentially stunning consequences of this result such as the ability to solve #P problems.
Semantic annotation of requirements for automatic UML class diagram generation
Venue: arXiv cs.SE 2011
Year: 2011

The increasing complexity of software engineering requires effective methods and tools to support requirements analysts' activities. While much of a company's knowledge can be found in text repositories, current content management systems have limited capabilities for structuring and interpreting documents. In this context, we propose a tool for transforming text documents describing users' requirements to an UML model. The presented tool uses Natural Language Processing (NLP) and semantic rules to generate an UML class diagram. The main contribution of our tool is to provide assistance to designers facilitating the transition from a textual description of user requirements to their UML diagrams based on GATE (General Architecture of Text) by formulating necessary rules that generate new semantic annotations.
From decision to action : intentionality, a guide for the specification of intelligent agents' behaviour
Venue: arXiv cs.AI 2011
Year: 2011

This article introduces a reflexion about behavioural specification for interactive and participative agent-based simulation in virtual reality. Within this context, it is neces sary to reach a high level of expressivness in order to enforce interactions between the designer and the behavioural model during the in-line prototyping. This requires to consider the need of semantic very early in the design process. The Intentional agent model is here exposed as a possible answer. It relies on a mixed imperative and declarative approach which focuses on the link between decision and action. The design of a tool able to simulate virtual environment implying agents based on this model is discuss
Optimal symmetric Tardos traitor tracing schemes
Venue: arXiv cs.CR 2011
Year: 2011

For the Tardos traitor tracing scheme, we show that by combining the symbol-symmetric accusation function of Skoric et al. with the improved analysis of Blayer and Tassa we get further improvements. Our construction gives codes that are up to 4 times shorter than Blayer and Tassa's, and up to 2 times shorter than the codes from Skoric et al. Asymptotically, we achieve the theoretical optimal codelength for Tardos' distribution function and the symmetric score function. For large coalitions, our codelengths are asymptotically about 4.93% of Tardos' original codelengths, which also improves upon results from Nuida et al.
Systematic Abstraction of Abstract Machines
Venue: arXiv cs.PL 2011
Year: 2011

We describe a derivational approach to abstract interpretation that yields novel and transparently sound static analyses when applied to well-established abstract machines for higher-order and imperative programming languages. To demonstrate the technique and support our claim, we transform the CEK machine of Felleisen and Friedman, a lazy variant of Krivine's machine, and the stack-inspecting CM machine of Clements and Felleisen into abstract interpretations of themselves. The resulting analyses bound temporal ordering of program events; predict return-flow and stack-inspection behavior; and approximate the flow and evaluation of by-need parameters. For all of these machines, we find that a series of well-known concrete machine refactorings, plus a technique of store-allocated continuations, leads to machines that abstract into static analyses simply by bounding their stores. We demonstrate that the technique scales up uniformly to allow static analysis of realistic language features, including tail calls, conditionals, side effects, exceptions, first-class continuations, and even garbage collection. In order to close the gap between formalism and implementation, we provide translations of the mathematics as running Haskell code for the initial development of our method.
New construction of APN quaratic
Venue: arXiv cs.IT 2011
Year: 2011

The purpose of this paper is to detail the article of Carlet. Along the way I recall some interesting results in the theory of finite fields, I give (new) proofs of some known results, and then I generalize the construction of a family of APN function. The reference precedes each result, and in the absence of reference the proof is due to the author. Keywords: boolean, bent, APN
On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
Venue: arXiv cs.DS 2011
Year: 2011

The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite (i.e., 2-colorable) by deleting at most l vertices. We study structural parameterizations of OCT with respect to their polynomial kernelizability, i.e., whether instances can be efficiently reduced to a size polynomial in the chosen parameter. It is a major open problem in parameterized complexity whether Odd Cycle Transversal admits a polynomial kernel when parameterized by l. On the positive side, we show a polynomial kernel for OCT when parameterized by the vertex deletion distance to the class of bipartite graphs of treewidth at most w (for any constant w); this generalizes the parameter feedback vertex set number (i.e., the distance to a forest). Complementing this, we exclude polynomial kernels for OCT parameterized by the distance to outerplanar graphs, conditioned on the assumption that NP \not \subseteq coNP/poly. Thus the bipartiteness requirement for the treewidth w graphs is necessary. Further lower bounds are given for parameterization by distance from cluster and co-cluster graphs respectively, as well as for Weighted OCT parameterized by the vertex cover number (i.e., the distance from an independent set).
Ubiquitous Mobile Health Monitoring System for Elderly (UMHMSE)
Venue: arXiv cs.NI 2011
Year: 2011

Recent research in ubiquitous computing uses technologies of Body Area Networks (BANs) to monitor the person's kinematics and physiological parameters. In this paper we propose a real time mobile health system for monitoring elderly patients from indoor or outdoor environments. The system uses a bio- signal sensor worn by the patient and a Smartphone as a central node. The sensor data is collected and transmitted to the intelligent server through GPRS/UMTS to be analyzed. The prototype (UMHMSE) monitors the elderly mobility, location and vital signs such as Sp02 and Heart Rate. Remote users (family and medical personnel) might have a real time access to the collected information through a web application.
Using Variational Inference and MapReduce to Scale Topic Modeling
Venue: arXiv cs.AI 2011
Year: 2011

Latent Dirichlet Allocation (LDA) is a popular topic modeling technique for exploring document collections. Because of the increasing prevalence of large datasets, there is a need to improve the scalability of inference of LDA. In this paper, we propose a technique called ~\emph{MapReduce LDA} (Mr. LDA) to accommodate very large corpus collections in the MapReduce framework. In contrast to other techniques to scale inference for LDA, which use Gibbs sampling, we use variational inference. Our solution efficiently distributes computation and is relatively simple to implement. More importantly, this variational implementation, unlike highly tuned and specialized implementations, is easily extensible. We demonstrate two extensions of the model possible with this scalable framework: informed priors to guide topic discovery and modeling topics from a multilingual corpus.
Teaching Introductory Electrical Engineering Course to CS Students in a Russian University
Venue: arXiv cs.CY 2011
Year: 2011

This article is about the author's experience with developing and teaching an introductory electrical engineering course for students of Faculty (department) of Information Technology of a Russian university. The curriculum of this department conforms to typical computer science curricula of US engineering schools with a noticeable omission of comparable electrical engineering courses. When developing the course, I did my best to pay attention to learning preferences of the department's student body. I also hoped to contribute to a degree to meeting labor market demands for developers of electrical engineering CAD software. As for inspiration, I was enchanted with ideas of the Mead & Conway revolution, albeit indirectly related to my enterprise.
Online Anomaly Detection Systems Using Incremental Commute Time
Venue: arXiv cs.AI 2011
Year: 2011

Commute Time Distance (CTD) is a random walk based metric on graphs. CTD has found widespread applications in many domains including personalized search, collaborative filtering and making search engines robust against manipulation. Our interest is inspired by the use of CTD as a metric for anomaly detection. It has been shown that CTD can be used to simultaneously identify both global and local anomalies. Here we propose an accurate and efficient approximation for computing the CTD in an incremental fashion in order to facilitate real-time applications. An online anomaly detection algorithm is designed where the CTD of each new arriving data point to any point in the current graph can be estimated in constant time ensuring a real-time response. Moreover, the proposed approach can also be applied in many other applications that utilize commute time distance.
Metrics of Risk Associated with Defects Rediscovery
Venue: arXiv cs.SE 2011
Year: 2011

Software defects rediscovered by a large number of customers affect various stakeholders and may: 1) hint at gaps in a software manufacturer's Quality Assurance (QA) processes, 2) lead to an over-load of a software manufacturer's support and maintenance teams, and 3) consume customers' resources, leading to a loss of reputation and a decrease in sales. Quantifying risk associated with the rediscovery of defects can help all of these stake-holders. In this chapter we present a set of metrics needed to quantify the risks. The metrics are designed to help: 1) the QA team to assess their processes; 2) the support and maintenance teams to allocate their resources; and 3) the customers to assess the risk associated with using the software product. The paper includes a validation case study which applies the risk metrics to industrial data. To calculate the metrics we use mathematical instruments like the heavy-tailed Kappa distribution and the G/M/k queuing model.
Towards Completely Lifted Search-based Probabilistic Inference
Venue: arXiv cs.AI 2011
Year: 2011

The promise of lifted probabilistic inference is to carry out probabilistic inference in a relational probabilistic model without needing to reason about each individual separately (grounding out the representation) by treating the undistinguished individuals as a block. Current exact methods still need to ground out in some cases, typically because the representation of the intermediate results is not closed under the lifted operations. We set out to answer the question as to whether there is some fundamental reason why lifted algorithms would need to ground out undifferentiated individuals. We have two main results: (1) We completely characterize the cases where grounding is polynomial in a population size, and show how we can do lifted inference in time polynomial in the logarithm of the population size for these cases. (2) For the case of no-argument and single-argument parametrized random variables where the grounding is not polynomial in a population size, we present lifted inference which is polynomial in the population size whereas grounding is exponential. Neither of these cases requires reasoning separately about the individuals that are not explicitly mentioned.
Sending Hidden Data via Google Suggest
Venue: arXiv cs.CR 2011
Year: 2011

Google Suggest is a service incorporated within Google Web Search which was created to help user find the right search phrase by proposing the autocompleting popular phrases while typing. The paper presents a new network steganography method called StegSuggest which utilizes suggestions generated by Google Suggest as a hidden data carrier. The detailed description of the method's idea is backed up with the analysis of the network traffic generated by the Google Suggest to prove its feasibility. The traffic analysis was also performed to discover the occurrence of two TCP options: Window Scale and Timestamp which StegSuggest uses to operate. Estimation of method steganographic bandwidth proves that it is possible to insert 100 bits of steganogram into every suggestions list sent by Google Suggest service.
Analysis on the computability over the efficient utilization problem of the four-dimensional space-time
Venue: arXiv cs.CC 2011
Year: 2011

This paper formally proposes a problem about the efficient utilization of the four dimensional space-time. Given a cuboid container, a finite number of rigid cuboid items, and the time length that each item should be continuous baked in the container, the problem asks to arrange the starting time for each item being placed into the container and to arrange the position and orientation for each item at each instant during its continuous baking period such that the total time length the container be utilized is as short as possible. Here all side dimensions of the container and of the items are positive real numbers arbitrarily given. Differs from the classical packing problems, the position and orientation of each item in the container could be changed over time. Therefore, according to above mathematical model, the four-dimensional space-time can be utilized more truly and more fully. This paper then proves that there exists an exact algorithm that could solve the problem by finite operations, so we say this problem is weak computable. Based on the understanding of this computability proof, it is expected to design effective approximate algorithms in the near future. A piggyback work completed is a strict proof on the weak computability over general and natural case of the three-dimensional cuboid packing decision problem that all parameters are positive real numbers.
Local Optima Networks of the Quadratic Assignment Problem
Venue: arXiv cs.AI 2011
Year: 2011

Using a recently proposed model for combinatorial landscapes, Local Optima Networks (LON), we conduct a thorough analysis of two types of instances of the Quadratic Assignment Problem (QAP). This network model is a reduction of the landscape in which the nodes correspond to the local optima, and the edges account for the notion of adjacency between their basins of attraction. The model was inspired by the notion of 'inherent network' of potential energy surfaces proposed in physical-chemistry. The local optima networks extracted from the so called uniform and real-like QAP instances, show features clearly distinguishing these two types of instances. Apart from a clear confirmation that the search difficulty increases with the problem dimension, the analysis provides new confirming evidence explaining why the real-like instances are easier to solve exactly using heuristic search, while the uniform instances are easier to solve approximately. Although the local optima network model is still under development, we argue that it provides a novel view of combinatorial landscapes, opening up the possibilities for new analytical tools and understanding of problem difficulty in combinatorial optimization.
Interference minimization in physical model of wireless networks
Venue: arXiv cs.DS 2011
Year: 2011

Interference minimization problem in wireless sensor and ad-hoc networks is considered. That is to assign a transmission power to each node of a network such that the network is connected and at the same time the maximum of accumulated signal straight on network nodes is minimum. Previous works on interference minimization in wireless networks mainly consider the disk graph model of network. For disk graph model two approximation algorithms with $O(\sqrt{n})$ and $O((opt\ln{n})^{2})$ upper bounds of maximum interference are known, where $n$ is the number of nodes and $opt$ is the minimal interference of a given network. In current work we consider more general interference model, the physical interference model, where sender nodes' signal straight on a given node is a function of a sender/receiver node pair and sender nodes' transmission power. For this model we give a polynomial time approximation algorithm which finds a connected network with at most $O((opt\ln{n})^{2}/β)$ interference, where $β\geq 1$ is the minimum signal straight necessary on receiver node for successfully receiving a message.
Greedy Set Cover Estimations
Venue: arXiv cs.DM 2011
Year: 2011

More precise estimation of the greedy algorithm complexity for a special case of the set cover problem is given in this paper.
The IHS Transformations Based Image Fusion
Venue: arXiv cs.CV 2011
Year: 2011

The IHS sharpening technique is one of the most commonly used techniques for sharpening. Different transformations have been developed to transfer a color image from the RGB space to the IHS space. Through literature, it appears that, various scientists proposed alternative IHS transformations and many papers have reported good results whereas others show bad ones as will as not those obtained which the formula of IHS transformation were used. In addition to that, many papers show different formulas of transformation matrix such as IHS transformation. This leads to confusion what is the exact formula of the IHS transformation?. Therefore, the main purpose of this work is to explore different IHS transformation techniques and experiment it as IHS based image fusion. The image fusion performance was evaluated, in this study, using various methods to estimate the quality and degree of information improvement of a fused image quantitatively.
Logical Concurrency Control from Sequential Proofs
Venue: arXiv cs.PL 2011
Year: 2011

We are interested in identifying and enforcing the isolation requirements of a concurrent program, i.e., concurrency control that ensures that the program meets its specification. The thesis of this paper is that this can be done systematically starting from a sequential proof, i.e., a proof of correctness of the program in the absence of concurrent interleavings. We illustrate our thesis by presenting a solution to the problem of making a sequential library thread-safe for concurrent clients. We consider a sequential library annotated with assertions along with a proof that these assertions hold in a sequential execution. We show how we can use the proof to derive concurrency control that ensures that any execution of the library methods, when invoked by concurrent clients, satisfies the same assertions. We also present an extension to guarantee that the library methods are linearizable or atomic.
A Game Theoretic Approach to Distributed Opportunistic Scheduling
Venue: arXiv cs.NI 2011
Year: 2011

Distributed Opportunistic Scheduling (DOS) is inherently harder than conventional opportunistic scheduling due to the absence of a central entity that has knowledge of all the channel states. With DOS, stations contend for the channel using random access; after a successful contention, they measure the channel conditions and only transmit in case of a good channel, while giving up the transmission opportunity when the channel conditions are poor. The distributed nature of DOS systems makes them vulnerable to selfish users: by deviating from the protocol and using more transmission opportunities, a selfish user can gain a greater share of the wireless resources at the expense of the well-behaved users. In this paper, we address the selfishness problem in DOS from a game theoretic standpoint. We propose an algorithm that satisfies the following properties: (i) when all stations implement the algorithm, the wireless network is driven to the optimal point of operation, and (ii) one or more selfish stations cannot gain any profit by deviating from the algorithm. The key idea of the algorithm is to react to a selfish station by using a more aggressive configuration that (indirectly) punishes this station. We build on multivariable control theory to design a mechanism for punishment that on the one hand is sufficiently severe to prevent selfish behavior while on the other hand is light enough to guarantee that, in the absence of selfish behavior, the system is stable and converges to the optimum point of operation. We conduct a game theoretic analysis based on repeated games to show the algorithm's effectiveness against selfish stations. These results are confirmed by extensive simulations.
Remarks on generalized toric codes
Venue: arXiv cs.IT 2011
Year: 2011

This note presents some new information on how the minimum distance of the generalized toric code corresponding to a fixed set of integer lattice points S in R^2 varies with the base field. The main results show that in some cases, over sufficiently large fields, the minimum distance of the code corresponding to a set S will be the same as that of the code corresponding to the convex hull of S. In an example, we will also discuss a [49,12,28] generalized toric code over GF(8), better than any previously known code according to M. Grassl's online tables, as of July 2011.