OpenRaiser/Intern-Atlas huggingface dataset:
Physical Layer Network Coding Over Finite And Infinite Fields
Venue: arXiv cs.NI 2008
Year: 2008

Direct application of network coding at the physical layer - physical layer network coding (PNC) - is a promising technique for two-way relay wireless networks. In a two-way relay network, relay nodes are used to relay two-way information flows between pairs of end nodes. This paper proposes a precise definition for PNC. Specifically, in PNC, a relay node does not decode the source information from the two ends separately, but rather directly maps the combined signals received simultaneously to a signal to be relayed. Based on this definition, PNC can be further sub-classed into two categories - PNCF (PNC over finite field) and PNCI (PNC over infinite field) - according to whether the network-code field (or groups, rings) adopted is finite or infinite. For each of PNCF and PNCI, we consider two specific estimation techniques for dealing with noise in the mapping process. The performance of the four schemes is investigated by means of analysis and simulation, assuming symbol-level synchronization only.
A Logic Programming Framework for Combinational Circuit Synthesis
Venue: arXiv cs.LO 2008
Year: 2008

Logic Programming languages and combinational circuit synthesis tools share a common "combinatorial search over logic formulae" background. This paper attempts to reconnect the two fields with a fresh look at Prolog encodings for the combinatorial objects involved in circuit synthesis. While benefiting from Prolog's fast unification algorithm and built-in backtracking mechanism, efficiency of our search algorithm is ensured by using parallel bitstring operations together with logic variable equality propagation, as a mapping mechanism from primary inputs to the leaves of candidate Leaf-DAGs implementing a combinational circuit specification. After an exhaustive expressiveness comparison of various minimal libraries, a surprising first-runner, Strict Boolean Inequality "<" together with constant function "1" also turns out to have small transistor-count implementations, competitive to NAND-only or NOR-only libraries. As a practical outcome, a more realistic circuit synthesizer is implemented that combines rewriting-based simplification of (<,1) circuits with exhaustive Leaf-DAG circuit search. Keywords: logic programming and circuit design, combinatorial object generation, exact combinational circuit synthesis, universal boolean logic libraries, symbolic rewriting, minimal transistor-count circuit synthesis
Parimutuel Betting on Permutations
Venue: arXiv cs.GT 2008
Year: 2008

We focus on a permutation betting market under parimutuel call auction model where traders bet on the final ranking of n candidates. We present a Proportional Betting mechanism for this market. Our mechanism allows the traders to bet on any subset of the n x n 'candidate-rank' pairs, and rewards them proportionally to the number of pairs that appear in the final outcome. We show that market organizer's decision problem for this mechanism can be formulated as a convex program of polynomial size. More importantly, the formulation yields a set of n x n unique marginal prices that are sufficient to price the bets in this mechanism, and are computable in polynomial-time. The marginal prices reflect the traders' beliefs about the marginal distributions over outcomes. We also propose techniques to compute the joint distribution over n! permutations from these marginal distributions. We show that using a maximum entropy criterion, we can obtain a concise parametric form (with only n x n parameters) for the joint distribution which is defined over an exponentially large state space. We then present an approximation algorithm for computing the parameters of this distribution. In fact, the algorithm addresses the generic problem of finding the maximum entropy distribution over permutations that has a given mean, and may be of independent interest.
p-Symmetric fuzzy measures
Venue: arXiv cs.DM 2008
Year: 2008

In this paper we propose a generalization of the concept of symmetric fuzzy measure based in a decomposition of the universal set in what we have called subsets of indifference. Some properties of these measures are studied, as well as their Choquet integral. Finally, a degree of interaction between the subsets of indifference is defined.
Philosophical Smoke Signals: Theory and Practice in Information Systems Design
Venue: arXiv cs.SE 2008
Year: 2008

Although the gulf between the theory and practice in Information Systems is much lamented, few researchers have offered a way forward except through a number of (failed) attempts to develop a single systematic theory for Information Systems. In this paper, we encourage researchers to re-examine the practical consequences of their theoretical arguments. By examining these arguments we may be able to form a number of more rigorous theories of Information Systems, allowing us to draw theory and practice together without undertaking yet another attempt at the holy grail of a single unified systematic theory of Information Systems.
Low-Complexity LDPC Codes with Near-Optimum Performance over the BEC
Venue: arXiv cs.IT 2008
Year: 2008

Recent works showed how low-density parity-check (LDPC) erasure correcting codes, under maximum likelihood (ML) decoding, are capable of tightly approaching the performance of an ideal maximum-distance-separable code on the binary erasure channel. Such result is achievable down to low error rates, even for small and moderate block sizes, while keeping the decoding complexity low, thanks to a class of decoding algorithms which exploits the sparseness of the parity-check matrix to reduce the complexity of Gaussian elimination (GE). In this paper the main concepts underlying ML decoding of LDPC codes are recalled. A performance analysis among various LDPC code classes is then carried out, including a comparison with fixed-rate Raptor codes. The results show that LDPC and Raptor codes provide almost identical performance in terms of decoding failure probability vs. overhead.
"E pluribus unum" or How to Derive Single-equation Descriptions for Output-quantities in Nonlinear Circuits using Differential Algebra
Venue: arXiv cs.SC 2008
Year: 2008

In this paper we describe by a number of examples how to deduce one single characterizing higher order differential equation for output quantities of an analog circuit. In the linear case, we apply basic "symbolic" methods from linear algebra to the system of differential equations which is used to model the analog circuit. For nonlinear circuits and their corresponding nonlinear differential equations, we show how to employ computer algebra tools implemented in Maple, which are based on differential algebra.
Experiments in Model-Checking Optimistic Replication Algorithms
Venue: arXiv cs.LO 2008
Year: 2008

This paper describes a series of model-checking experiments to verify optimistic replication algorithms based on Operational Transformation (OT) approach used for supporting collaborative edition. We formally define, using tool UPPAAL, the behavior and the main consistency requirement (i.e. convergence property) of the collaborative editing systems, as well as the abstract behavior of the environment where these systems are supposed to operate. Due to data replication and the unpredictable nature of user interactions, such systems have infinitely many states. So, we show how to exploit some features of the UPPAAL specification language to attenuate the severe state explosion problem. Two models are proposed. The first one, called concrete model, is very close to the system implementation but runs up against a severe explosion of states. The second model, called symbolic model, aims to overcome the limitation of the concrete model by delaying the effective selection and execution of editing operations until the construction of symbolic execution traces of all sites is completed. Experimental results have shown that the symbolic model allows a significant gain in both space and time. Using the symbolic model, we have been able to show that if the number of sites exceeds 2 then the convergence property is not satisfied for all OT algorithms considered here. A counterexample is provided for every algorithm.
A lower bound on web services composition
Venue: arXiv cs.LO 2008
Year: 2008

A web service is modeled here as a finite state machine. A composition problem for web services is to decide if a given web service can be constructed from a given set of web services; where the construction is understood as a simulation of the specification by a fully asynchronous product of the given services. We show an EXPTIME-lower bound for this problem, thus matching the known upper bound. Our result also applies to richer models of web services, such as the Roman model.
Leveraging Coherent Distributed Space-Time Codes for Noncoherent Communication in Relay Networks via Training
Venue: arXiv cs.IT 2008
Year: 2008

For point to point multiple input multiple output systems, Dayal-Brehler-Varanasi have proved that training codes achieve the same diversity order as that of the underlying coherent space time block code (STBC) if a simple minimum mean squared error estimate of the channel formed using the training part is employed for coherent detection of the underlying STBC. In this letter, a similar strategy involving a combination of training, channel estimation and detection in conjunction with existing coherent distributed STBCs is proposed for noncoherent communication in AF relay networks. Simulation results show that the proposed simple strategy outperforms distributed differential space-time coding for AF relay networks. Finally, the proposed strategy is extended to asynchronous relay networks using orthogonal frequency division multiplexing.
Technical Report - Automatic Contour Extraction from 2D Neuron Images
Venue: arXiv cs.CV 2008
Year: 2008

This work describes a novel methodology for automatic contour extraction from 2D images of 3D neurons (e.g. camera lucida images and other types of 2D microscopy). Most contour-based shape analysis methods can not be used to characterize such cells because of overlaps between neuronal processes. The proposed framework is specifically aimed at the problem of contour following even in presence of multiple overlaps. First, the input image is preprocessed in order to obtain an 8-connected skeleton with one-pixel-wide branches, as well as a set of critical regions (i.e., bifurcations and crossings). Next, for each subtree, the tracking stage iteratively labels all valid pixel of branches, up to a critical region, where it determines the suitable direction to proceed. Finally, the labeled skeleton segments are followed in order to yield the parametric contour of the neuronal shape under analysis. The reported system was successfully tested with respect to several images and the results from a set of three neuron images are presented here, each pertaining to a different class, i.e. alpha, delta and epsilon ganglion cells, containing a total of 34 crossings. The algorithms successfully got across all these overlaps. The method has also been found to exhibit robustness even for images with close parallel segments. The proposed method is robust and may be implemented in an efficient manner. The introduction of this approach should pave the way for more systematic application of contour-based shape analysis methods in neuronal morphology.
Electronic Voting: the Devil is in the Details
Venue: arXiv cs.CY 2008
Year: 2008

Observing electronic voting from an international point of view gives some perspective about its genesis and evolution. An analysis of the voting process through its cultural, ontological, legal and political dimensions explains the difficulty to normalize this process. It appears that international organizations are not capable to properly defend the fundamental rights of the citizens. The approach that was taken when DRE voting computers appeared seems to have reoccured with VVAT voting computers and the european e-poll project.
Phoneme recognition in TIMIT with BLSTM-CTC
Venue: arXiv cs.CL 2008
Year: 2008

We compare the performance of a recurrent neural network with the best results published so far on phoneme recognition in the TIMIT database. These published results have been obtained with a combination of classifiers. However, in this paper we apply a single recurrent neural network to the same task. Our recurrent neural network attains an error rate of 24.6%. This result is not significantly different from that obtained by the other best methods, but they rely on a combination of classifiers for achieving comparable performance.
Combinatorial invariants for graph isomorphism problem
Venue: arXiv cs.CC 2008
Year: 2008

Presented approach in polynomial time calculates large number of invariants for each vertex, which won't change with graph isomorphism and should fully determine the graph. For example numbers of closed paths of length k for given starting vertex, what can be though as the diagonal terms of k-th power of the adjacency matrix. For k=2 we would get degree of verities invariant, higher describes local topology deeper. Now if two graphs are isomorphic, they have the same set of such vectors of invariants - we can sort theses vectors lexicographically and compare them. If they agree, permutations from sorting allow to reconstruct the isomorphism. I'm presenting arguments that these invariants should fully determine the graph, but unfortunately I can't prove it in this moment. This approach can give hope, that maybe P=NP - instead of checking all instances, we should make arithmetics on these large numbers.
An $\tilde{O}(n^{2.5})$-Time Algorithm for Online Topological Ordering
Venue: arXiv cs.GT 2008
Year: 2008

We present an $\tilde{O}(n^{2.5})$-time algorithm for maintaining the topological order of a directed acyclic graph with $n$ vertices while inserting $m$ edges.
Effects of Leaders Position and Shape on Aerodynamic Performances of V Flight Formation
Venue: arXiv cs.RO 2008
Year: 2008

The influences of the leader in a group of V flight formation are dealt with. The investigation is focused on the effect of its position and shape on aerodynamics performances of a given V flight formation. Vortices generated the wing tip of the leader moves downstream forming a pair of opposite rotating line vortices. These vortices are generally undesirable because they create a downwash that increases the induced drag on leaders wing. However, this downwash is also accompanied by an upwash that can beneficial to the followers wing flying behind the leaders one, namely a favorable lift for the followers wing. How much contributions of the leaders wing to the followers wing in the V formation flight is determined by the strength of tip vortices generated by the leaders wing which is influenced by its position and shape including incidence angle, dihedral angle, aspect ratio and taper ratio. The prediction of aerodynamic performances of the V flight formation including lift, drag and moment coefficients is numerically performed by solving Navier Stokes equations with k e turbulence model. The computational domain is defined with multiblock topology to capture the complex geometry arrangement of the V flight formation.
Uncorrectable Errors of Weight Half the Minimum Distance for Binary Linear Codes
Venue: arXiv cs.IT 2008
Year: 2008

A lower bound on the number of uncorrectable errors of weight half the minimum distance is derived for binary linear codes satisfying some condition. The condition is satisfied by some primitive BCH codes, extended primitive BCH codes, Reed-Muller codes, and random linear codes. The bound asymptotically coincides with the corresponding upper bound for Reed-Muller codes and random linear codes. By generalizing the idea of the lower bound, a lower bound on the number of uncorrectable errors for weights larger than half the minimum distance is also obtained, but the generalized lower bound is weak for large weights. The monotone error structure and its related notion larger half and trial set, which are introduced by Helleseth, Kløve, and Levenshtein, are mainly used to derive the bounds.
On the Asymptotic Behavior of Selfish Transmitters Sharing a Common Channel
Venue: arXiv cs.IT 2008
Year: 2008

This paper analyzes the asymptotic behavior of a multiple-access network comprising a large number of selfish transmitters competing for access to a common wireless communication channel, and having different utility functions for determining their strategies. A necessary and sufficient condition is given for the total number of packet arrivals from selfish transmitters to converge in distribution. The asymptotic packet arrival distribution at Nash equilibrium is shown to be a mixture of a Poisson distribution and finitely many Bernoulli distributions.
Capacity Definitions for General Channels with Receiver Side Information
Venue: arXiv cs.IT 2008
Year: 2008

We consider three capacity definitions for general channels with channel side information at the receiver, where the channel is modeled as a sequence of finite dimensional conditional distributions not necessarily stationary, ergodic, or information stable. The {\em Shannon capacity} is the highest rate asymptotically achievable with arbitrarily small error probability. The {\em capacity versus outage} is the highest rate asymptotically achievable with a given probability of decoder-recognized outage. The {\em expected capacity} is the highest average rate asymptotically achievable with a single encoder and multiple decoders, where the channel side information determines the decoder in use. As a special case of channel codes for expected rate, the code for capacity versus outage has two decoders: one operates in the non-outage states and decodes all transmitted information, and the other operates in the outage states and decodes nothing. Expected capacity equals Shannon capacity for channels governed by a stationary ergodic random process but is typically greater for general channels. These alternative capacity definitions essentially relax the constraint that all transmitted information must be decoded at the receiver. We derive capacity theorems for these capacity definitions through information density. Numerical examples are provided to demonstrate their connections and differences. We also discuss the implication of these alternative capacity definitions for end-to-end distortion, source-channel coding and separation.
Eppstein's bound on intersecting triangles revisited
Venue: arXiv cs.CG 2008
Year: 2008

Let S be a set of n points in the plane, and let T be a set of m triangles with vertices in S. Then there exists a point in the plane contained in Omega(m^3 / (n^6 log^2 n)) triangles of T. Eppstein (1993) gave a proof of this claim, but there is a problem with his proof. Here we provide a correct proof by slightly modifying Eppstein's argument.
Étude de performance des systèmes de découverte de ressources
Venue: arXiv cs.DC 2008
Year: 2008

The Desktop Grid offers solutions to overcome several challenges and to answer increasingly needs of scientific computing. This technology consists mainly in exploiting PC resources, geographically dispersed, to treat time consuming applications and/or important storage capacity requiring applications. However, as resources number increases, the need for scalability, self-organisation, dynamic reconfiguration, decentralization and performance becomes more and more essential. In this context, this paper evaluates the scalability and performance of P2P tools for registering and discovering services (Publish/Subscribe systems). Three protocols are used in this purpose: Bonjour, Avahi and Pastry. We have studied the behaviour of these protocols related to two criteria: the elapsed time for registrations services and the needed time to discover new services.
Fast Density Codes for Image Data
Venue: arXiv cs.NE 2008
Year: 2008

Recently, a new method for encoding data sets in the form of "Density Codes" was proposed in the literature (Courrieu, 2006). This method allows to compare sets of points belonging to every multidimensional space, and to build shape spaces invariant to a wide variety of affine and non-affine transformations. However, this general method does not take advantage of the special properties of image data, resulting in a quite slow encoding process that makes this tool practically unusable for processing large image databases with conventional computers. This paper proposes a very simple variant of the density code method that directly works on the image function, which is thousands times faster than the original Parzen window based method, without loss of its useful properties.
The Effect of Structural Diversity of an Ensemble of Classifiers on Classification Accuracy
Venue: arXiv cs.LG 2008
Year: 2008

This paper aims to showcase the measure of structural diversity of an ensemble of 9 classifiers and then map a relationship between this structural diversity and accuracy. The structural diversity was induced by having different architectures or structures of the classifiers The Genetical Algorithms (GA) were used to derive the relationship between diversity and the classification accuracy by evolving the classifiers and then picking 9 classifiers out on an ensemble of 60 classifiers. It was found that as the ensemble became diverse the accuracy improved. However at a certain diversity measure the accuracy began to drop. The Kohavi-Wolpert variance method is used to measure the diversity of the ensemble. A method of voting is used to aggregate the results from each classifier. The lowest error was observed at a diversity measure of 0.16 with a mean square error of 0.274, when taking 0.2024 as maximum diversity measured. The parameters that were varied were: the number of hidden nodes, learning rate and the activation function.
The Numerical Control Design for a Pair of Dubins Vehicles
Venue: arXiv cs.RO 2008
Year: 2008

In this paper, a model of a pair of Dubins vehicles is considered. The vehicles move from an initial position and orientation to final position and orientation. A long the motion, the two vehicles are not allowed to collide however the two vehicles cant to far each other. The optimal control of the vehicle is found using the Pontryagins Maximum Principle (PMP). This PMP leads to a Hamiltonian system consisting of a system of differential equation and its adjoint. The originally differential equation has initial and final condition but the adjoint system doesn't have one. The classical difficulty is solved numerically by the greatest gradient descent method. Some simulation results are presented in this paper.
Fast Computation of Moore-Penrose Inverse Matrices
Venue: arXiv cs.NE 2008
Year: 2008

Many neural learning algorithms require to solve large least square systems in order to obtain synaptic weights. Moore-Penrose inverse matrices allow for solving such systems, even with rank deficiency, and they provide minimum-norm vectors of synaptic weights, which contribute to the regularization of the input-output mapping. It is thus of interest to develop fast and accurate algorithms for computing Moore-Penrose inverse matrices. In this paper, an algorithm based on a full rank Cholesky factorization is proposed. The resulting pseudoinverse matrices are similar to those provided by other algorithms. However the computation time is substantially shorter, particularly for large systems.