OpenRaiser/Intern-Atlas huggingface dataset:
A Hybrid Bacterial Foraging Algorithm For Solving Job Shop Scheduling Problems
Venue: arXiv cs.NE 2012
Year: 2012

Bio-Inspired computing is the subset of Nature-Inspired computing. Job Shop Scheduling Problem is categorized under popular scheduling problems. In this research work, Bacterial Foraging Optimization was hybridized with Ant Colony Optimization and a new technique Hybrid Bacterial Foraging Optimization for solving Job Shop Scheduling Problem was proposed. The optimal solutions obtained by proposed Hybrid Bacterial Foraging Optimization algorithms are much better when compared with the solutions obtained by Bacterial Foraging Optimization algorithm for well-known test problems of different sizes. From the implementation of this research work, it could be observed that the proposed Hybrid Bacterial Foraging Optimization was effective than Bacterial Foraging Optimization algorithm in solving Job Shop Scheduling Problems. Hybrid Bacterial Foraging Optimization is used to implement real world Job Shop Scheduling Problems.
Human-Centric Process-Aware Information Systems (HC-PAIS)
Venue: arXiv cs.HC 2012
Year: 2012

Process-Aware Information Systems (PAIS) support organizations in managing and automating their processes. A full automation of processes is in particular industries, such as service-oriented markets, not practicable. The integration of humans in PAIS is necessary to manage and perform processes that require human capabilities, judgments and decisions. A challenge of interdisciplinary PAIS research is to provide concepts and solutions that support human integration in PAIS and human orientation of PAIS in a way that provably increase the PAIS users' satisfaction and motivation with working with the Human-Centric Process Aware Information System (HC-PAIS) and consequently influence users' performance of tasks. This work is an initial step of research that aims at providing a definition of Human-Centric Process Aware Information Systems (HC-PAIS) and future research challenges of HC-PAIS. Results of focus group research are presented.
Notes on Convex Transversals
Venue: arXiv cs.CG 2012
Year: 2012

In this paper, we prove the problem of stabbing a set of disjoint bends by a convex stabber to be NP-hard. We also consider the optimization version of the convex stabber problem and prove this problem to be APX-hard for sets of line segments.
The Rightmost Equal-Cost Position Problem
Venue: arXiv cs.DS 2012
Year: 2012

LZ77-based compression schemes compress the input text by replacing factors in the text with an encoded reference to a previous occurrence formed by the couple (length, offset). For a given factor, the smallest is the offset, the smallest is the resulting compression ratio. This is optimally achieved by using the rightmost occurrence of a factor in the previous text. Given a cost function, for instance the minimum number of bits used to represent an integer, we define the Rightmost Equal-Cost Position (REP) problem as the problem of finding one of the occurrences of a factor which cost is equal to the cost of the rightmost one. We present the Multi-Layer Suffix Tree data structure that, for a text of length n, at any time i, it provides REP(LPF) in constant time, where LPF is the longest previous factor, i.e. the greedy phrase, a reference to the list of REP({set of prefixes of LPF}) in constant time and REP(p) in time O(|p| log log n) for any given pattern p.
Continuous Markovian Logics - Axiomatization and Quantified Metatheory
Venue: arXiv cs.LO 2012
Year: 2012

Continuous Markovian Logic (CML) is a multimodal logic that expresses quantitative and qualitative properties of continuous-time labelled Markov processes with arbitrary (analytic) state-spaces, henceforth called continuous Markov processes (CMPs). The modalities of CML evaluate the rates of the exponentially distributed random variables that characterize the duration of the labeled transitions of a CMP. In this paper we present weak and strong complete axiomatizations for CML and prove a series of metaproperties, including the finite model property and the construction of canonical models. CML characterizes stochastic bisimilarity and it supports the definition of a quantified extension of the satisfiability relation that measures the "compatibility" between a model and a property. In this context, the metaproperties allows us to prove two robustness theorems for the logic stating that one can perturb formulas and maintain "approximate satisfaction".
Sparsity-Aware Learning and Compressed Sensing: An Overview
Venue: arXiv cs.IT 2012
Year: 2012

This paper is based on a chapter of a new book on Machine Learning, by the first and third author, which is currently under preparation. We provide an overview of the major theoretical advances as well as the main trends in algorithmic developments in the area of sparsity-aware learning and compressed sensing. Both batch processing and online processing techniques are considered. A case study in the context of time-frequency analysis of signals is also presented. Our intent is to update this review from time to time, since this is a very hot research area with a momentum and speed that is sometimes difficult to follow up.
Non-Asymptotic Analysis of Privacy Amplification via Renyi Entropy and Inf-Spectral Entropy
Venue: arXiv cs.IT 2012
Year: 2012

This paper investigates the privacy amplification problem, and compares the existing two bounds: the exponential bound derived by one of the authors and the min-entropy bound derived by Renner. It turns out that the exponential bound is better than the min-entropy bound when a security parameter is rather small for a block length, and that the min-entropy bound is better than the exponential bound when a security parameter is rather large for a block length. Furthermore, we present another bound that interpolates the exponential bound and the min-entropy bound by a hybrid use of the Renyi entropy and the inf-spectral entropy.
What is Nature-like Computation? A Behavioural Approach and a Notion of Programmability
Venue: arXiv cs.LO 2012
Year: 2012

The aim of this paper is to propose an alternative behavioural definition of computation (and of a computer) based simply on whether a system is capable of reacting to the environment-the input-as reflected in a measure of programmability. This definition is intended to have relevance beyond the realm of digital computers, particularly vis-a-vis natural systems. This will be done by using an extension of a phase transition coefficient previously defined in an attempt to characterise the dynamical behaviour of cellular automata and other systems. The transition coefficient measures the sensitivity of a system to external stimuli, and will be used to define the susceptibility of a system to being (efficiently) programmed.
Game Dynamics and Nash Equilibria
Venue: arXiv cs.GT 2012
Year: 2012

If a game has a unique Nash equilibrium, then this equilibrium is arguably the solution of the game from the refinement's literature point of view. However, it might be that for almost all initial conditions, all strategies in the support of this equilibrium are eliminated by the replicator dynamics and the best-reply dynamics.
Optimal design of PID controllers using the QFT method
Venue: arXiv cs.SY 2012
Year: 2012

An optimisation algorithm is proposed for designing PID controllers, which minimises the asymptotic open-loop gain of a system, subject to appropriate robust- stability and performance QFT constraints. The algorithm is simple and can be used to automate the loop-shaping step of the QFT design procedure. The effectiveness of the method is illustrated with an example.
A Note on Kolmogorov-Uspensky Machines
Venue: arXiv cs.CC 2012
Year: 2012

Solving an open problem stated by Shvachko, it is shown that a language which is not real-time recognizable by some variants of pointer machines can be accepted by a Kolmogorov-Uspensky machine in real-time.
Texture Modeling with Convolutional Spike-and-Slab RBMs and Deep Extensions
Venue: arXiv cs.LG 2012
Year: 2012

We apply the spike-and-slab Restricted Boltzmann Machine (ssRBM) to texture modeling. The ssRBM with tiled-convolution weight sharing (TssRBM) achieves or surpasses the state-of-the-art on texture synthesis and inpainting by parametric models. We also develop a novel RBM model with a spike-and-slab visible layer and binary variables in the hidden layer. This model is designed to be stacked on top of the TssRBM. We show the resulting deep belief network (DBN) is a powerful generative model that improves on single-layer models and is capable of modeling not only single high-resolution and challenging textures but also multiple textures.
Compliance error compensation technique for parallel robots composed of non-perfect serial chains
Venue: arXiv cs.RO 2012
Year: 2012

The paper presents the compliance errors compensation technique for over-constrained parallel manipulators under external and internal loadings. This technique is based on the non-linear stiffness modeling which is able to take into account the influence of non-perfect geometry of serial chains caused by manufacturing errors. Within the developed technique, the deviation compensation reduces to an adjustment of a target trajectory that is modified in the off-line mode. The advantages and practical significance of the proposed technique are illustrated by an example that deals with groove milling by the Orthoglide manipulator that considers different locations of the workpiece. It is also demonstrated that the impact of the compliance errors and the errors caused by inaccuracy in serial chains cannot be taken into account using the superposition principle.
Super-Resolution by Compressive Sensing Algorithms
Venue: arXiv cs.IT 2012
Year: 2012

In this work, super-resolution by 4 compressive sensing methods (OMP, BP, BLOOMP, BP-BLOT) with highly coherent partial Fourier measurements is comparatively studied. An alternative metric more suitable for gauging the quality of spike recovery is introduced and based on the concept of filtration with a parameter representing the level of tolerance for support offset. In terms of the filtered error norm only BLOOMP and BP-BLOT can perform grid-independent recovery of well separated spikes of Rayleigh index 1 for arbitrarily large super-resolution factor. Moreover both BLOOMP and BP-BLOT can localize spike support within a few percent of the Rayleigh length. This is a weak form of super-resolution. Only BP-BLOT can achieve this feat for closely spaced spikes separated by a fraction of the Rayleigh length, a strong form of super-resolution.
MMSE Performance Analysis of Generalized Multibeam Satellite Channels
Venue: arXiv cs.IT 2012
Year: 2012

Aggressive frequency reuse in the return link (RL) of multibeam satellite communications (SatComs) is crucial towards the implementation of next generation, interactive satellite services. In this direction, multiuser detection has shown great potential in mitigating the increased intrasystem interferences, induced by a tight spectrum reuse. Herein we present an analytic framework to describe the linear Minimum Mean Square Error (MMSE) performance of multiuser channels that exhibit full receive correlation: an inherent attribute of the RL of multibeam SatComs. Analytic, tight approximations on the MMSE performance are proposed for cases where closed form solutions are not available in the existing literature. The proposed framework is generic, thus providing a generalized solution straightforwardly extendable to various fading models over channels that exhibit full receive correlation. Simulation results are provided to show the tightness of the proposed approximation with respect to the available transmit power.
On the Egalitarian Weights of Nations
Venue: arXiv cs.GT 2012
Year: 2012

Voters from m disjoint constituencies (regions, federal states, etc.) are represented in an assembly which contains one delegate from each constituency and applies a weighted voting rule. All agents are assumed to have single-peaked preferences over an interval; each delegate's preferences match his constituency's median voter; and the collective decision equals the assembly's Condorcet winner. We characterize the asymptotic behavior of the probability of a given delegate determining the outcome (i.e., being the weighted median of medians) in order to address a contentious practical question: which voting weights w_1, ..., w_m ought to be selected if constituency sizes differ and all voters are to have a priori equal influence on collective decisions? It is shown that if ideal point distributions have identical median M and are suitably continuous, the probability for a given delegate i's ideal point λ_i being the Condorcet winner becomes asymptotically proportional to i's voting weight w_i times λ_i's density at M as $m\to \infty$. Indirect representation of citizens is approximately egalitarian for weights proportional to the square root of constituency sizes if all individual ideal points are i.i.d. In contrast, weights that are linear in-- or, better, induce a Shapley value linear in-- size are egalitarian when preferences are sufficiently strongly affiliated within constituencies.
Automatic Verification of Message-Based Device Drivers
Venue: arXiv cs.OS 2012
Year: 2012

We develop a practical solution to the problem of automatic verification of the interface between device drivers and the OS. Our solution relies on a combination of improved driver architecture and verification tools. It supports drivers written in C and can be implemented in any existing OS, which sets it apart from previous proposals for verification-friendly drivers. Our Linux-based evaluation shows that this methodology amplifies the power of existing verification tools in detecting driver bugs, making it possible to verify properties beyond the reach of traditional techniques.
Static Analysis of Lockless Microcontroller C Programs
Venue: arXiv cs.PL 2012
Year: 2012

Concurrently accessing shared data without locking is usually a subject to race conditions resulting in inconsistent or corrupted data. However, there are programs operating correctly without locking by exploiting the atomicity of certain operations on a specific hardware. In this paper, we describe how to precisely analyze lockless microcontroller C programs with interrupts by taking the hardware architecture into account. We evaluate this technique in an octagon-based value range analysis using access-based localization to increase efficiency.
Formal Semantics of Heterogeneous CUDA-C: A Modular Approach with Applications
Venue: arXiv cs.PL 2012
Year: 2012

We extend an off-the-shelf, executable formal semantics of C (Ellison and Rosu's K Framework semantics) with the core features of CUDA-C. The hybrid CPU/GPU computation model of CUDA-C presents challenges not just for programmers, but also for practitioners of formal methods. Our formal semantics helps expose and clarify these issues. We demonstrate the usefulness of our semantics by generating a tool from it capable of detecting some race conditions and deadlocks in CUDA-C programs. We discuss limitations of our model and argue that its extensibility can easily enable a wider range of verification tasks.
A simple non-parametric Topic Mixture for Authors and Documents
Venue: arXiv cs.LG 2012
Year: 2012

This article reviews the Author-Topic Model and presents a new non-parametric extension based on the Hierarchical Dirichlet Process. The extension is especially suitable when no prior information about the number of components necessary is available. A blocked Gibbs sampler is described and focus put on staying as close as possible to the original model with only the minimum of theoretical and implementation overhead necessary.
A RDF-based Data Integration Framework
Venue: arXiv cs.DB 2012
Year: 2012

Data integration is one of the main problems in distributed data sources. An approach is to provide an integrated mediated schema for various data sources. This research work aims at developing a framework for defining an integrated schema and querying on it. The basic idea is to employ recent standard languages and tools to provide a unified data integration framework. RDF is used for integrated schema descriptions as well as providing a unified view of data. RDQL is used for query reformulation. Furthermore, description logic inference services provide necessary means for satisfiability checking of concepts in integrated schema. The framework has tools to display integrated schema, query on it, and provides enough flexibilities to be used in different application domains.
Citation content analysis (cca): A framework for syntactic and semantic analysis of citation content
Venue: arXiv cs.DL 2012
Year: 2012

This paper proposes a new framework for Citation Content Analysis (CCA), for syntactic and semantic analysis of citation content that can be used to better analyze the rich sociocultural context of research behavior. The framework could be considered the next generation of citation analysis. This paper briefly reviews the history and features of content analysis in traditional social sciences, and its previous application in Library and Information Science. Based on critical discussion of the theoretical necessity of a new method as well as the limits of citation analysis, the nature and purposes of CCA are discussed, and potential procedures to conduct CCA, including principles to identify the reference scope, a two-dimensional (citing and cited) and two-modular (syntactic and semantic modules) codebook, are provided and described. Future works and implications are also suggested.
Obesity Heuristic, New Way On Artificial Immune Systems
Venue: arXiv cs.AI 2012
Year: 2012

There is a need for new metaphors from immunology to flourish the application areas of Artificial Immune Systems. A metaheuristic called Obesity Heuristic derived from advances in obesity treatment is proposed. The main forces of the algorithm are the generation omega-6 and omega-3 fatty acids. The algorithm works with Just-In-Time philosophy; by starting only when desired. A case study of data cleaning is provided. With experiments conducted on standard tables, results show that Obesity Heuristic outperforms other algorithms, with 100% recall. This is a great improvement over other algorithms
A Unified Framework for the Ergodic Capacity of Spectrum Sharing Cognitive Radio Systems
Venue: arXiv cs.IT 2012
Year: 2012

We consider a spectrum sharing communication scenario in which a primary and a secondary users are communicating, simultaneously, with their respective destinations using the same frequency carrier. Both optimal power profile and ergodic capacity are derived for fading channels, under an average transmit power and an instantaneous interference outage constraints. Unlike previous studies, we assume that the secondary user has a noisy version of the cross link and the secondary link Channel State Information (CSI). After deriving the capacity in this case, we provide an ergodic capacity generalization, through a unified expression, that encompasses several previously studied spectrum sharing settings. In addition, we provide an asymptotic capacity analysis at high and low signal-to-noise ratio (SNR). Numerical results, applied for independent Rayleigh fading channels, show that at low SNR regime, only the secondary channel estimation matters with no effect of the cross link on the capacity; whereas at high SNR regime, the capacity is rather driven by the cross link CSI. Furthermore, a practical on-off power allocation scheme is proposed and is shown, through numerical results, to achieve the full capacity at high and low SNR
Intrusion Detection on Smartphones
Venue: arXiv cs.CR 2012
Year: 2012

Smartphone technology is more and more becoming the predominant communication tool for people across the world. People use their smartphones to keep their contact data, to browse the internet, to exchange messages, to keep notes, carry their personal files and documents, etc. Users while browsing are also capable of shopping online, thus provoking a need to type their credit card numbers and security codes. As the smartphones are becoming widespread so do the security threats and vulnerabilities facing this technology. Recent news and articles indicate huge increase in malware and viruses for operating systems employed on smartphones (primarily Android and iOS). Major limitations of smartphone technology are its processing power and its scarce energy source since smartphones rely on battery usage. Since smartphones are devices which change their network location as the user moves between different places, intrusion detection systems for smartphone technology are most often classified as IDSs designed for mobile ad-hoc networks. The aim of this research is to give a brief overview of IDS technology, give an overview of major machine learning and pattern recognition algorithms used in IDS technologies, give an overview of security models of iOS and Android and propose a new host-based IDS model for smartphones and create proof-of-concept application for Android platform for the newly proposed model. Keywords: IDS, SVM, Android, iOS;
Refinement of the Sphere-Packing Bound: Asymmetric Channels
Venue: arXiv cs.IT 2012
Year: 2012

We provide a refinement of the sphere-packing bound for constant composition codes over asymmetric discrete memoryless channels that improves the pre-factor in front of the exponential term. The order of our pre-factor is $Ω(N^{-1/2(1+ε+ ρ_{R}^{\ast})})$ for any $ε>0$, where $ρ_{R}^{\ast}$ is the maximum absolute-value subdifferential of the sphere-packing exponent at rate $R$ and $N$ is the blocklength.
Various approaches to a human preference analysis in a digital signage display design
Venue: arXiv cs.HC 2012
Year: 2012

The paper is concerned with various ways of analysing the subjective assessment of displaying digital signage content. In the beginning the brief description of the signage system evolution is described and next, the carried out ex-periment is depicted. The preferences of the 32 subjects were obtained using pairwise comparisons of the designed screen formats. Then the priorities were derived by applying the Analytic Hierarchy Process (Saaty, 1977; 1980) framework. The gathered data were modelled and analysed by means of the analysis of variance, multiple regression, conjoint and factor analysis. The results suggest that the application of different methods of preference analysis may provide additional information, which could facilitate more in-depth understanding of the given preference structure.
User Defined Spreadsheet Functions in Excel
Venue: arXiv cs.SE 2012
Year: 2012

Creating user defined functions (UDFs) is a powerful method to improve the quality of computer applications, in particular spreadsheets. However, the only direct way to use UDFs in spreadsheets is to switch from the functional and declarative style of spreadsheet formulas to the imperative VBA, which creates a high entry barrier even for proficient spreadsheet users. It has been proposed to extend Excel by UDFs declared by a spreadsheet: user defined spreadsheet functions (UDSFs). In this paper we present a method to create a limited form of UDSFs in Excel without any use of VBA. Calls to those UDSFs utilize what-if data tables to execute the same part of a worksheet several times, thus turning it into a reusable function definition.