OpenRaiser/Intern-Atlas huggingface dataset:
On the Automorphism Groups and Equivalence of Cyclic Combinatorial Objects
Venue: arXiv cs.IT 2012
Year: 2012

We determine the permutation groups that arise as the automorphism groups of cyclic combinatorial objects. As special cases we classify the automorphism groups of cyclic codes. We also give the permutations by which two cyclic combinatorial objects on $p^m$ elements are equivalent.
Quality Assurance And Integration Testing Aspects In Web Based Applications
Venue: arXiv cs.SE 2012
Year: 2012

Integration testing is one the important phase in software testing life cycle (STLC). With the fast growth of internet and web services, web-based applications are also growing rapidly and their importance and complexity is also increasing. Heterogeneous and diverse nature of distributed components, applications, along with their multi-platform support and cooperativeness make these applications more complex and swiftly increasing in their size. Quality assurance of these applications is becoming more crucial and important. Testing is one of the key processes to achieve and ensure the quality of these software or Webbased products. There are many testing challenges involved in Web-based applications. But most importantly integration is the most critical testing associated with Web-based applications. There are number of challenging factors involved in integration testing efforts. These factors have almost 70 percent to 80 percent impact on overall quality of Web-based applications. In software industry different kind of testing approaches are used by practitioners to solve the issues associated with integration which are due to ever increasing complexities of Web-based applications.
An Empirical Study of the Relation Between Community Structure and Transitivity
Venue: arXiv cs.SI 2012
Year: 2012

One of the most prominent properties in real-world networks is the presence of a community structure, i.e. dense and loosely interconnected groups of nodes called communities. In an attempt to better understand this concept, we study the relationship between the strength of the community structure and the network transitivity (or clustering coefficient). Although intuitively appealing, this analysis was not performed before. We adopt an approach based on random models to empirically study how one property varies depending on the other. It turns out the transitivity increases with the community structure strength, and is also affected by the distribution of the community sizes. Furthermore, increasing the transitivity also results in a stronger community structure. More surprisingly, if a very weak community structure causes almost zero transitivity, the opposite is not true and a network with a close to zero transitivity can still have a clearly defined community structure. Further analytical work is necessary to characterize the exact nature of the identified relationship.
Canonized Rewriting and Ground AC Completion Modulo Shostak Theories : Design and Implementation
Venue: arXiv cs.LO 2012
Year: 2012

AC-completion efficiently handles equality modulo associative and commutative function symbols. When the input is ground, the procedure terminates and provides a decision algorithm for the word problem. In this paper, we present a modular extension of ground AC-completion for deciding formulas in the combination of the theory of equality with user-defined AC symbols, uninterpreted symbols and an arbitrary signature disjoint Shostak theory X. Our algorithm, called AC(X), is obtained by augmenting in a modular way ground AC-completion with the canonizer and solver present for the theory X. This integration rests on canonized rewriting, a new relation reminiscent to normalized rewriting, which integrates canonizers in rewriting steps. AC(X) is proved sound, complete and terminating, and is implemented to extend the core of the Alt-Ergo theorem prover.
Learning the Pseudoinverse Solution to Network Weights
Venue: arXiv cs.NE 2012
Year: 2012

The last decade has seen the parallel emergence in computational neuroscience and machine learning of neural network structures which spread the input signal randomly to a higher dimensional space; perform a nonlinear activation; and then solve for a regression or classification output by means of a mathematical pseudoinverse operation. In the field of neuromorphic engineering, these methods are increasingly popular for synthesizing biologically plausible neural networks, but the "learning method" - computation of the pseudoinverse by singular value decomposition - is problematic both for biological plausibility and because it is not an online or an adaptive method. We present an online or incremental method of computing the pseudoinverse, which we argue is biologically plausible as a learning method, and which can be made adaptable for non-stationary data streams. The method is significantly more memory-efficient than the conventional computation of pseudoinverses by singular value decomposition.
Construction of Cyclic Codes over $\mathbb{F}_2+u\mathbb{F}_2$ for DNA Computing
Venue: arXiv cs.IT 2012
Year: 2012

We construct codes over the ring $\mathbb{F}_2+u\mathbb{F}_2$ with $u^2=0$. These code are designed for use in DNA computing applications. The codes obtained satisfy the reverse complement constraint, the $GC$ content constraint and avoid the secondary structure. they are derived from the cyclic complement reversible codes over the ring $\mathbb{F}_2+u\mathbb{F}_2$. We also construct an infinite family of BCH DNA codes.
Self-dual Repeated Root Cyclic and Negacyclic Codes over Finite Fields
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we investigate repeated root cyclic and negacyclic codes of length $p^rm$ over $\mathbb{F}_{p^s}$ with $(m,p)=1$. In the case $p$ odd, we give necessary and sufficient conditions on the existence of negacyclic self-dual codes. When $m=2m'$ with $m'$ odd, we characterize the codes in terms of their generator polynomials. This provides simple conditions on the existence of self-dual negacyclic codes, and generalizes the results of Dinh \cite{dinh}. We also answer an open problem concerning the number of self-dual cyclic codes given by Jia et al. \cite{jia}.
On Distributability of Petri Nets
Venue: arXiv cs.LO 2012
Year: 2012

We formalise a general concept of distributed systems as sequential components interacting asynchronously. We define a corresponding class of Petri nets, called LSGA nets, and precisely characterise those system specifications which can be implemented as LSGA nets up to branching ST-bisimilarity with explicit divergence.
Statistical Simulation Models for Cascaded Rayleigh Fading Channels
Venue: arXiv cs.OH 2012
Year: 2012

In this paper, we present statistical simulators for cascaded Rayleigh fading channels with and without line-of-sight (LOS). These simulators contain two individual summations and are therefore easy to implement with lower complexity. Detailed statistical properties, including auto- and cross-correlations of the in-phase, quadrature components of the channels, envelopes, and squared envelopes, are derived. The time-average statistical properties and the corresponding variance are also investigated to justify that the proposed simulators achieve good convergence performance. Extensive Monte Carlo simulations are performed for various statistical properties to validate the proposed simulators. Results show that the simulators provide fast convergence to all desired statistical properties, including the probability density function (PDF), various auto- and cross-correlations, level crossing rate (LCR), and average fading duration (AFD). While various tests and measurements in dense scattering urban and forest environments indicate that mobile-to-mobile channels may experience cascaded Rayleigh fading, the proposed statistical models can be applied to simulate the underlying channels.
On the Resilience of Routing Tables
Venue: arXiv cs.DC 2012
Year: 2012

Many modern network designs incorporate "failover" paths into routers' forwarding tables. We initiate the theoretical study of the conditions under which such resilient routing tables can guarantee delivery of packets.
Light Spanner and Monotone Tree
Venue: arXiv cs.DS 2012
Year: 2012

In approximation algorithm design, light spanners has applications in graph-metric problems such as metric TSP (the traveling salesman problem). We have developed an efficient algorithm for light spanners in bounded pathwidth graphs, based on an intermediate data structure called monotone tree. In this paper, we extended the results to include bounded catwidth graphs.
On the Relationship between LTL Normal Forms and Buechi Automata
Venue: arXiv cs.FL 2012
Year: 2012

In this paper, we consider the problem of translating LTL formulas to Buechi automata. We first translate the given LTL formula into a special disjuctive-normal form (DNF). The formula will be part of the state, and its DNF normal form specifies the atomic properties that should hold immediately (labels of the transitions) and the formula that should hold afterwards (the corresponding successor state). Surprisingly, if the given formula is Until-free or Release-free, the Buechi automaton can be obtained directly in this manner. For a general formula, the construction is slightly involved: an additional component will be needed for each formula that helps us to identify the set of accepting states. Notably, our construction is an on-the-fly construction, and the resulting Buechi automaton has in worst case 2^{2n+1} states where n denotes the number of subformulas. Moreover, it has a better bound 2^{n+1} when the formula is Until- (or Release-) free.
Transmission of Voice Signal: BER Performance Analysis of Different FEC Schemes Based OFDM System over Various Channels
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we investigate the impact of Forward Error Correction (FEC) codes namely Cyclic Redundancy Code and Convolution Code on the performance of OFDM wireless communication system for speech signal transmission over both AWGN and fading (Rayleigh and Rician) channels in term of Bit Error Probability. The simulation has been done in conjunction with QPSK digital modulation and compared with uncoded resultstal modulation. In the fading channels, it is found via computer simulation that the performance of the Convolution interleaved based OFDM systems outperform than that of CRC interleaved OFDM system as well as uncoded OFDM channels.
A New Determinant Inequality of Positive Semi-Definite Matrices
Venue: arXiv cs.IT 2012
Year: 2012

A new determinant inequality of positive semidefinite matrices is discovered and proved by us. This new inequality is useful for attacking and solving a variety of optimization problems arising from the design of wireless communication systems.
Effect of Interleaved FEC Code on Wavelet Based MC-CDMA System with Alamouti STBC in Different Modulation Schemes
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, the impact of Forward Error Correction (FEC) code namely Trellis code with interleaver on the performance of wavelet based MC-CDMA wireless communication system with the implementation of Alamouti antenna diversity scheme has been investigated in terms of Bit Error Rate (BER) as a function of Signal-to-Noise Ratio (SNR) per bit. Simulation of the system under proposed study has been done in M-ary modulation schemes (MPSK, MQAM and DPSK) over AWGN and Rayleigh fading channel incorporating Walsh Hadamard code as orthogonal spreading code to discriminate the message signal for individual user. It is observed via computer simulation that the performance of the interleaved coded based proposed system outperforms than that of the uncoded system in all modulation schemes over Rayleigh fading channel.
Automatic Segmentation of Manipuri (Meiteilon) Word into Syllabic Units
Venue: arXiv cs.CL 2012
Year: 2012

The work of automatic segmentation of a Manipuri language (or Meiteilon) word into syllabic units is demonstrated in this paper. This language is a scheduled Indian language of Tibeto-Burman origin, which is also a very highly agglutinative language. This language usages two script: a Bengali script and Meitei Mayek (Script). The present work is based on the second script. An algorithm is designed so as to identify mainly the syllables of Manipuri origin word. The result of the algorithm shows a Recall of 74.77, Precision of 91.21 and F-Score of 82.18 which is a reasonable score with the first attempt of such kind for this language.
Optimization of a Finite Frequency-Hopping Ad Hoc Network in Nakagami Fading
Venue: arXiv cs.IT 2012
Year: 2012

This paper considers the analysis and optimization of a frequency-hopping ad hoc network with a finite number of mobiles and finite spatial extent. The mobiles communicate using coded continuous-phase frequency-shift keying (CPFSK) modulation. The performance of the system is a function of the number of hopping channels, the rate of the error-correction code, and the modulation index used by the CPFSK modulation. For a given channel model and density of mobiles, these parameters are jointly optimized by maximizing the (modulation-constrained) transmission capacity, which is a measure of the spatial spectral efficiency of the system. The transmission capacity of the finite network is found by using a recent expression for the spatially averaged outage probability in the presence of Nakagami fading, which is found in closed form in the absence of shadowing and can be solved using numerical integration in the presence of shadowing.
Stable Independance and Complexity of Representation
Venue: arXiv cs.AI 2012
Year: 2012

The representation of independence relations generally builds upon the well-known semigraphoid axioms of independence. Recently, a representation has been proposed that captures a set of dominant statements of an independence relation from which any other statement can be generated by means of the axioms; the cardinality of this set is taken to indicate the complexity of the relation. Building upon the idea of dominance, we introduce the concept of stability to provide for a more compact representation of independence. We give an associated algorithm for establishing such a representation.We show that, with our concept of stability, many independence relations are found to be of lower complexity than with existing representations.
A Logic Programming Framework for Possibilistic Argumentation with Vague Knowledge
Venue: arXiv cs.AI 2012
Year: 2012

Defeasible argumentation frameworks have evolved to become a sound setting to formalize commonsense, qualitative reasoning from incomplete and potentially inconsistent knowledge. Defeasible Logic Programming (DeLP) is a defeasible argumentation formalism based on an extension of logic programming. Although DeLP has been successfully integrated in a number of different real-world applications, DeLP cannot deal with explicit uncertainty, nor with vague knowledge, as defeasibility is directly encoded in the object language. This paper introduces P-DeLP, a new logic programming language that extends original DeLP capabilities for qualitative reasoning by incorporating the treatment of possibilistic uncertainty and fuzzy knowledge. Such features will be formalized on the basis of PGL, a possibilistic logic based on Godel fuzzy logic.
Applying Discrete PCA in Data Analysis
Venue: arXiv cs.LG 2012
Year: 2012

Methods for analysis of principal components in discrete data have existed for some time under various names such as grade of membership modelling, probabilistic latent semantic analysis, and genotype inference with admixture. In this paper we explore a number of extensions to the common theory, and present some application of these methods to some common statistical tasks. We show that these methods can be interpreted as a discrete version of ICA. We develop a hierarchical version yielding components at different levels of detail, and additional techniques for Gibbs sampling. We compare the algorithms on a text prediction task using support vector machines, and to information retrieval.
Computing Nash Equilibria of Action-Graph Games
Venue: arXiv cs.GT 2012
Year: 2012

Action-graph games (AGGs) are a fully expressive game representation which can compactly express both strict and context-specific independence between players' utility functions. Actions are represented as nodes in a graph G, and the payoff to an agent who chose the action s depends only on the numbers of other agents who chose actions connected to s. We present algorithms for computing both symmetric and arbitrary equilibria of AGGs using a continuation method. We analyze the worst-case cost of computing the Jacobian of the payoff function, the exponential-time bottleneck step, and in all cases achieve exponential speedup. When the indegree of G is bounded by a constant and the game is symmetric, the Jacobian can be computed in polynomial time.
Convolutional Factor Graphs as Probabilistic Models
Venue: arXiv cs.AI 2012
Year: 2012

Based on a recent development in the area of error control coding, we introduce the notion of convolutional factor graphs (CFGs) as a new class of probabilistic graphical models. In this context, the conventional factor graphs are referred to as multiplicative factor graphs (MFGs). This paper shows that CFGs are natural models for probability functions when summation of independent latent random variables is involved. In particular, CFGs capture a large class of linear models, where the linearity is in the sense that the observed variables are obtained as a linear ransformation of the latent variables taking arbitrary distributions. We use Gaussian models and independent factor models as examples to emonstrate the use of CFGs. The requirement of a linear transformation between latent variables (with certain independence restriction) and the bserved variables, to an extent, limits the modelling flexibility of CFGs. This structural restriction however provides a powerful analytic tool to the framework of CFGs; that is, upon taking the Fourier transform of the function represented by the CFG, the resulting function is represented by a FG with identical structure. This Fourier transform duality allows inference problems on a CFG to be solved on the corresponding dual MFG.
Graph partition strategies for generalized mean field inference
Venue: arXiv cs.LG 2012
Year: 2012

An autonomous variational inference algorithm for arbitrary graphical models requires the ability to optimize variational approximations over the space of model parameters as well as over the choice of tractable families used for the variational approximation. In this paper, we present a novel combination of graph partitioning algorithms with a generalized mean field (GMF) inference algorithm. This combination optimizes over disjoint clustering of variables and performs inference using those clusters. We provide a formal analysis of the relationship between the graph cut and the GMF approximation, and explore several graph partition strategies empirically. Our empirical results provide rather clear support for a weighted version of MinCut as a useful clustering algorithm for GMF inference, which is consistent with the implications from the formal analysis.
A Parametric Counterexample Refinement Approach for Robust Timed Specifications
Venue: arXiv cs.SE 2012
Year: 2012

Robustness analyzes the impact of small perturbations in the semantics of a model. This allows to model hardware imprecision and therefore it has been applied to determine implementability of timed automata. In a recent paper, we extend this problem to a specification theory for real-timed systems based on timed input/output automata, that are interpreted as two-player games. We propose a construction that allows to synthesize an implementation of a specification that is robust under a given timed perturbation, and we study the impact of these perturbations when composing different specifications. To complete this work we present a technique that evaluates the greatest admissible perturbation. It consists in an iterative process that extracts a spoiling strategy when a game is lost, and through a parametric analysis refines the admissible values for the perturbation. We demonstrate this approach with a prototype implementation.
Spatio-Temporal Data Correlation with Adaptive Strategies in Wireless Sensor Networks
Venue: arXiv cs.NI 2012
Year: 2012

One of the major task of sensor nodes in wireless sensor networks is to transmit a subset of sensor readings to the sink node estimating a desired data accuracy. Therefore in this paper, we propose an accuracy model using Steepest Decent method called Adaptive Data Accuracy (ADA) model which doesn't require any a priori information of input signal statistics to select an optimal set of sensor nodes in the network. Moreover we develop another model using LMS filter called Spatio-Temporal Data Prediction (STDP) model which captures the spatial and temporal correlation of sensing data to reduce the communication overhead under data reduction strategies. Finally using STDP model, we illustrate a mechanism to trace the malicious nodes in the network under extreme physical environment. Computer simulations illustrate the performance of ADA and STDP models respectively.
Faster SDP hierarchy solvers for local rounding algorithms
Venue: arXiv cs.DS 2012
Year: 2012

Convex relaxations based on different hierarchies of linear/semi-definite programs have been used recently to devise approximation algorithms for various optimization problems. The approximation guarantee of these algorithms improves with the number of {\em rounds} $r$ in the hierarchy, though the complexity of solving (or even writing down the solution for) the $r$'th level program grows as $n^{Ω(r)}$ where $n$ is the input size. In this work, we observe that many of these algorithms are based on {\em local} rounding procedures that only use a small part of the SDP solution (of size $n^{O(1)} 2^{O(r)}$ instead of $n^{Ω(r)}$). We give an algorithm to find the requisite portion in time polynomial in its size. The challenge in achieving this is that the required portion of the solution is not fixed a priori but depends on other parts of the solution, sometimes in a complicated iterative manner. Our solver leads to $n^{O(1)} 2^{O(r)}$ time algorithms to obtain the same guarantees in many cases as the earlier $n^{O(r)}$ time algorithms based on $r$ rounds of the Lasserre hierarchy. In particular, guarantees based on $O(\log n)$ rounds can be realized in polynomial time. We develop and describe our algorithm in a fairly general abstract framework. The main technical tool in our work, which might be of independent interest in convex optimization, is an efficient ellipsoid algorithm based separation oracle for convex programs that can output a {\em certificate of infeasibility with restricted support}. This is used in a recursive manner to find a sequence of consistent points in nested convex bodies that "fools" local rounding algorithms.
Towards Understanding Triangle Construction Problems
Venue: arXiv cs.AI 2012
Year: 2012

Straightedge and compass construction problems are one of the oldest and most challenging problems in elementary mathematics. The central challenge, for a human or for a computer program, in solving construction problems is a huge search space. In this paper we analyze one family of triangle construction problems, aiming at detecting a small core of the underlying geometry knowledge. The analysis leads to a small set of needed definitions, lemmas and primitive construction steps, and consequently, to a simple algorithm for automated solving of problems from this family. The same approach can be applied to other families of construction problems.