OpenRaiser/Intern-Atlas huggingface dataset:
Multiple serial episode matching
Venue: arXiv cs.DS 2006
Year: 2006

In a previous paper we generalized the Knuth-Morris-Pratt (KMP) pattern matching algorithm and defined a non-conventional kind of RAM, the MP--RAMs (RAMS equipped with extra operations), and designed an O(n) on-line algorithm for solving the serial episode matching problem on MP--RAMs when there is only one single episode. We here give two extensions of this algorithm to the case when we search for several patterns simultaneously and compare them. More preciseley, given $q+1$ strings (a text $t$ of length $n$ and $q$ patterns $m\_1,...,m\_q$) and a natural number $w$, the {\em multiple serial episode matching problem} consists in finding the number of size $w$ windows of text $t$ which contain patterns $m\_1,...,m\_q$ as subsequences, i.e. for each $m\_i$, if $m\_i=p\_1,..., p\_k$, the letters $p\_1,..., p\_k$ occur in the window, in the same order as in $m\_i$, but not necessarily consecutively (they may be interleaved with other letters).} The main contribution is an algorithm solving this problem on-line in time $O(nq)$.
Derivatives of Entropy Rate in Special Families of Hidden Markov Chains
Venue: arXiv cs.IT 2006
Year: 2006

Consider a hidden Markov chain obtained as the observation process of an ordinary Markov chain corrupted by noise. Zuk, et. al. [13], [14] showed how, in principle, one can explicitly compute the derivatives of the entropy rate of at extreme values of the noise. Namely, they showed that the derivatives of standard upper approximations to the entropy rate actually stabilize at an explicit finite time. We generalize this result to a natural class of hidden Markov chains called ``Black Holes.'' We also discuss in depth special cases of binary Markov chains observed in binary symmetric noise, and give an abstract formula for the first derivative in terms of a measure on the simplex due to Blackwell.
Implementing the Three-Stage Quantum Cryptography Protocol
Venue: arXiv cs.CR 2006
Year: 2006

We present simple implementations of Kak's three-stage quantum cryptography protocol. The case where the transformation is applied to more than one qubit at the same time is also considered.
Universal Lossless Compression with Unknown Alphabets - The Average Case
Venue: arXiv cs.IT 2006
Year: 2006

Universal compression of patterns of sequences generated by independently identically distributed (i.i.d.) sources with unknown, possibly large, alphabets is investigated. A pattern is a sequence of indices that contains all consecutive indices in increasing order of first occurrence. If the alphabet of a source that generated a sequence is unknown, the inevitable cost of coding the unknown alphabet symbols can be exploited to create the pattern of the sequence. This pattern can in turn be compressed by itself. It is shown that if the alphabet size $k$ is essentially small, then the average minimax and maximin redundancies as well as the redundancy of every code for almost every source, when compressing a pattern, consist of at least 0.5 log(n/k^3) bits per each unknown probability parameter, and if all alphabet letters are likely to occur, there exist codes whose redundancy is at most 0.5 log(n/k^2) bits per each unknown probability parameter, where n is the length of the data sequences. Otherwise, if the alphabet is large, these redundancies are essentially at least O(n^{-2/3}) bits per symbol, and there exist codes that achieve redundancy of essentially O(n^{-1/2}) bits per symbol. Two sub-optimal low-complexity sequential algorithms for compression of patterns are presented and their description lengths analyzed, also pointing out that the pattern average universal description length can decrease below the underlying i.i.d.\ entropy for large enough alphabets.
Predicting the Path of an Open System
Venue: arXiv cs.RO 2006
Year: 2006

The expected path of an open system,which is a big Poincare system,has been found in this paper.This path has been obtained from the actual and from the expected droop of the open system.The actual droop has been reconstructed from the variations in the power and in the frequency of the open system.The expected droop has been found as a function of rotation from the expected potential energy of the open system under synchronization of that system.
An Explicit Solution to Post's Problem over the Reals
Venue: arXiv cs.LO 2006
Year: 2006

In the BCSS model of real number computations we prove a concrete and explicit semi-decidable language to be undecidable yet not reducible from (and thus strictly easier than) the real Halting Language. This solution to Post's Problem over the reals significantly differs from its classical, discrete variant where advanced diagonalization techniques are only known to yield the existence of such intermediate Turing degrees. Strengthening the above result, we construct (that is, obtain again explicitly) as well an uncountable number of incomparable semi-decidable Turing degrees below the real Halting problem in the BCSS model. Finally we show the same to hold for the linear BCSS model, that is over (R,+,-,<) rather than (R,+,-,*,/,<).
Peer-to-Peer Communication Across Network Address Translators
Venue: arXiv cs.NI 2006
Year: 2006

Network Address Translation (NAT) causes well-known difficulties for peer-to-peer (P2P) communication, since the peers involved may not be reachable at any globally valid IP address. Several NAT traversal techniques are known, but their documentation is slim, and data about their robustness or relative merits is slimmer. This paper documents and analyzes one of the simplest but most robust and practical NAT traversal techniques, commonly known as "hole punching." Hole punching is moderately well-understood for UDP communication, but we show how it can be reliably used to set up peer-to-peer TCP streams as well. After gathering data on the reliability of this technique on a wide variety of deployed NATs, we find that about 82% of the NATs tested support hole punching for UDP, and about 64% support hole punching for TCP streams. As NAT vendors become increasingly conscious of the needs of important P2P applications such as Voice over IP and online gaming protocols, support for hole punching is likely to increase in the future.
Application of Support Vector Regression to Interpolation of Sparse Shock Physics Data Sets
Venue: arXiv cs.AI 2006
Year: 2006

Shock physics experiments are often complicated and expensive. As a result, researchers are unable to conduct as many experiments as they would like - leading to sparse data sets. In this paper, Support Vector Machines for regression are applied to velocimetry data sets for shock damaged and melted tin metal. Some success at interpolating between data sets is achieved. Implications for future work are discussed.
Novel BCD Adders and Their Reversible Logic Implementation for IEEE 754r Format
Venue: arXiv cs.AR 2006
Year: 2006

IEEE 754r is the ongoing revision to the IEEE 754 floating point standard and a major enhancement to the standard is the addition of decimal format. This paper proposes two novel BCD adders called carry skip and carry look-ahead BCD adders respectively. Furthermore, in the recent years, reversible logic has emerged as a promising technology having its applications in low power CMOS, quantum computing, nanotechnology, and optical computing. It is not possible to realize quantum computing without reversible logic. Thus, this paper also paper provides the reversible logic implementation of the conventional BCD adder as the well as the proposed Carry Skip BCD adder using a recently proposed TSG gate. Furthermore, a new reversible gate called TS-3 is also being proposed and it has been shown that the proposed reversible logic implementation of the BCD Adders is much better compared to recently proposed one, in terms of number of reversible gates used and garbage outputs produced. The reversible BCD circuits designed and proposed here form the basis of the decimal ALU of a primitive quantum CPU.
Topological Grammars for Data Approximation
Venue: arXiv cs.NE 2006
Year: 2006

A method of {\it topological grammars} is proposed for multidimensional data approximation. For data with complex topology we define a {\it principal cubic complex} of low dimension and given complexity that gives the best approximation for the dataset. This complex is a generalization of linear and non-linear principal manifolds and includes them as particular cases. The problem of optimal principal complex construction is transformed into a series of minimization problems for quadratic functionals. These quadratic functionals have a physically transparent interpretation in terms of elastic energy. For the energy computation, the whole complex is represented as a system of nodes and springs. Topologically, the principal complex is a product of one-dimensional continuums (represented by graphs), and the grammars describe how these continuums transform during the process of optimal complex construction. This factorization of the whole process onto one-dimensional transformations using minimization of quadratic energy functionals allow us to construct efficient algorithms.
On the Capacity Achieving Transmit Covariance Matrices of MIMO Correlated Rician Channels: A Large System Approach
Venue: arXiv cs.IT 2006
Year: 2006

We determine the capacity-achieving input covariance matrices for coherent block-fading correlated MIMO Rician channels. In contrast with the Rayleigh and uncorrelated Rician cases, no closed-form expressions for the eigenvectors of the optimum input covariance matrix are available. Both the eigenvectors and eigenvalues have to be evaluated by using numerical techniques. As the corresponding optimization algorithms are not very attractive, we evaluate the limit of the average mutual information when the number of transmit and receive antennas converge to infinity at the same rate. If the channel is semi-correlated, we propose an attractive optimization algorithm of the large system approximant, and establish some convergence results. Simulation results show that our approach provide reliable results even for a quite moderate number of transmit and receive antennas.
Verification of Ptime reducibility for system F terms via Dual Light Affine Logic
Venue: arXiv cs.LO 2006
Year: 2006

In a previous work we introduced Dual Light Affine Logic (DLAL) ([BaillotTerui04]) as a variant of Light Linear Logic suitable for guaranteeing complexity properties on lambda-calculus terms: all typable terms can be evaluated in polynomial time and all Ptime functions can be represented. In the present work we address the problem of typing lambda-terms in second-order DLAL. For that we give a procedure which, starting with a term typed in system F, finds all possible ways to decorate it into a DLAL typed term. We show that our procedure can be run in time polynomial in the size of the original Church typed system F term.
Fourier Analysis and Holographic Representations of 1D and 2D Signals
Venue: arXiv cs.CV 2006
Year: 2006

In this paper, we focus on Fourier analysis and holographic transforms for signal representation. For instance, in the case of image processing, the holographic representation has the property that an arbitrary portion of the transformed image enables reconstruction of the whole image with details missing. We focus on holographic representation defined through the Fourier Transforms. Thus, We firstly review some results in Fourier transform and Fourier series. Next, we review the Discrete Holographic Fourier Transform (DHFT) for image representation. Then, we describe the contributions of our work. We show a simple scheme for progressive transmission based on the DHFT. Next, we propose the Continuous Holographic Fourier Transform (CHFT) and discuss some theoretical aspects of it for 1D signals. Finally, some testes are presented in the experimental results
Affine functions and series with co-inductive real numbers
Venue: arXiv cs.LO 2006
Year: 2006

We extend the work of A. Ciaffaglione and P. Di Gianantonio on mechanical verification of algorithms for exact computation on real numbers, using infinite streams of digits implemented as co-inductive types. Four aspects are studied: the first aspect concerns the proof that digit streams can be related to the axiomatized real numbers that are already axiomatized in the proof system (axiomatized, but with no fixed representation). The second aspect re-visits the definition of an addition function, looking at techniques to let the proof search mechanism perform the effective construction of an algorithm that is correct by construction. The third aspect concerns the definition of a function to compute affine formulas with positive rational coefficients. This should be understood as a testbed to describe a technique to combine co-recursion and recursion to obtain a model for an algorithm that appears at first sight to be outside the expressive power allowed by the proof system. The fourth aspect concerns the definition of a function to compute series, with an application on the series that is used to compute Euler's number e. All these experiments should be reproducible in any proof system that supports co-inductive types, co-recursion and general forms of terminating recursion, but we performed with the Coq system [12, 3, 14].
CoInduction in Coq
Venue: arXiv cs.LO 2006
Year: 2006

We describe the basic notions of co-induction as they are available in the coq system. As an application, we describe arithmetic properties for simple representations of real numbers.
minimUML: A Minimalist Approach to UML Diagraming for Early Computer Science Education
Venue: arXiv cs.HC 2006
Year: 2006

The Unified Modeling Language (UML) is commonly used in introductory Computer Science to teach basic object-oriented design. However, there appears to be a lack of suitable software to support this task. Many of the available programs that support UML focus on developing code and not on enhancing learning. Those that were designed for educational use sometimes have poor interfaces or are missing common and important features, such as multiple selection and undo/redo. There is a need for software that is tailored to an instructional environment and has all the useful and needed functionality for that specific task. This is the purpose of minimUML. minimUML provides a minimum amount of UML, just what is commonly used in beginning programming classes, while providing a simple, usable interface. In particular, minimUML was designed to support abstract design while supplying features for exploratory learning and error avoidance. In addition, it allows for the annotation of diagrams, through text or freeform drawings, so students can receive feedback on their work. minimUML was developed with the goal of supporting ease of use, supporting novice students, and a requirement of no prior-training for its use.
Towards the Optimal Amplify-and-Forward Cooperative Diversity Scheme
Venue: arXiv cs.IT 2006
Year: 2006

In a slow fading channel, how to find a cooperative diversity scheme that achieves the transmit diversity bound is still an open problem. In fact, all previously proposed amplify-and-forward (AF) and decode-and-forward (DF) schemes do not improve with the number of relays in terms of the diversity multiplexing tradeoff (DMT) for multiplexing gains r higher than 0.5. In this work, we study the class of slotted amplify-and-forward (SAF) schemes. We first establish an upper bound on the DMT for any SAF scheme with an arbitrary number of relays N and number of slots M. Then, we propose a sequential SAF scheme that can exploit the potential diversity gain in the high multiplexing gain regime. More precisely, in certain conditions, the sequential SAF scheme achieves the proposed DMT upper bound which tends to the transmit diversity bound when M goes to infinity. In particular, for the two-relay case, the three-slot sequential SAF scheme achieves the proposed upper bound and outperforms the two-relay non-orthorgonal amplify-and-forward (NAF) scheme of Azarian et al. for multiplexing gains r < 2/3. Numerical results reveal a significant gain of our scheme over the previously proposed AF schemes, especially in high spectral efficiency and large network size regime.
Open at the Top; Open at the Bottom; and Continually (but Slowly) Evolving
Venue: arXiv cs.MA 2006
Year: 2006

Systems of systems differ from traditional systems in that they are open at the top, open at the bottom, and continually (but slowly) evolving. "Open at the top" means that there is no pre-defined top level application. New applications may be created at any time. "Open at the bottom" means that the system primitives are defined functionally rather than concretely. This allows the implementation of these primitives to be modified as technology changes. "Continually (but slowly) evolving" means that the system's functionality is stable enough to be useful but is understood to be subject to modification. Systems with these properties tend to be environments within which other systems operate--and hence are systems of systems. It is also important to understand the larger environment within which a system of systems exists.
Towards Analog Reverse Time Computation
Venue: arXiv cs.CC 2006
Year: 2006

We report the consequences of a destabilization process on a simulated General Purpose Analog Computer. This new technology overcomes problems linked with serial ambiguity, and provides an analog bias to encode algorithms whose complexity is over polynomial. We also implicitly demonstrate how countermesures of the Stochastic Aperture Degeneracy could efficiently reach higher computational classes, and would open a road towards Analog Reverse Time Computation.
Revealing the Autonomous System Taxonomy: The Machine Learning Approach
Venue: arXiv cs.NI 2006
Year: 2006

Although the Internet AS-level topology has been extensively studied over the past few years, little is known about the details of the AS taxonomy. An AS "node" can represent a wide variety of organizations, e.g., large ISP, or small private business, university, with vastly different network characteristics, external connectivity patterns, network growth tendencies, and other properties that we can hardly neglect while working on veracious Internet representations in simulation environments. In this paper, we introduce a radically new approach based on machine learning techniques to map all the ASes in the Internet into a natural AS taxonomy. We successfully classify 95.3% of ASes with expected accuracy of 78.1%. We release to the community the AS-level topology dataset augmented with: 1) the AS taxonomy information and 2) the set of AS attributes we used to classify ASes. We believe that this dataset will serve as an invaluable addition to further understanding of the structure and evolution of the Internet.
Adaptative combination rule and proportional conflict redistribution rule for information fusion
Venue: arXiv cs.AI 2006
Year: 2006

This paper presents two new promising rules of combination for the fusion of uncertain and potentially highly conflicting sources of evidences in the framework of the theory of belief functions in order to palliate the well-know limitations of Dempster's rule and to work beyond the limits of applicability of the Dempster-Shafer theory. We present both a new class of adaptive combination rules (ACR) and a new efficient Proportional Conflict Redistribution (PCR) rule allowing to deal with highly conflicting sources for static and dynamic fusion applications.
An exact algorithm for higher-dimensional orthogonal packing
Venue: arXiv cs.DS 2006
Year: 2006

Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Combining the use of our data structure for characterizing feasible packings with our new classes of lower bounds, and other heuristics, we develop a two-level tree search algorithm for solving higher-dimensional packing problems to optimality. Computational results are reported, including optimal solutions for all two--dimensional test problems from recent literature. This is the third in a series of articles describing new approaches to higher-dimensional packing; see cs.DS/0310032 and cs.DS/0402044.
Low SNR Capacity of Fading Channels with Peak and Average Power Constraints
Venue: arXiv cs.IT 2006
Year: 2006

Flat-fading channels that are correlated in time are considered under peak and average power constraints. For discrete-time channels, a new upper bound on the capacity per unit time is derived. A low SNR analysis of a full-scattering vector channel is used to derive a complimentary lower bound. Together, these bounds allow us to identify the exact scaling of channel capacity for a fixed peak to average ratio, as the average power converges to zero. The upper bound is also asymptotically tight as the average power converges to zero for a fixed peak power. For a continuous time infinite bandwidth channel, Viterbi identified the capacity for M-FSK modulation. Recently, Zhang and Laneman showed that the capacity can be achieved with non-bursty signaling (QPSK). An additional contribution of this paper is to obtain similar results under peak and average power constraints.
A Short Note on The Volume of Hypersphere
Venue: arXiv cs.IT 2006
Year: 2006

In this note, a new method for deriving the volume of hypersphere is proposed by using probability theory. The explicit expression of the multiple times convolution of the probability density functions we should use is very complicated. But in here, we don't need its whole explicit expression. We just need the only a part of information and this fact make it possible to derive the general expression of the voulume of hypersphere. We also comments about the paradox in the hypersphere which was introduced by R.W.Hamming.
Effect of E-printing on Citation Rates in Astronomy and Physics
Venue: arXiv cs.DL 2006
Year: 2006

In this report we examine the change in citation behavior since the introduction of the arXiv e-print repository (Ginsparg, 2001). It has been observed that papers that initially appear as arXiv e-prints get cited more than papers that do not (Lawrence, 2001; Brody et al., 2004; Schwarz & Kennicutt, 2004; Kurtz et al., 2005a, Metcalfe, 2005). Using the citation statistics from the NASA-Smithsonian Astrophysics Data System (ADS; Kurtz et al., 1993, 2000), we confirm the findings from other studies, we examine the average citation rate to e-printed papers in the Astrophysical Journal, and we show that for a number of major astronomy and physics journals the most important papers are submitted to the arXiv e-print repository first.
Univariate polynomial real root isolation: Continued Fractions revisited
Venue: arXiv cs.SC 2006
Year: 2006

We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued fraction expansion of real algebraic numbers. One motivation is to explain the method's good performance in practice. We improve the previously known bound by a factor of $d τ$, where $d$ is the polynomial degree and $τ$ bounds the coefficient bitsize, thus matching the current record complexity for real root isolation by exact methods. Namely, the complexity bound is $\sOB(d^4 τ^2)$ using the standard bound on the expected bitsize of the integers in the continued fraction expansion. We show how to compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. Finally, we present an efficient open-source \texttt{C++} implementation in the algebraic library \synaps, and illustrate its efficiency as compared to other available software. We use polynomials with coefficient bitsize up to 8000 and degree up to 1000.