OpenRaiser/Intern-Atlas huggingface dataset:
On the information carried by programs about the objects they compute
Venue: arXiv cs.LO 2014
Year: 2014

In computability theory and computable analysis, finite programs can compute infinite objects. Presenting a computable object via any program for it, provides at least as much information as presenting the object itself, written on an infinite tape. What additional information do programs provide? We characterize this additional information to be any upper bound on the Kolmogorov complexity of the object. Hence we identify the exact relationship between Markov-computability and Type-2-computability. We then use this relationship to obtain several results characterizing the computational and topological structure of Markov-semidecidable sets.
Analysis of Boolean Functions based on Interaction Graphs and their influence in System Biology
Venue: arXiv cs.SY 2014
Year: 2014

Interaction graphs provide an important qualitative modeling approach for System Biology. This paper presents a novel approach for construction of interaction graph with the help of Boolean function decomposition. Each decomposition part (Consisting of 2-bits) of the Boolean functions has some important significance. In the dynamics of a biological system, each variable or node is nothing but gene or protein. Their regulation has been explored in terms of interaction graphs which are generated by Boolean functions. In this paper, different classes of Boolean functions with regards to Interaction Graph with biologically significant properties have been adumbrated.
A note on the longest common substring with $k$-mismatches problem
Venue: arXiv cs.DS 2014
Year: 2014

The recently introduced longest common substring with $k$-mismatches ($k$-LCF) problem is to find, given two sequences $S_1$ and $S_2$ of length $n$ each, a longest substring $A_1$ of $S_1$ and $A_2$ of $S_2$ such that the Hamming distance between $A_1$ and $A_2$ is at most $k$. So far, the only subquadratic time result for this problem was known for $k = 1$~\cite{FGKU2014}. We first present two output-dependent algorithms solving the $k$-LCF problem and show that for $k = O(\log^{1-\varepsilon} n)$, where $\varepsilon > 0$, at least one of them works in subquadratic time, using $O(n)$ words of space. The choice of one of these two algorithms to be applied for a given input can be done after linear time and space preprocessing. Finally we present a tabulation-based algorithm working, in its range of applicability, in $O(n^2\log\min(k+\ell_0, σ)/\log n)$ time, where $\ell_0$ is the length of the standard longest common substring.
Image Classification with A Deep Network Model based on Compressive Sensing
Venue: arXiv cs.CV 2014
Year: 2014

To simplify the parameter of the deep learning network, a cascaded compressive sensing model "CSNet" is implemented for image classification. Firstly, we use cascaded compressive sensing network to learn feature from the data. Secondly, CSNet generates the feature by binary hashing and block-wise histograms. Finally, a linear SVM classifier is used to classify these features. The experiments on the MNIST dataset indicate that higher classification accuracy can be obtained by this algorithm.
On Shor's Factoring Algorithm with More Registers and the Problem to Certify Quantum Computers
Venue: arXiv cs.DS 2014
Year: 2014

Shor's factoring algorithm uses two quantum registers. By introducing more registers we show that the measured numbers in these registers which are of the same pre-measurement state, should be equal if the original Shor's complexity argument is sound. This contradicts the argument that the second register has $r$ possible measured values. There is an anonymous comment which argues that the states in these registers are entangled. If so, the entanglement involving many quantum registers can not be interpreted by the mechanism of EPR pairs and the like. In view of this peculiar entanglement has not yet been mentioned and investigated, we think the claim that the Shor's algorithm runs in polynomial time needs more physical verifications. We also discuss the problem to certify quantum computers.
LP-decodable multipermutation codes
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we introduce a new way of constructing and decoding multipermutation codes. Multipermutations are permutations of a multiset that may consist of duplicate entries. We first introduce a new class of matrices called multipermutation matrices. We characterize the convex hull of multipermutation matrices. Based on this characterization, we propose a new class of codes that we term LP-decodable multipermutation codes. Then, we derive two LP decoding algorithms. We first formulate an LP decoding problem for memoryless channels. We then derive an LP algorithm that minimizes the Chebyshev distance. Finally, we show a numerical example of our algorithm.
A Higher-order Framework for Decision Problems and Games
Venue: arXiv cs.LO 2014
Year: 2014

We introduce a new unified framework for modelling both decision problems and finite games based on quantifiers and selection functions. We show that the canonical utility maximisation is one special case of a quantifier and that our more abstract framework provides several additional degrees of freedom in modelling. In particular, incomplete preferences, non-maximising heuristics, and context-dependent motives can be taken into account when describing an agent's goal. We introduce a suitable generalisation of Nash equilibrium for games in terms of quantifiers and selection functions. Moreover, we introduce a refinement of Nash that captures context-dependency of goals. Modelling in our framework is compositional as the parts of the game are modular and can be easily exchanged. We provide an extended example where we illustrate concepts and highlight the benefits of our alternative modelling approach.
Effect of LOS/NLOS Propagation on Area Spectral Efficiency and Energy Efficiency of Small-Cells
Venue: arXiv cs.NI 2014
Year: 2014

In this paper we investigate the effect of Line-of-Sight (LOS) and Non-Line-of-Sight (NLOS) propagation on the Area Spectral Efficiency (ASE) and on the energy efficiency of dense small-cell networks. We show that including both LOS and NLOS propagation in the path-loss model provides a completely different picture of the behaviours of ASE and energy efficiency than what would be observed in case of either LOS or NLOS propagation only. In particular, with combined LOS/NLOS path-loss, the ASE exhibits superlinear and sublinear behaviour at low and high cell densities, respectively. In addition, the energy efficiency as a function of the cell density has a global maximum and is not a monotonically increasing function like in case of LOS or NLOS propagation only. Based on our findings, we claim that Line-of-Sight (LOS) and Non-Line-of-Sight (NLOS) propagations play an important role in studying the performance of extremely dense small-cell networks.
Gradient-based Taxis Algorithms for Network Robotics
Venue: arXiv cs.RO 2014
Year: 2014

Finding the physical location of a specific network node is a prototypical task for navigation inside a wireless network. In this paper, we consider in depth the implications of wireless communication as a measurement input of gradient-based taxis algorithms. We discuss how gradients can be measured and determine the errors of this estimation. We then introduce a gradient-based taxis algorithm as an example of a family of gradient-based, convergent algorithms and discuss its convergence in the context of network robotics. We also conduct an exemplary experiment to show how to overcome some of the specific problems related to network robotics. Finally, we show how to adapt this framework to more complex objectives.
A (Somewhat Dated) Comparative Study of Betweenness Centrality Algorithms on GPU
Venue: arXiv cs.SI 2014
Year: 2014

The problem of computing the Betweenness Centrality (BC) is important in analyzing graphs in many practical applications like social networks, biological networks, transportation networks, electrical circuits, etc. Since this problem is computation intensive, researchers have been developing algorithms using high performance computing resources like supercomputers, clusters, and Graphics Processing Units (GPUs). Current GPU algorithms for computing BC employ Brandes' sequential algorithm with different trade-offs for thread scheduling, data structures, and atomic operations. In this paper, we study three GPU algorithms for computing BC of unweighted, directed, scale-free networks. We discuss and measure the trade-offs of their design choices about balanced thread scheduling, atomic operations, synchronizations and latency hiding. Our program is written in NVIDIA CUDA C and was tested on an NVIDIA Tesla M2050 GPU.
Input-Output Clustering Criterion (IOCC) for Optimizing Distributed Antenna Locations
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we propose an input-output space clustering criterion (IOCC) to optimize the locations of the remote antenna units (RAUs) of generalized Distributed Antenna Systems (DASs) under sum power constraint. In IOCC, the input space refers to RAU location space and output space refers to location specific ergodic capacity space for noise-limited environments. Given a location-specific arbitrary desired ergodic capacity function over a geographical area, we define the error as the difference between actual and desired ergodic capacity. Our investigations show that i) the IOCC provides an upper bound to the cell averaged ergodic capacity error; and ii) the derived upper bound is equal to a weighted quantization error function in location-capacity space (input-output space) and iii) the upper bound can be made arbitrarily small by a clustering process increasing the number of RAUs for a feasible DAS. IOCC converts the RAU location problem into a codebook design problem in vector quantization in input-output space, and thus includes the Squared Distance Criterion (SDC) for DAS in [15] (and other related papers) as a special case, which takes only the input space into account. Computer simulations confirm the theoretical findings and show that the IOCC outperforms the SDC for DAS in terms of the defined cell averaged "effective" ergodic capacity.
Computing downward closures for stacked counter automata
Venue: arXiv cs.FL 2014
Year: 2014

The downward closure of a language $L$ of words is the set of all (not necessarily contiguous) subwords of members of $L$. It is well known that the downward closure of any language is regular. Although the downward closure seems to be a promising abstraction, there are only few language classes for which an automaton for the downward closure is known to be computable. It is shown here that for stacked counter automata, the downward closure is computable. Stacked counter automata are finite automata with a storage mechanism obtained by \emph{adding blind counters} and \emph{building stacks}. Hence, they generalize pushdown and blind counter automata. The class of languages accepted by these automata are precisely those in the hierarchy obtained from the context-free languages by alternating two closure operators: imposing semilinear constraints and taking the algebraic extension. The main tool for computing downward closures is the new concept of Parikh annotations. As a second application of Parikh annotations, it is shown that the hierarchy above is strict at every level.
Architecture of Environmental Risk Modelling: for a faster and more robust response to natural disasters
Venue: arXiv cs.CE 2014
Year: 2014

Demands on the disaster response capacity of the European Union are likely to increase, as the impacts of disasters continue to grow both in size and frequency. This has resulted in intensive research on issues concerning spatially-explicit information and modelling and their multiple sources of uncertainty. Geospatial support is one of the forms of assistance frequently required by emergency response centres along with hazard forecast and event management assessment. Robust modelling of natural hazards requires dynamic simulations under an array of multiple inputs from different sources. Uncertainty is associated with meteorological forecast and calibration of the model parameters. Software uncertainty also derives from the data transformation models (D-TM) needed for predicting hazard behaviour and its consequences. On the other hand, social contributions have recently been recognized as valuable in raw-data collection and mapping efforts traditionally dominated by professional organizations. Here an architecture overview is proposed for adaptive and robust modelling of natural hazards, following the Semantic Array Programming paradigm to also include the distributed array of social contributors called Citizen Sensor in a semantically-enhanced strategy for D-TM modelling. The modelling architecture proposes a multicriteria approach for assessing the array of potential impacts with qualitative rapid assessment methods based on a Partial Open Loop Feedback Control (POLFC) schema and complementing more traditional and accurate a-posteriori assessment. We discuss the computational aspect of environmental risk modelling using array-based parallel paradigms on High Performance Computing (HPC) platforms, in order for the implications of urgency to be introduced into the systems (Urgent-HPC).
Modeling In vivo Wireless Path Loss
Venue: arXiv cs.OH 2014
Year: 2014

Our long-term research goal is to model the in vivo wireless channel. As a first step towards this goal, in this paper we performed in vivo path loss measurements at 2.4GHz and make a comparison with free space path loss. We calculate the path loss by using the electric field radiated by a Hertzian-Dipole located inside the abdominal cavity. The simulations quantify and confirm that the path loss falls more rapidly inside the body than outside the body. We also observe fluctuations of the path loss caused by the inhomogeneity of the human body. In comparison with the path loss measured with monopole antennas, we conclude that the significant variations in Received Signal Strength is caused by both the angular dependent path loss and the significantly modified in vivo antenna effects.
A Smart Cushion for Real-Time Heart Rate Monitoring
Venue: arXiv cs.OH 2014
Year: 2014

This paper presents a smart cushion for real time heart rate monitoring. The cushion comprises of an integrated micro-bending fiber sensor, which records the BCG (Ballistocardiogram) signal without direct skin-electrode contact, and an optical transceiver that does signal amplification, digitization, and pre-filtering. To remove the artifacts and extract heart rate from BCG signal, a computationally efficient heart rate detection algorithm is developed. The system doesn't require any pre-training and is highly responsive with the outputs updated every 3 sec and initial response within first 10 sec. Tests conducted on human subjects show the detected heart rate closely matches the one from a commercial SpO2 device.
Detecting Behavioral and Structural Anomalies in MediaCloud Applications
Venue: arXiv cs.CR 2014
Year: 2014

In the past years technological advances such as the increasing bandwidth in network infrastructures and new software developments such as message and agent-based systems gave rise to the field of cloud technologies, which have evolved from abstract concepts to concrete solutions, ranging from flexible, platform-independent systems to highly specialized software solutions. In this paper we introduce and evaluate two anomaly detection methods to achieve a higher level of security in a specific cloud solution for interactive media, the Media Cloud from Alcatel-Lucent. The Media Cloud focuses on real-time processing of interactive media applications, allowing for optimal resource planning using highly specific functional components. The proposed anomaly detection methods are designed to work complimentary to each other and are capable of detecting known and unknown vulnerabilities and security issues, offering very low false positive rates and very high detection rates, as is shown by the evaluation on real Media Cloud data and synthetic data. The proposed methods use behavioral and structural features, and are capable of locating the detected anomalies as well, giving the executing analyst easy insight into the running processes.
Workflow Partitioning and Deployment on the Cloud using Orchestra
Venue: arXiv cs.DC 2014
Year: 2014

Orchestrating service-oriented workflows is typically based on a design model that routes both data and control through a single point - the centralised workflow engine. This causes scalability problems that include the unnecessary consumption of the network bandwidth, high latency in transmitting data between the services, and performance bottlenecks. These problems are highly prominent when orchestrating workflows that are composed from services dispersed across distant geographical locations. This paper presents a novel workflow partitioning approach, which attempts to improve the scalability of orchestrating large-scale workflows. It permits the workflow computation to be moved towards the services providing the data in order to garner optimal performance results. This is achieved by decomposing the workflow into smaller sub workflows for parallel execution, and determining the most appropriate network locations to which these sub workflows are transmitted and subsequently executed. This paper demonstrates the efficiency of our approach using a set of experimental workflows that are orchestrated over Amazon EC2 and across several geographic network regions.
Short-Term Predictability of Photovoltaic Production over Italy
Venue: arXiv cs.LG 2014
Year: 2014

Photovoltaic (PV) power production increased drastically in Europe throughout the last years. About the 6% of electricity in Italy comes from PV and for an efficient management of the power grid an accurate and reliable forecasting of production would be needed. Starting from a dataset of electricity production of 65 Italian solar plants for the years 2011-2012 we investigate the possibility to forecast daily production from one to ten days of lead time without using on site measurements. Our study is divided in two parts: an assessment of the predictability of meteorological variables using weather forecasts and an analysis on the application of data-driven modelling in predicting solar power production. We calibrate a SVM model using available observations and then we force the same model with the predicted variables from weather forecasts with a lead time from one to ten days. As expected, solar power production is strongly influenced by cloudiness and clear sky, in fact we observe that while during summer we obtain a general error under the 10% (slightly lower in south Italy), during winter the error is abundantly above the 20%.
On Searching Zimin Patterns
Venue: arXiv cs.DM 2014
Year: 2014

In the area of pattern avoidability the central role is played by special words called Zimin patterns. The symbols of these patterns are treated as variables and the rank of the pattern is its number of variables. Zimin type of a word $x$ is introduced here as the maximum rank of a Zimin pattern matching $x$. We show how to compute Zimin type of a word on-line in linear time. Consequently we get a quadratic time, linear-space algorithm for searching Zimin patterns in words. Then we how the Zimin type of the length $n$ prefix of the infinite Fibonacci word is related to the representation of $n$ in the Fibonacci numeration system. Using this relation, we prove that Zimin types of such prefixes and Zimin patterns inside them can be found in logarithmic time. Finally, we give some bounds on the function $f(n,k)$ such that every $k$-ary word of length at least $f(n,k)$ has a factor that matches the rank $n$ Zimin pattern.
About accuracy of the solution of NP-complete tasks
Venue: arXiv cs.CC 2014
Year: 2014

On example of tasks of class NP the questions concerning accuracy of work of already existing and possible in the future algorithms for the solution of tasks on discrete structures are considered.
A Bayesian Tensor Factorization Model via Variational Inference for Link Prediction
Venue: arXiv cs.LG 2014
Year: 2014

Probabilistic approaches for tensor factorization aim to extract meaningful structure from incomplete data by postulating low rank constraints. Recently, variational Bayesian (VB) inference techniques have successfully been applied to large scale models. This paper presents full Bayesian inference via VB on both single and coupled tensor factorization models. Our method can be run even for very large models and is easily implemented. It exhibits better prediction performance than existing approaches based on maximum likelihood on several real-world datasets for missing link prediction problem.
Reclaiming human machine nature
Venue: arXiv cs.HC 2014
Year: 2014

Extending and modifying his domain of life by artifact production is one of the main characteristics of humankind. From the first hominid, who used a wood stick or a stone for extending his upper limbs and augmenting his gesture strength, to current systems engineers who used technologies for augmenting human cognition, perception and action, extending human body capabilities remains a big issue. From more than fifty years cybernetics, computer and cognitive sciences have imposed only one reductionist model of human machine systems: cognitive systems. Inspired by philosophy, behaviorist psychology and the information treatment metaphor, the cognitive system paradigm requires a function view and a functional analysis in human systems design process. According that design approach, human have been reduced to his metaphysical and functional properties in a new dualism. Human body requirements have been left to physical ergonomics or "physiology". With multidisciplinary convergence, the issues of "human-machine" systems and "human artifacts" evolve. The loss of biological and social boundaries between human organisms and interactive and informational physical artifact questions the current engineering methods and ergonomic design of cognitive systems. New developpment of human machine systems for intensive care, human space activities or bio-engineering sytems requires grounding human systems design on a renewed epistemological framework for future human systems model and evidence based "bio-engineering". In that context, reclaiming human factors, augmented human and human machine nature is a necessity
Converting Reconfigurable Petri Nets to Maude
Venue: arXiv cs.FL 2014
Year: 2014

Model checking is an important aim of the theoretical computer science. It enables the verification of a model with a set of properties such as liveness, deadlock or safety. One of the typical modelling techniques are Petri nets they are well understood and can be used for a model checking. Reconfigurable Petri nets are based on a Petri nets with a set of rules. These rules can be used dynamically to change the net. Missing is the possibility to verify a reconfigurable net and properties such as deadlocks or liveness. This paper introduces a conversion from reconfigurable Petri net to Maude, that allows us to fill the gap. It presents a net transformation approach which is based on Maude's equation- and rewrite logic as well as the LTLR model checker.