OpenRaiser/Intern-Atlas huggingface dataset:
Fourier-Laguerre transform, convolution and wavelets on the ball
Venue: arXiv cs.IT 2013
Year: 2013

We review the Fourier-Laguerre transform, an alternative harmonic analysis on the three-dimensional ball to the usual Fourier-Bessel transform. The Fourier-Laguerre transform exhibits an exact quadrature rule and thus leads to a sampling theorem on the ball. We study the definition of convolution on the ball in this context, showing explicitly how translation on the radial line may be viewed as convolution with a shifted Dirac delta function. We review the exact Fourier-Laguerre wavelet transform on the ball, coined flaglets, and show that flaglets constitute a tight frame.
Making simple proofs simpler
Venue: arXiv cs.MS 2013
Year: 2013

An open partition π [Cod09a, Cod09b] of a tree T is a partition of the vertices of T with the property that, for each block B of π, the upset of B is a union of blocks of π. This paper deals with the number, NP(n), of open partitions of the tree, V_n, made of two chains with n points each, that share the root.
Clustering of Complex Networks and Community Detection Using Group Search Optimization
Venue: arXiv cs.NE 2013
Year: 2013

Group Search Optimizer(GSO) is one of the best algorithms, is very new in the field of Evolutionary Computing. It is very robust and efficient algorithm, which is inspired by animal searching behaviour. The paper describes an application of GSO to clustering of networks. We have tested GSO against five standard benchmark datasets, GSO algorithm is proved very competitive in terms of accuracy and convergence speed.
Lempel-Ziv Parsing in External Memory
Venue: arXiv cs.DS 2013
Year: 2013

For decades, computing the LZ factorization (or LZ77 parsing) of a string has been a requisite and computationally intensive step in many diverse applications, including text indexing and data compression. Many algorithms for LZ77 parsing have been discovered over the years; however, despite the increasing need to apply LZ77 to massive data sets, no algorithm to date scales to inputs that exceed the size of internal memory. In this paper we describe the first algorithm for computing the LZ77 parsing in external memory. Our algorithm is fast in practice and will allow the next generation of text indexes to be realised for massive strings and string collections.
Fundamentals of Heterogeneous Cellular Networks with Energy Harvesting
Venue: arXiv cs.IT 2013
Year: 2013

We develop a new tractable model for K-tier heterogeneous cellular networks (HetNets), where each base station (BS) is powered solely by a self-contained energy harvesting module. The BSs across tiers differ in terms of the energy harvesting rate, energy storage capacity, transmit power and deployment density. Since a BS may not always have enough energy, it may need to be kept OFF and allowed to recharge while nearby users are served by neighboring BSs that are ON. We show that the fraction of time a k^{th} tier BS can be kept ON, termed availability ρ_k, is a fundamental metric of interest. Using tools from random walk theory, fixed point analysis and stochastic geometry, we characterize the set of K-tuples (ρ_1, ρ_2, ... ρ_K), termed the availability region, that is achievable by general uncoordinated operational strategies, where the decision to toggle the current ON/OFF state of a BS is taken independently of the other BSs. If the availability vector corresponding to the optimal system performance, e.g., in terms of rate, lies in this availability region, there is no performance loss due to the presence of unreliable energy sources. As a part of our analysis, we model the temporal dynamics of the energy level at each BS as a birth-death process, derive the energy utilization rate, and use hitting/stopping time analysis to prove that there exists a fundamental limit on ρ_k that cannot be surpassed by any uncoordinated strategy.
Using MathML to Represent Units of Measurement for Improved Ontology Alignment
Venue: arXiv cs.AI 2013
Year: 2013

Ontologies provide a formal description of concepts and their relationships in a knowledge domain. The goal of ontology alignment is to identify semantically matching concepts and relationships across independently developed ontologies that purport to describe the same knowledge. In order to handle the widest possible class of ontologies, many alignment algorithms rely on terminological and structural meth- ods, but the often fuzzy nature of concepts complicates the matching process. However, one area that should provide clear matching solutions due to its mathematical nature, is units of measurement. Several on- tologies for units of measurement are available, but there has been no attempt to align them, notwithstanding the obvious importance for tech- nical interoperability. We propose a general strategy to map these (and similar) ontologies by introducing MathML to accurately capture the semantic description of concepts specified therein. We provide mapping results for three ontologies, and show that our approach improves on lexical comparisons.
An efficient reconciliation algorithm for social networks
Venue: arXiv cs.DS 2013
Year: 2013

People today typically use multiple online social networks (Facebook, Twitter, Google+, LinkedIn, etc.). Each online network represents a subset of their "real" ego-networks. An interesting and challenging problem is to reconcile these online networks, that is, to identify all the accounts belonging to the same individual. Besides providing a richer understanding of social dynamics, the problem has a number of practical applications. At first sight, this problem appears algorithmically challenging. Fortunately, a small fraction of individuals explicitly link their accounts across multiple networks; our work leverages these connections to identify a very large fraction of the network. Our main contributions are to mathematically formalize the problem for the first time, and to design a simple, local, and efficient parallel algorithm to solve it. We are able to prove strong theoretical guarantees on the algorithm's performance on well-established network models (Random Graphs, Preferential Attachment). We also experimentally confirm the effectiveness of the algorithm on synthetic and real social network data sets.
Linear-time generation of specifiable combinatorial structures: general theory and first examples
Venue: arXiv cs.DS 2013
Year: 2013

Various specifiable combinatorial structures, with d extensive parameters, can be exactly sampled both by the recursive method, with linear arithmetic complexity if a heavy preprocessing is performed, or by the Boltzmann method, with complexity Theta(n^{1+d/2}). We discuss a modified recursive method, crucially based on the asymptotic expansion of the associated saddle-point integrals, which can be adopted for a large number of such structures (e.g. partitions, permutations, lattice walks, trees, random graphs, all with a variety of prescribed statistics and/or constraints). The new algorithm requires no preprocessing, still it has linear complexity on average. In terms of bit complexity, instead of arithmetic, we only have extra logarithmic factors. For many families of structures, this provides, at our knowledge, the only known quasi-linear generators. We present the general theory, and detail a specific example: the partitions of n elements into k non-empty blocks, counted by the Stirling numbers of the second kind. These objects are involved in the exact sampling of minimal automata with prescribed alphabet size and number of states, which is thus performed here with average Theta(n ln n) bit complexity, outbreaking all previously known Theta(n^{3/2}) algorithms.
TEXIVE: Detecting Drivers Using Personal Smart Phones by Leveraging Inertial Sensors
Venue: arXiv cs.NI 2013
Year: 2013

In this work, we address a fundamental and critical task of detecting the behavior of driving and texting using smartphones carried by users. We propose, design, and implement TEXIVE that leverages various sensors integrated in the smartphone and realizes our goal of distinguishing drivers and passengers and detecting texting using rich user micro-movements and irregularities that can be detected by sensors in the phone before and during driving and texting. Without relying on external infrastructure, TEXIVE has an advantage of being readily implemented and adopted, while at the same time raising a number of challenges that need to be carefully addressed for achieving a successful detection with good sensitivity, specificity, accuracy, and precision. Our system distinguishes the driver and passengers by detecting whether a user is entering a vehicle or not, inferring which side of the vehicle s/he is entering, reasoning whether the user is siting in front or rear seats, and discovering if a user is texting by fusing multiple evidences collected from accelerometer, magnetometer, and gyroscope sensors. To validate our approach, we conduct extensive experiments with several users on various vehicles and smartphones. Our evaluation results show that TEXIVE has a classification accuracy of 87.18%, and precision of 96.67%.
PROOFTOOL: a GUI for the GAPT Framework
Venue: arXiv cs.LO 2013
Year: 2013

This paper introduces PROOFTOOL, the graphical user interface for the General Architecture for Proof Theory (GAPT) framework. Its features are described with a focus not only on the visualization but also on the analysis and transformation of proofs and related tree-like structures, and its implementation is explained. Finally, PROOFTOOL is compared with three other graphical interfaces for proofs.
OntoFM: A Personal Ontology-based File Manager for the Desktop
Venue: arXiv cs.HC 2013
Year: 2013

Personal ontologies have been proposed as a means to support the semantic management of user information. Assuming that a personal ontology system is in use, new tools have to be developed at user interface level to exploit the enhanced capabilities offered by the system. In this work, we present an ontology-based file manager that allows semantic searching on the user's personal information space. The file manager exploits the ontology relations to present files associated with specific concepts, proposes new related concepts to users, and helps them explore the information space and locate the required file.
Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculi
Venue: arXiv cs.LO 2013
Year: 2013

The Asynchronous pi-calculus, proposed by Honda and Tokoro (1991) and, independently, by Boudol (1992), is a subset of the pi-calculus (Milner, 1992) which contains no explicit operators for choice and output-prefixing. The communication mechanism of this calculus, however, is powerful enough to simulate output-prefixing, as shown by Honda and Tokoro (1991) and by Boudol (1992), and input-guarded choice, as shown by Nestmann and Pierce (2000). A natural question arises, then, whether or not it is as expressive as the full pi-calculus. We show that this is not the case. More precisely, we show that there does not exist any uniform, fully distributed translation from the pi-calculus into the asynchronous pi-calculus, up to any "reasonable" notion of equivalence. This result is based on the incapability of the asynchronous pi-calculus to break certain symmetries possibly present in the initial communication graph. By similar arguments, we prove a separation result between the pi-calculus and CCS, and between the pi-calculus and the pi-calculus with internal mobility, a subset of the pi-calculus proposed by Sangiorgi where the output actions can only transmit private names.
Efficiently determining Convergence in Polynomial Recurrence Sequences
Venue: arXiv cs.DM 2013
Year: 2013

We derive the necessary and sufficient condition, for a given Polynomial Recurrence Sequence to converge to a given target rational K. By converge, we mean that the Nth term of the sequence, is equal to K, as N tends to positive infinity. The basic idea of our approach is to construct a univariate polynomial equation in x, whose coefficients correspond to the terms of the Sequence. The approach then obtains the condition by analyzing five cases that cover all possible real values of x. The condition can be evaluated within time that is a polynomial function of the size of the description of the Polynomial Recurrence Sequence, hence convergence or non-convergence can be efficiently determined.
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
Venue: arXiv cs.DS 2013
Year: 2013

Given two graphs $H$ and $G$, the Subgraph Isomorphism problem asks if $H$ is isomorphic to a subgraph of $G$. While NP-hard in general, algorithms exist for various parameterized versions of the problem: for example, the problem can be solved (1) in time $2^{O(|V(H)|)}\cdot n^{O(\tw(H))}$ using the color-coding technique of Alon, Yuster, and Zwick; (2) in time $f(|V(H)|,\tw(G))\cdot n$ using Courcelle's Theorem; (3) in time $f(|V(H)|,\genus(G))\cdot n$ using a result on first-order model checking by Frick and Grohe; or (4) in time $f(\maxdeg(H))\cdot n^{O(\tw(G)})$ for connected $H$ using the algorithm of Matoušek and Thomas. Already this small sample of results shows that the way an algorithm can depend on the parameters is highly nontrivial and subtle. We develop a framework involving 10 relevant parameters for each of $H$ and $G$ (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time \[ f_1(p_1,p_2,..., p_\ell)\cdot n^{f_2(p_{\ell+1},..., p_k)} \] exist, where each of $p_1,..., p_k$ is one of the 10 parameters depending only on $H$ or $G$. We show that {\em all} the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs); some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of $G$ gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when $H$ is a bounded-degree tree of constant pathwidth and $G$ is a planar graph of bounded pathwidth.
A Knowledge-based Treatment of Human-Automation Systems
Venue: arXiv cs.HC 2013
Year: 2013

In a supervisory control system the human agent knowledge of past, current, and future system behavior is critical for system performance. Being able to reason about that knowledge in a precise and structured manner is central to effective system design. In this paper we introduce the application of a well-established formal approach to reasoning about knowledge to the modeling and analysis of complex human-automation systems. An intuitive notion of knowledge in human-automation systems is sketched and then cast as a formal model. We present a case study in which the approach is used to model and reason about a classic problem from the human-automation systems literature; the results of our analysis provide evidence for the validity and value of reasoning about complex systems in terms of the knowledge of the system agents. To conclude, we discuss research directions that will extend this approach, and note several systems in the aviation and human-robot team domains that are of particular interest.
Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back
Venue: arXiv cs.DS 2013
Year: 2013

We present an $\tilde{O}(m^{10/7})=\tilde{O}(m^{1.43})$-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing $O(m \min(\sqrt{m},n^{2/3}))$ time bound due to Even and Tarjan [EvenT75]. By well-known reductions, this also establishes an $\tilde{O}(m^{10/7})$-time algorithm for the maximum-cardinality bipartite matching problem. That, in turn, gives an improvement over the celebrated celebrated $O(m \sqrt{n})$ time bound of Hopcroft and Karp [HK73] whenever the input graph is sufficiently sparse.
Finding the Minimum-Weight k-Path
Venue: arXiv cs.DS 2013
Year: 2013

Given a weighted $n$-vertex graph $G$ with integer edge-weights taken from a range $[-M,M]$, we show that the minimum-weight simple path visiting $k$ vertices can be found in time $\tilde{O}(2^k \poly(k) M n^ω) = O^*(2^k M)$. If the weights are reals in $[1,M]$, we provide a $(1+\varepsilon)$-approximation which has a running time of $\tilde{O}(2^k \poly(k) n^ω(\log\log M + 1/\varepsilon))$. For the more general problem of $k$-tree, in which we wish to find a minimum-weight copy of a $k$-node tree $T$ in a given weighted graph $G$, under the same restrictions on edge weights respectively, we give an exact solution of running time $\tilde{O}(2^k \poly(k) M n^3) $ and a $(1+\varepsilon)$-approximate solution of running time $\tilde{O}(2^k \poly(k) n^3(\log\log M + 1/\varepsilon))$. All of the above algorithms are randomized with a polynomially-small error probability.
Testing experiments on synchronized Petri nets
Venue: arXiv cs.SY 2013
Year: 2013

Synchronizing sequences have been proposed in the late 60's to solve testing problems on systems modeled by finite state machines. Such sequences lead a system, seen as a black box, from an unknown current state to a known final one. This paper presents a first investigation of the computation of synchronizing sequences for systems modeled by bounded synchronized Petri nets. In the first part of the paper, existing techniques for automata are adapted to this new setting. Later on, new approaches, that exploit the net structure to efficiently compute synchronizing sequences without an exhaustive enumeration of the state space, are presented.
Greedy Online Bipartite Matching on Random Graphs
Venue: arXiv cs.DS 2013
Year: 2013

We study the average performance of online greedy matching algorithms on $G(n,n,p)$, the random bipartite graph with $n$ vertices on each side and edges occurring independently with probability $p=p(n)$. In the online model, vertices on one side of the graph are given up front while vertices on the other side arrive sequentially; when a vertex arrives its edges are revealed and it must be immediately matched or dropped. We begin by analyzing the \textsc{oblivious} algorithm, which tries to match each arriving vertex to a random neighbor, even if the neighbor has already been matched. The algorithm is shown to have a performance ratio of at least $1-1/e$ for all monotonic functions $p(n)$, where the performance ratio is defined asymptotically as the ratio of the expected matching size given by the algorithm to the expected maximum matching size. Next we show that the conventional \textsc{greedy} algorithm, which assigns each vertex to a random unmatched neighbor, has a performance ratio of at least 0.837 for all monotonic functions $p(n)$. Under the $G(n,n,p)$ model, the performance of \textsc{greedy} is equivalent to the performance of the well known \textsc{ranking} algorithm, so our results show that \textsc{ranking} has a performance ratio of at least 0.837. We finally consider vertex-weighted bipartite matching. Our proofs are based on simple differential equations that describe the evolution of the matching process.
MacWilliams Type identities for $m$-spotty Rosenbloom-Tsfasman weight enumerators over finite commutative Frobenius rings
Venue: arXiv cs.IT 2013
Year: 2013

The $m$-spotty byte error control codes provide a good source for detecting and correcting errors in semiconductor memory systems using high density RAM chips with wide I/O data (e.g. 8, 16, or 32 bits). $m$-spotty byte error control codes are very suitable for burst correction. M. Özen and V. Siap [7] proved a MacWilliams identity for the $m$-spotty Rosenbloom-Tsfasman (shortly RT) weight enumerators of binary codes. The main purpose of this paper is to present the MacWilliams type identities for $m$-spotty RT weight enumerators of linear codes over finite commutative Frobenius rings.
From Design to Implementation: an Automated, Credible Autocoding Chain for Control Systems
Venue: arXiv cs.SY 2013
Year: 2013

This article describes a fully automated, credible autocoding chain for control systems. The framework generates code, along with guarantees of high level functional properties which can be independently verified. It relies on domain specific knowledge and fomal methods of analysis to address a context of heightened safety requirements for critical embedded systems and ever-increasing costs of verification and validation. The platform strives to bridge the semantic gap between domain expert and code verification expert. First, a graphical dataflow language is extended with annotation symbols enabling the control engineer to express high level properties of its control law within the framework of a familiar language. An existing autocoder is enhanced to both generate the code implementing the initial design, but also to carry high level properties down to annotations at the level of the code. Finally, using customized code analysis tools, certificates are generated which guarantee the correctness of the annotations with respect to the code, and can be verified using existing static analysis tools. Only a subset of properties and controllers are handled at this point.
Applications of repeat degree on coverings of neighborhoods
Venue: arXiv cs.AI 2013
Year: 2013

In covering based rough sets, the neighborhood of an element is the intersection of all the covering blocks containing the element. All the neighborhoods form a new covering called a covering of neighborhoods. In the course of studying under what condition a covering of neighborhoods is a partition, the concept of repeat degree is proposed, with the help of which the issue is addressed. This paper studies further the application of repeat degree on coverings of neighborhoods. First, we investigate under what condition a covering of neighborhoods is the reduct of the covering inducing it. As a preparation for addressing this issue, we give a necessary and sufficient condition for a subset of a set family to be the reduct of the set family. Then we study under what condition two coverings induce a same relation and a same covering of neighborhoods. Finally, we give the method of calculating the covering according to repeat degree.
Unique expansion matroids and union minimal matroids
Venue: arXiv cs.DM 2013
Year: 2013

The expansion axiom of matroids requires only the existence of some kind of independent sets, not the uniqueness of them. This causes that the base families of some matroids can be reduced while the unions of the base families of these matroids remain unchanged. In this paper, we define unique expansion matroids in which the expansion axiom has some extent uniqueness; we define union minimal matroids in which the base families have some extent minimality. Some properties of them and the relationship between them are studied. First, we propose the concepts of secondary base and forming base family. Secondly, we propose the concept of unique expansion matroid, and prove that a matroid is a unique expansion matroid if and only if its forming base family is a partition. Thirdly, we propose the concept of union minimal matroid, and prove that unique expansion matroids are union minimal matroids. Finally, we extend the concept of unique expansion matroid to unique exchange matroid and prove that both unique expansion matroids and their dual matroids are unique exchange matroids.
An Efficient Multiplication Algorithm Using Nikhilam Method
Venue: arXiv cs.DS 2013
Year: 2013

Multiplication is one of the most important operation in computer arithmetic. Many integer operations such as squaring, division and computing reciprocal require same order of time as multiplication whereas some other operations such as computing GCD and residue operation require at most a factor of $\log n$ time more than multiplication. We propose an integer multiplication algorithm using Nikhilam method of Vedic mathematics which can be used to multiply two binary numbers efficiently.