OpenRaiser/Intern-Atlas huggingface dataset:
Hamiltonian Connectivity of Twisted Hypercube-Like Networks under the Large Fault Model
Venue: arXiv cs.DC 2011
Year: 2011

Twisted hypercube-like networks (THLNs) are an important class of interconnection networks for parallel computing systems, which include most popular variants of the hypercubes, such as crossed cubes, Möbius cubes, twisted cubes and locally twisted cubes. This paper deals with the fault-tolerant hamiltonian connectivity of THLNs under the large fault model. Let $G$ be an $n$-dimensional THLN and $F \subseteq V(G)\bigcup E(G)$, where $n \geq 7$ and $|F| \leq 2n - 10$. We prove that for any two nodes $u,v \in V(G - F)$ satisfying a simple necessary condition on neighbors of $u$ and $v$, there exists a hamiltonian or near-hamiltonian path between $u$ and $v$ in $G-F$. The result extends further the fault-tolerant graph embedding capability of THLNs.
Independent sets of words and the synchronization problem
Venue: arXiv cs.FL 2011
Year: 2011

The synchronization problem is investigated for the class of locally strongly transitive automata introduced in a previous work of the authors. Some extensions of this problem related to the notions of stable set and word of minimal rank of an automaton are studied. An application to synchronizing colorings of aperiodic graphs with a Hamiltonian path is also considered.
A New Technique to Backup and Restore DBMS using XML and .NET Technologies
Venue: arXiv cs.DB 2011
Year: 2011

In this paper, we proposed a new technique for backing up and restoring different Database Management Systems (DBMS). The technique is enabling to backup and restore a part of or the whole database using a unified interface using ASP.NET and XML technologies. It presents a Web Solution allowing the administrators to do their jobs from everywhere, locally or remotely. To show the importance of our solution, we have taken two case studies, oracle 11g and SQL Server 2008.
A GP-MOEA/D Approach for Modelling Total Electron Content over Cyprus
Venue: arXiv cs.AI 2011
Year: 2011

Vertical Total Electron Content (vTEC) is an ionospheric characteristic used to derive the signal delay imposed by the ionosphere on near-vertical trans-ionospheric links. The major aim of this paper is to design a prediction model based on the main factors that influence the variability of this parameter on a diurnal, seasonal and long-term time-scale. The model should be accurate and general (comprehensive) enough for efficiently approximating the high variations of vTEC. However, good approximation and generalization are conflicting objectives. For this reason a Genetic Programming (GP) with Multi-objective Evolutionary Algorithm based on Decomposition characteristics (GP-MOEA/D) is designed and proposed for modeling vTEC over Cyprus. Experimental results show that the Multi-Objective GP-model, considering real vTEC measurements obtained over a period of 11 years, has produced a good approximation of the modeled parameter and can be implemented as a local model to account for the ionospheric imposed error in positioning. Particulary, the GP-MOEA/D approach performs better than a Single Objective Optimization GP, a GP with Non-dominated Sorting Genetic Algorithm-II (NSGA-II) characteristics and the previously proposed Neural Network-based approach in most cases.
Partial mutual exclusion for infinitely many processes
Venue: arXiv cs.DC 2011
Year: 2011

Partial mutual exclusion is the drinking philosophers problem for complete graphs. It is the problem that a process may enter a critical section CS of its code only when some finite set nbh of other processes are not in their critical sections. For each execution of CS, the set nbh can be given by the environment. We present a starvation free solution of this problem in a setting with infinitely many processes, each with finite memory, that communicate by asynchronous messages. The solution has the property of first-come first-served, in so far as this can be guaranteed by asynchronous messages. For every execution of CS and every process in nbh, between three and six messages are needed. The correctness of the solution is argued with invariants and temporal logic. It has been verified with the proof assistant PVS.
Sampling, Filtering and Sparse Approximations on Combinatorial Graphs
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we address sampling and approximation of functions on combinatorial graphs. We develop filtering on graphs by using Schrödinger's group of operators generated by combinatorial Laplace operator. Then we construct a sampling theory by proving Poincare and Plancherel-Polya-type inequalities for functions on graphs. These results lead to a theory of sparse approximations on graphs and have potential applications to filtering, denoising, data dimension reduction, image processing, image compression, computer graphics, visualization and learning theory.
Capacity-Approaching Signal Constellations for the Additive Exponential Noise Channel
Venue: arXiv cs.IT 2011
Year: 2011

We present a new family of signal constellations, called log constellations, that can be used to design near-capacity coded modulation schemes over additive exponential noise (AEN) channels. Log constellations are designed by geometrically approximating the input distribution that maximizes the AEN channel capacity. The mutual information achievable over AEN channels with both coded modulation (CM) and bit-interleaved coded modulation (BICM) approaches is evaluated for various signal sets. In the case of CM, the proposed log constellations outperform, sometimes by over half a decibel, the best existing signal sets available from the literature, and can display error performance within only 0.12 dB of the AEN channel capacity. In the context of BICM, log constellations do not offer significant performance advantages over the best existing constellations. As the potential performance degradation resulting from the use of BICM instead of CM is larger than 1 dB, BICM may however not be a suitable design approach over AEN channels.
Unique decodability of bigram counts by finite automata
Venue: arXiv cs.FL 2011
Year: 2011

We revisit the problem of deciding whether a given string is uniquely decodable from its bigram counts by means of a finite automaton. An efficient algorithm for constructing a polynomial-size nondeterministic finite automaton that decides unique decodability is given. Conversely, we show that the minimum deterministic finite automaton for deciding unique decodability has at least exponentially many states in alphabet size.
Constraint Satisfaction Tractability from Semi-lattice Operations on Infinite Sets
Venue: arXiv cs.CC 2011
Year: 2011

A famous result by Jeavons, Cohen, and Gyssens shows that every constraint satisfaction problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called universal-algebraic approach to a systematic theory of tractability and hardness in finite domain constraint satisfaction. Not surprisingly, the theorem of Jeavons et al. fails for arbitrary infinite domain CSPs. Many CSPs of practical interest, though, and in particular those CSPs that are motivated by qualitative reasoning calculi from Artificial Intelligence, can be formulated with constraint languages that are rather well-behaved from a model-theoretic point of view. In particular, the automorphism group of these constraint languages tends to be large in the sense that the number of orbits of n-subsets of the automorphism group is bounded by some function in n. In this paper we present a generalization of the theorem by Jeavons et al. to infinite domain CSPs where the number of orbits of n-subsets grows sub-exponentially in n, and prove that preservation under a semi-lattice operation for such CSPs implies polynomial-time tractability. Unlike the result of Jeavons et al., this includes many CSPs that cannot be solved by Datalog.
Packet flow analysis in IP networks via abstract interpretation
Venue: arXiv cs.NI 2011
Year: 2011

Static analysis (aka offline analysis) of a model of an IP network is useful for understanding, debugging, and verifying packet flow properties of the network. There have been static analysis approaches proposed in the literature for networks based on model checking as well as graph reachability. Abstract interpretation is a method that has typically been applied to static analysis of programs. We propose a new, abstract-interpretation based approach for analysis of networks. We formalize our approach, mention its correctness guarantee, and demonstrate its flexibility in addressing multiple network-analysis problems that have been previously solved via tailor-made approaches. Finally, we investigate an application of our analysis to a novel problem -- inferring a high-level policy for the network -- which has been addressed in the past only in the restricted single-router setting.
Beyond The Desktop Spreadsheet
Venue: arXiv cs.SE 2011
Year: 2011

Hypernumbers is a new commercial web-based spreadsheet. It addresses several risk factors in deploying spreadsheets.
The M4RIE library for dense linear algebra over small fields with even characteristic
Venue: arXiv cs.MS 2011
Year: 2011

In this work, we present the M4RIE library which implements efficient algorithms for linear algebra with dense matrices over GF(2^e) for 2 <= 2 <= 10. As the name of the library indicates, it makes heavy use of the M4RI library both directly (i.e., by calling it) and indirectly (i.e., by using its concepts). We provide an open-source GPLv2+ C library for efficient linear algebra over GF(2^e) for e small. In this library we implemented an idea due to Bradshaw and Boothby which reduces matrix multiplication over GF(p^k) to a series of matrix multiplications over GF(p). Furthermore, we propose a caching technique - Newton-John tables - to avoid finite field multiplications which is inspired by Kronrod's method ("M4RM") for matrix multiplication over GF(2). Using these two techniques we provide asymptotically fast triangular solving with matrices (TRSM) and PLE-based Gaussian elimination. As a result, we are able to significantly improve upon the state of the art in dense linear algebra over GF(2^e) with 2 <= e <= 10.
A Cook's Tour of the Finitary Non-Well-Founded Sets
Venue: arXiv cs.LO 2011
Year: 2011

We give multiple descriptions of a topological universe of finitary sets, which can be seen as a natural limit completion of the hereditarily finite sets. This universe is characterized as a metric completion of the hereditarily finite sets; as a Stone space arising as the solution of a functorial fixed-point equation involving the Vietoris construction; as the Stone dual of the free modal algebra; and as the subspace of maximal elements of a domain equation involving the Plotkin (or convex) powerdomain. These results illustrate the methods developed in the author's 'Domain theory in logical form', and related literature, and have been taken up in recent work on topological coalgebras. The set-theoretic universe of finitary sets also supports an interesting form of set theory. It contains non-well founded sets and a universal set; and is closed under positive versions of the usual axioms of set theory.
Indexing the Earth Mover's Distance Using Normal Distributions
Venue: arXiv cs.DB 2011
Year: 2011

Querying uncertain data sets (represented as probability distributions) presents many challenges due to the large amount of data involved and the difficulties comparing uncertainty between distributions. The Earth Mover's Distance (EMD) has increasingly been employed to compare uncertain data due to its ability to effectively capture the differences between two distributions. Computing the EMD entails finding a solution to the transportation problem, which is computationally intensive. In this paper, we propose a new lower bound to the EMD and an index structure to significantly improve the performance of EMD based K-nearest neighbor (K-NN) queries on uncertain databases. We propose a new lower bound to the EMD that approximates the EMD on a projection vector. Each distribution is projected onto a vector and approximated by a normal distribution, as well as an accompanying error term. We then represent each normal as a point in a Hough transformed space. We then use the concept of stochastic dominance to implement an efficient index structure in the transformed space. We show that our method significantly decreases K-NN query time on uncertain databases. The index structure also scales well with database cardinality. It is well suited for heterogeneous data sets, helping to keep EMD based queries tractable as uncertain data sets become larger and more complex.
PASS-JOIN: A Partition-based Method for Similarity Joins
Venue: arXiv cs.DB 2011
Year: 2011

As an essential operation in data cleaning, the similarity join has attracted considerable attention from the database community. In this paper, we study string similarity joins with edit-distance constraints, which find similar string pairs from two large sets of strings whose edit distance is within a given threshold. Existing algorithms are efficient either for short strings or for long strings, and there is no algorithm that can efficiently and adaptively support both short strings and long strings. To address this problem, we propose a partition-based method called Pass-Join. Pass-Join partitions a string into a set of segments and creates inverted indices for the segments. Then for each string, Pass-Join selects some of its substrings and uses the selected substrings to find candidate pairs using the inverted indices. We devise efficient techniques to select the substrings and prove that our method can minimize the number of selected substrings. We develop novel pruning techniques to efficiently verify the candidate pairs. Experimental results show that our algorithms are efficient for both short strings and long strings, and outperform state-of-the-art methods on real datasets.
Achieving Both Valid and Secure Logistic Regression Analysis on Aggregated Data from Different Private Sources
Venue: arXiv cs.CR 2011
Year: 2011

Preserving the privacy of individual databases when carrying out statistical calculations has a long history in statistics and had been the focus of much recent attention in machine learning In this paper, we present a protocol for computing logistic regression when the data are held by separate parties without actually combining information sources by exploiting results from the literature on multi-party secure computation. We provide only the final result of the calculation compared with other methods that share intermediate values and thus present an opportunity for compromise of values in the combined database. Our paper has two themes: (1) the development of a secure protocol for computing the logistic parameters, and a demonstration of its performances in practice, and (2) and amended protocol that speeds up the computation of the logistic function. We illustrate the nature of the calculations and their accuracy using an extract of data from the Current Population Survey divided between two parties.
Flip-OFDM for Unipolar Communication Systems
Venue: arXiv cs.IT 2011
Year: 2011

Unipolar communications systems can transmit information using only real and positive signals. This includes a variety of physical channels ranging from optical (fiber or free-space), to RF wireless using amplitude modulation with non-coherent reception, to baseband single wire communications. Unipolar OFDM techniques enable to efficiently compensate frequency selective distortion in the unipolar communication systems. One of the leading examples of unipolar OFDM is asymmetric clipped optical OFDM (ACO-OFDM) originally proposed for optical communications. Flip-OFDM is an alternative approach that was proposed in a patent, but its performance and full potentials have never been investigated in the literature. In this paper, we first compare Flip-OFDM and ACO-OFDM, and show that both techniques have the same performance but different complexities (Flip-OFDM offers 50% saving). We then propose a new detection scheme, which enables to reduce the noise at the Flip-OFDM receiver by almost 3dB. The analytical performance of the noise filtering schemes is supported by the simulation results.
An automaton approach for waiting times in DNA evolution
Venue: arXiv cs.DM 2011
Year: 2011

In a recent article, Behrens and Vingron (JCB 17, 12, 2010) compute waiting times for k-mers to appear during DNA evolution under the assumption that the considered k-mers do not occur in the initial DNA sequence, an issue arising when studying the evolution of regulatory DNA sequences with regard to transcription factor (TF) binding site emergence. The mathematical analysis underlying their computation assumes that occurrences of words under interest do not overlap. We relax here this assumption by use of an automata approach. In an alphabet of size 4 like the DNA alphabet, most words have no or a low autocorrelation; therefore, globally, our results confirm those of Behrens and Vingron. The outcome is quite different when considering highly autocorrelated k-mers; in this case, the autocorrelation pushes down the probability of occurrence of these k-mers at generation 1 and, consequently, increases the waiting time for apparition of these k-mers up to 40%. An analysis of existing TF binding sites unveils a significant proportion of k-mers exhibiting autocorrelation. Thus, our computations based on automata greatly improve the accuracy of predicting waiting times for the emergence of TF binding sites to appear during DNA evolution. We do the computation in the Bernoulli or M0 model; computations in the M1 model, a Markov model of order 1, are more costly in terms of time and memory but should produce similar results. While Behrens and Vingron considered specifically promoters of length 1000, we extend the results to promoters of any size; we exhibit the property that the probability that a k-mer occurs at generation time 1 while being absent at time 0 behaves linearly with respect to the length of the promoter, which induces a hyperbolic behaviour of the waiting time of any k-mer with respect to the length of the promoter.
Supervised Learning of Logical Operations in Layered Spiking Neural Networks with Spike Train Encoding
Venue: arXiv cs.NE 2011
Year: 2011

Few algorithms for supervised training of spiking neural networks exist that can deal with patterns of multiple spikes, and their computational properties are largely unexplored. We demonstrate in a set of simulations that the ReSuMe learning algorithm can be successfully applied to layered neural networks. Input and output patterns are encoded as spike trains of multiple precisely timed spikes, and the network learns to transform the input trains into target output trains. This is done by combining the ReSuMe learning algorithm with multiplicative scaling of the connections of downstream neurons. We show in particular that layered networks with one hidden layer can learn the basic logical operations, including Exclusive-Or, while networks without hidden layer cannot, mirroring an analogous result for layered networks of rate neurons. While supervised learning in spiking neural networks is not yet fit for technical purposes, exploring computational properties of spiking neural networks advances our understanding of how computations can be done with spike trains.
Ontological Queries: Rewriting and Optimization (Extended Version)
Venue: arXiv cs.DB 2011
Year: 2011

Ontological queries are evaluated against an ontology rather than directly on a database. The evaluation and optimization of such queries is an intriguing new problem for database research. In this paper we discuss two important aspects of this problem: query rewriting and query optimization. Query rewriting consists of the compilation of an ontological query into an equivalent query against the underlying relational database. The focus here is on soundness and completeness. We review previous results and present a new rewriting algorithm for rather general types of ontological constraints. In particular, we show how a conjunctive query against an ontology can be compiled into a union of conjunctive queries against the underlying database. Ontological query optimization, in this context, attempts to improve this process so to produce possibly small and cost-effective UCQ rewritings for an input query. We review existing optimization methods, and propose an effective new method that works for linear Datalog+/-, a class of Datalog-based rules that encompasses well-known description logics of the DL-Lite family.
Reliable Communication in Wireless Body Area Sensor Network for Health Monitoring
Venue: arXiv cs.NI 2011
Year: 2011

Now days, interests in the application of Wireless Body Area Network (WBAN) have grown considerably. A number of tiny wireless sensors, strategically placed on the human body, create a wireless body area network that can monitor various vital signs, providing real-time feedback to the user and medical personnel. This communication needs to be energy efficient and highly reliable while keeping delays low. In this paper we present hardware and software architecture for BAN and also we offer reliable communication and data aggregation.
Quantum Strategies Win in a Defector-Dominated Population
Venue: arXiv cs.GT 2011
Year: 2011

Quantum strategies are introduced into evolutionary games. The agents using quantum strategies are regarded as invaders whose fraction generally is 1% of a population in contrast to the 50% defectors. In this paper, the evolution of strategies on networks is investigated in a defector-dominated population, when three networks (Regular Lattice, Newman-Watts small world network, scale-free network) are constructed and three games (Prisoners' Dilemma, Snowdrift, Stag-Hunt) are employed. As far as these three games are concerned, the results show that quantum strategies can always invade the population successfully. Comparing the three networks, we find that the regular lattice is most easily invaded by agents that adopt quantum strategies. However, for a scale-free network it can be invaded by agents adopting quantum strategies only if a hub is occupied by an agent with a quantum strategy or if the fraction of agents with quantum strategies in the population is significant.
Performance Analysis of Hybrid Relay Selection in Cooperative Wireless Systems
Venue: arXiv cs.IT 2011
Year: 2011

The hybrid relay selection (HRS) scheme, which adaptively chooses amplify-and-forward (AF) and decode-and-forward (DF) protocols, is very effective to achieve robust performance in wireless networks. This paper analyzes the frame error rate (FER) of the HRS scheme in general cooperative wireless networks without and with utilizing error control coding at the source node. We first develop an improved signal-to-noise ratio (SNR) threshold-based FER approximation model. Then, we derive an analytical average FER expression as well as an asymptotic expression at high SNR for the HRS scheme and generalize to other relaying schemes. Simulation results are in excellent agreement with the theoretical analysis, which validates the derived FER expressions.
Quantum Cost Efficient Reversible BCD Adder for Nanotechnology Based Systems
Venue: arXiv cs.AR 2011
Year: 2011

Reversible logic allows low power dissipating circuit design and founds its application in cryptography, digital signal processing, quantum and optical information processing. This paper presents a novel quantum cost efficient reversible BCD adder for nanotechnology based systems using PFAG gate. It has been demonstrated that the proposed design offers less hardware complexity and requires minimum number of garbage outputs than the existing counterparts. The remarkable property of the proposed designs is that its quantum realization is given in NMR technology.