OpenRaiser/Intern-Atlas huggingface dataset:
A Reconfigurable USAR Robot Designed for Traversing Complex 3D Terrain
Venue: arXiv cs.RO 2015
Year: 2015

The use of robotics in Urban Search and Rescue (USAR) is growing steadily from their initial inception during the 2001 World Trade Centre incident. Despite years of progress, the core design of robots currently in use for USAR purposes has deviated little, favoring software and control development and optimization of the basic robot template to improve performance instead. Presented here is a novel design description of the Cricket, an advanced robot with a broader range of physical capabilities than traditional USAR robots. By incorporating the tracked structure of earlier robots, appreciated for energy efficiency and robustness, into a multi-limbed walking design, the Cricket enables the use of advanced locomotion techniques. The ability to climb over obstacles many times the height of the robot, ascend vertical shafts without the assistance of a tether, and traverse rough and near vertical terrain improves the Cricket's capability to successfully locate victims in confined spaces.
Towards Security of Additive Layer Manufacturing
Venue: arXiv cs.CR 2015
Year: 2015

Additive Layer Manufacturing (ALM), also broadly known as 3D printing, is a new technology to produce 3D objects. As an opposite approach to the conventional subtractive manufacturing process, 3D objects are created by adding thin material layers over layers. Until recently, they have been used, mainly, for plastic models. However, the technology has evolved making it possible to use high-quality printing with metal alloys. Agencies and companies like NASA, ESA, Boeing, Airbus, etc. are investigating various ALM technology application areas. Recently, SpaceX used additive manufacturing to produce engine chambers for the newest Dragon spacecraft. BAE System plans to print on-demand a complete Unmanned Aerial Vehicle (UAV), depending on the operational requirements. Companies expect the implementation of ALM technology will bring a broad variety of technological and economic benefits. This includes, but not limited to, the reduction of the time needed to produce complex parts, reduction of wasted material and thus control of production costs along with minimization of part storage space as companies implement just-in-time and on-demand production solutions. The broad variety of application areas and a high grade of computerization of the manufacturing process will inevitably make ALM an attractive target for various attacks.
Social and Collaborative Services for Organizations: Back to Requirements
Venue: arXiv cs.CY 2015
Year: 2015

Social and collaborative services have widely spread within the enterprises as they play a part in improving productivity and business outcomes. However, the deployment of these services fluctuates between success and failure. This paper intends to assess their deployment and how they can contribute to value creation in different industries. We investigate the relationship between the services' functionalities and the organizational requirement of these services represented by the coordination. We also consider the organizational transformation driven by servitization and emphasize its impact on the act of coordination. We highlight the tight correlation between the functionalities and the requirement in organic forms which suggests a successful deployment in such enterprises. We nonetheless find that, when the servitization is a strategic intent in organizations with mechanistic characteristics, deploying social and collaborative services can contribute to achieving this aim.
Atomic Read/Write Memory in Signature-free Byzantine Asynchronous Message-passing Systems
Venue: arXiv cs.DC 2015
Year: 2015

This article presents a signature-free distributed algorithm which builds an atomic read/write shared memory on top of an $n$-process asynchronous message-passing system in which up to $t<n/3$ processes may commit Byzantine failures. From a conceptual point of view, this algorithm is designed to be as close as possible to the algorithm proposed by Attiya, Bar-Noy and Dolev (JACM 1995), which builds an atomic register in an $n$-process asynchronous message-passing system where up to $t<n/2$ processes may crash. The proposed algorithm is particularly simple. It does not use cryptography to cope with Byzantine processes, and is optimal from a $t$-resilience point of view ($t<n/3$). A read operation requires $O(n)$ messages, and a write operation requires $O(n^2)$ messages.
Notes on phonological based drunken detection algorithm
Venue: arXiv cs.CY 2015
Year: 2015

In this paper we propose a new algorithm for detecting if a person is under the influence of alcohol. This algorithm is based on number of pauses the speaker makes by judging that if the number of pauses compared to the previous recordings of the same person, which has been recorded beforehand, is higher. If so the algorithm mark the speaker as drunk.
A New Approach for a Better Load Balancing and a Better Distribution of Resources in Cloud Computing
Venue: arXiv cs.DC 2015
Year: 2015

Cloud computing is a new paradigm where data and services of Information Technology are provided via the Internet by using remote servers. It represents a new way of delivering computing resources allowing access to the network on demand. Cloud computing consists of several services, each of which can hold several tasks. As the problem of scheduling tasks is an NP-complete problem, the task management can be an important element in the technology of cloud computing. To optimize the performance of virtual machines hosted in cloud computing, several algorithms of scheduling tasks have been proposed. In this paper, we present an approach allowing to solve the problem optimally and to take into account the QoS constraints based on the different user requests. This technique, based on the Branch and Bound algorithm, allows to assign tasks to different virtual machines while ensuring load balance and a better distribution of resources. The experimental results show that our approach gives very promising results for an effective tasks planning. - See more at: http://thesai.org/Publications/ViewPaper?Volume=6&Issue=10&Code=IJACSA&SerialNo=36#sthash.aV1fxMaQ.dpuf
FOSS-Based Grid Computing
Venue: arXiv cs.DC 2015
Year: 2015

In this expository paper we will be primarily concerned with core aspects of Grids and Grid computing using free and open-source software with some emphasis on utility computing. It is based on a technical report entitled 'Grid-Computing Using GNU/Linux' by the present author. This article was written in 2006 and should be of historical interest.
The Minimum Backlog Problem
Venue: arXiv cs.DS 2016
Year: 2016

We study the minimum backlog problem (MBP). This online problem arises, e.g., in the context of sensor networks. We focus on two main variants of MBP. The discrete MBP is a 2-person game played on a graph $G=(V,E)$. The player is initially located at a vertex of the graph. In each time step, the adversary pours a total of one unit of water into cups that are located on the vertices of the graph, arbitrarily distributing the water among the cups. The player then moves from her current vertex to an adjacent vertex and empties the cup at that vertex. The player's objective is to minimize the backlog, i.e., the maximum amount of water in any cup at any time. The geometric MBP is a continuous-time version of the MBP: the cups are points in the two-dimensional plane, the adversary pours water continuously at a constant rate, and the player moves in the plane with unit speed. Again, the player's objective is to minimize the backlog. We show that the competitive ratio of any algorithm for the MBP has a lower bound of $Ω(D)$, where $D$ is the diameter of the graph (for the discrete MBP) or the diameter of the point set (for the geometric MBP). Therefore we focus on determining a strategy for the player that guarantees a uniform upper bound on the absolute value of the backlog. For the absolute value of the backlog there is a trivial lower bound of $Ω(D)$, and the deamortization analysis of Dietz and Sleator gives an upper bound of $O(D\log N)$ for $N$ cups. Our main result is a tight upper bound for the geometric MBP: we show that there is a strategy for the player that guarantees a backlog of $O(D)$, independently of the number of cups.
About the impossibility to prove P=NP and the pseudo-randomness in NP
Venue: arXiv cs.CC 2016
Year: 2016

The relationship between the complexity classes P and NP is an unsolved question in the field of theoretical computer science. In this paper, we look at the link between the P - NP question and the "Deterministic" versus "Non Deterministic" nature of a problem, and more specifically at the temporal nature of the complexity within the NP class of problems. Let us remind that the NP class is called the class of "Non Deterministic Polynomial" languages. Using the meta argument that results in Mathematics should be "time independent" as they are reproducible, the paper shows that the P!=NP assertion is impossible to prove in the a-temporal framework of Mathematics. In a previous version of the report, we use a similar argument based on randomness to show that the P = NP assertion was also impossible to prove, but this part of the paper was shown to be incorrect. So, this version deletes it. In fact, this paper highlights the time dependence of the complexity for any NP problem, linked to some pseudo-randomness in its heart.
Optimal quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks
Venue: arXiv cs.CR 2016
Year: 2016

Recently, an image scrambling encryption algorithm of pixel bit based on chaos map was proposed. Considering the algorithm as a typical binary image scrambling/permutation algorithm exerting on plaintext of size $M\times (8N)$, this paper proposes a novel optimal method to break it with some known/chosen-plaintexts. The spatial complexity and computational complexity of the attack are only $O(32\cdot MN)$ and $O(16\cdot n_0\cdot MN)$ respectively, where $n_0$ is the number of known/chosen-plaintexts used. The method can be easily extended to break any permutation-only encryption scheme exerting on plaintext of size $M\times N$ and with $L$ different levels of values. The corresponding spatial complexity and computational complexity are only $O(MN)$ and $O(\lceil\log_L(MN)\rceil \cdot MN)$ respectively. In addition, some specific remarks on the performance of the image scrambling encryption algorithm are presented.
Connectivity graphs of uncertainty regions
Venue: arXiv cs.CG 2016
Year: 2016

We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorable Best-Case Uncertainty (BU), each input point can be chosen from a given set to yield the best possible objective value. In the unfavorable Worst-Case Uncertainty (WU), the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the following Best-Case Connectivity with Uncertainty (BCU) problem: Given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there are n+k regions, where k of the regions are line segments and n of the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the corresponding Worst-Case Connectivity with Uncertainty (WCU) problem: Given a set of uncertainty regions, find the minimal distance r such that for any choice of points, one per region, there is a spanning tree among the points with edge length at most r.
Representations of task assignments in distributed systems using Young tableaux and symmetric groups
Venue: arXiv cs.DC 2016
Year: 2016

This paper presents a novel approach to representing task assignments for partitioned agents (respectively, tasks) in distributed systems. A partition of agents (respectively, tasks) is represented by a Young tableau, which is one of the main tools in studying symmetric groups and combinatorics. In this paper we propose a task, agent, and assignment tableau in order to represent a task assignment for partitioned agents (respectively, tasks) in a distributed system. This paper is concerned with representations of task assignments rather than finding approximate or near optimal solutions for task assignments. A Young tableau approach allows us to raise the expressiveness of partitioned agents (respectively, tasks) and their task assignments.
Finding of k in Fagin's R. Theorem 24
Venue: arXiv cs.CC 2016
Year: 2016

By using of analytical multi-logic expresses in conjunction with non-deterministic Turing machine the proposition was proved that algorithm of deterministic Turing counter machine of polynomial time complexity can be decreased to the algorithm of linear time complexity in non-deterministic Turing counter machine. Furthermore, it was shown that existence of reduction of polynomial time complexity to the linear time complexity by switching from deterministic to non-deterministic Turing machine for string recognition imply P equals to NP. Analytical generation functions of higher order logic were used for finding of k value in Fagin's R. Theorem 24.
Abstracting Path Conditions
Venue: arXiv cs.SE 2016
Year: 2016

We present a symbolic-execution-based algorithm that for a given program and a given program location produces a nontrivial necessary condition on input values to drive the program execution to the given location. We also propose an application of necessary conditions in contemporary bug-finding and test-generation tools. Experimental results show that the presented technique can significantly improve performance of the tools.
Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
Venue: arXiv cs.DM 2016
Year: 2016

Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006) establish a beautiful picture for the computational complexity of approximating the partition function of the hard-core model. Let $λ_c(T_Δ)$ denote the critical activity for the hard-model on the infinite $Δ$-regular tree. Weitz presented an FPTAS for the partition function when $λ<λ_c(T_Δ)$ for graphs with constant maximum degree $Δ$. In contrast, Sly showed that for all $Δ\geq 3$, there exists $ε_Δ>0$ such that (unless RP=NP) there is no FPRAS for approximating the partition function on graphs of maximum degree $Δ$ for activities $λ$ satisfying $λ_c(T_Δ)<λ<λ_c(T_Δ)+ε_Δ$. We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Recent results of Li et al. and Sinclair et al. extend Weitz's approach to any 2-spin model, which includes the antiferromagnetic Ising model, to yield an FPTAS for the partition function for all graphs of constant maximum degree $Δ$ when the parameters of the model lie in the uniqueness regime of the infinite tree $T_Δ$. We prove the complementary result that for the antiferrogmanetic Ising model without external field that, unless RP=NP, for all $Δ\geq 3$, there is no FPRAS for approximating the partition function on graphs of maximum degree $Δ$ when the inverse temperature lies in the non-uniqueness regime of the infinite tree $T_Δ$. Our results extend to a region of the parameter space for general 2-spin models. Our proof works by relating certain second moment calculations for random $Δ$-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.
Marginal multi-Bernoulli filters: RFS derivation of MHT, JIPDA and association-based MeMBer
Venue: arXiv cs.SY 2016
Year: 2016

Recent developments in random finite sets (RFSs) have yielded a variety of tracking methods that avoid data association. This paper derives a form of the full Bayes RFS filter and observes that data association is implicitly present, in a data structure similar to MHT. Subsequently, algorithms are obtained by approximating the distribution of associations. Two algorithms result: one nearly identical to JIPDA, and another related to the MeMBer filter. Both improve performance in challenging environments.
What is the least number of moves needed to solve the k-peg Towers of Hanoi problem?
Venue: arXiv cs.DM 2016
Year: 2016

We prove that the solutions to the k-peg Tower of Hanoi Problem given by Frame and Stewart are minimal.
Science Visualization and Discursive Knowledge
Venue: arXiv cs.CY 2016
Year: 2016

Positional and relational perspectives on network data have led to two different research traditions in textual analysis and social network analysis, respectively. Latent Semantic Analysis (LSA) focuses on the latent dimensions in textual data; social network analysis (SNA) on the observable networks. The two coupled topographies of information-processing in the network space and meaning-processing in the vector space operate with different (nonlinear) dynamics. The historical dynamics of information processing in observable networks organizes the system into instantiations; the systems dynamics, however, can be considered as self-organizing in terms of fluxes of communication along the various dimensions that operate with different codes. The development over time adds evolutionary differentiation to the historical integration; a richer structure can process more complexity.
Using Tableau to Decide Description Logics with Full Role Negation and Identity
Venue: arXiv cs.LO 2016
Year: 2016

This paper presents a tableau approach for deciding expressive description logics with full role negation and role identity. We consider the description logic ALBOid, which is the extension of ALC with the Boolean role operators, inverse of roles, the identity role, and includes full support for individuals and singleton concepts. ALBOid is expressively equivalent to the two-variable fragment of first-order logic with equality and subsumes Boolean modal logic. In this paper we define a sound and complete tableau calculus for the ALBOid that provides a basis for decision procedures for this logic and all its sublogics. An important novelty of our approach is the use of a generic unrestricted blocking mechanism. Being based on a conceptually simple rule, unrestricted blocking performs case distinctions over whether two individuals are equal or not and equality reasoning to find finite models. The blocking mechanism ties the proof of termination of tableau derivations to the finite model property of ALBOid.
Completely reducible sets
Venue: arXiv cs.FL 2016
Year: 2016

We study the family of rational sets of words, called completely reducible and which are such that the syntactic representation of their characteristic series is completely reducible. This family contains, by a result of Reutenauer, the submonoids generated by bifix codes and, by a result of Berstel and Reutenauer, the cyclic sets. We study the closure properties of this family. We prove a result on linear representations of monoids which gives a generalization of the result concerning the complete reducibility of the submonoid generated by a bifix code to sets called birecurrent. We also give a new proof of the result concerning cyclic sets.
Computation in Multicast Networks: Function Alignment and Converse Theorems
Venue: arXiv cs.IT 2016
Year: 2016

The classical problem in network coding theory considers communication over multicast networks. Multiple transmitters send independent messages to multiple receivers which decode the same set of messages. In this work, computation over multicast networks is considered: each receiver decodes an identical function of the original messages. For a countably infinite class of two-transmitter two-receiver single-hop linear deterministic networks, the computing capacity is characterized for a linear function (modulo-2 sum) of Bernoulli sources. Inspired by the geometric concept of interference alignment in networks, a new achievable coding scheme called function alignment is introduced. A new converse theorem is established that is tighter than cut-set based and genie-aided bounds. Computation (vs. communication) over multicast networks requires additional analysis to account for multiple receivers sharing a network's computational resources. We also develop a network decomposition theorem which identifies elementary parallel subnetworks that can constitute an original network without loss of optimality. The decomposition theorem provides a conceptually-simpler algebraic proof of achievability that generalizes to $L$-transmitter $L$-receiver networks.
Underapproximation of Procedure Summaries for Integer Programs
Venue: arXiv cs.PL 2016
Year: 2016

We show how to underapproximate the procedure summaries of recursive programs over the integers using off-the-shelf analyzers for non-recursive programs. The novelty of our approach is that the non-recursive program we compute may capture unboundedly many behaviors of the original recursive program for which stack usage cannot be bounded. Moreover, we identify a class of recursive programs on which our method terminates and returns the precise summary relations without underapproximation. Doing so, we generalize a similar result for non-recursive programs to the recursive case. Finally, we present experimental results of an implementation of our method applied on a number of examples.
Breaking a novel image encryption scheme based on improved hyperchaotic sequences
Venue: arXiv cs.CR 2016
Year: 2016

Recently, a novel image encryption scheme based on improved hyperchaotic sequences was proposed. A pseudo-random number sequence, generated by a hyper-chaos system, is used to determine two involved encryption functions, bitwise exclusive or (XOR) operation and modulo addition. It was reported that the scheme can be broken with some pairs of chosen plain-images and the corresponding cipherimages. This paper re-evaluates the security of the encryption scheme and finds that the encryption scheme can be broken with only one known plain-image. The performance of the known-plaintext attack, in terms of success probability and computation load, become even much better when two known plain-images are available. In addition, security defects on insensitivity of the encryption result with respect to changes of secret key and plain-image are also reported.
Exact Recovery of Sparse Signals via Orthogonal Matching Pursuit: How Many Iterations Do We Need?
Venue: arXiv cs.IT 2016
Year: 2016

Orthogonal matching pursuit (OMP) is a greedy algorithm widely used for the recovery of sparse signals from compressed measurements. In this paper, we analyze the number of iterations required for the OMP algorithm to perform exact recovery of sparse signals. Our analysis shows that OMP can accurately recover all $K$-sparse signals within $\lceil 2.8 K \rceil$ iterations when the measurement matrix satisfies a restricted isometry property (RIP). Our result improves upon the recent result of Zhang and also bridges the gap between Zhang's result and the fundamental limit of OMP at which exact recovery of $K$-sparse signals cannot be uniformly guaranteed.