OpenRaiser/Intern-Atlas huggingface dataset:
Verifying nondeterministic probabilistic channel systems against $ω$-regular linear-time properties
Venue: arXiv cs.LO 2006
Year: 2006

Lossy channel systems (LCSs) are systems of finite state automata that communicate via unreliable unbounded fifo channels. In order to circumvent the undecidability of model checking for nondeterministic LCSs, probabilistic models have been introduced, where it can be decided whether a linear-time property holds almost surely. However, such fully probabilistic systems are not a faithful model of nondeterministic protocols. We study a hybrid model for LCSs where losses of messages are seen as faults occurring with some given probability, and where the internal behavior of the system remains nondeterministic. Thus the semantics is in terms of infinite-state Markov decision processes. The purpose of this article is to discuss the decidability of linear-time properties formalized by formulas of linear temporal logic (LTL). Our focus is on the qualitative setting where one asks, e.g., whether a LTL-formula holds almost surely or with zero probability (in case the formula describes the bad behaviors). Surprisingly, it turns out that -- in contrast to finite-state Markov decision processes -- the satisfaction relation for LTL formulas depends on the chosen type of schedulers that resolve the nondeterminism. While all variants of the qualitative LTL model checking problem for the full class of history-dependent schedulers are undecidable, the same questions for finite-memory scheduler can be solved algorithmically. However, the restriction to reachability properties and special kinds of recurrent reachability properties yields decidable verification problems for the full class of schedulers, which -- for this restricted class of properties -- are as powerful as finite-memory schedulers, or even a subclass of them.
MIMO Diversity in the Presence of Double Scattering
Venue: arXiv cs.IT 2006
Year: 2006

The potential benefits of multiple-antenna systems may be limited by two types of channel degradations rank deficiency and spatial fading correlation of the channel. In this paper, we assess the effects of these degradations on the diversity performance of multiple-input multiple-output (MIMO) systems, with an emphasis on orthogonal space-time block codes, in terms of the symbol error probability, the effective fading figure (EFF), and the capacity at low signal-to-noise ratio (SNR). In particular, we consider a general family of MIMO channels known as double-scattering channels, which encompasses a variety of propagation environments from independent and identically distributed Rayleigh to degenerate keyhole or pinhole cases by embracing both rank-deficient and spatial correlation effects. It is shown that a MIMO system with $n_T$ transmit and $n_R$ receive antennas achieves the diversity of order $\frac{\n_T n_S n_R}{\max(n_T,n_S,n_R)}$ in a double-scattering channel with $n_S$ effective scatterers. We also quantify the combined effect of the spatial correlation and the lack of scattering richness on the EFF and the low-SNR capacity in terms of the correlation figures of transmit, receive, and scatterer correlation matrices. We further show the monotonicity properties of these performance measures with respect to the strength of spatial correlation, characterized by the eigenvalue majorization relations of the correlation matrices.
DAMNED: A Distributed and Multithreaded Neural Event-Driven simulation framework
Venue: arXiv cs.NE 2006
Year: 2006

In a Spiking Neural Networks (SNN), spike emissions are sparsely and irregularly distributed both in time and in the network architecture. Since a current feature of SNNs is a low average activity, efficient implementations of SNNs are usually based on an Event-Driven Simulation (EDS). On the other hand, simulations of large scale neural networks can take advantage of distributing the neurons on a set of processors (either workstation cluster or parallel computer). This article presents DAMNED, a large scale SNN simulation framework able to gather the benefits of EDS and parallel computing. Two levels of parallelism are combined: Distributed mapping of the neural topology, at the network level, and local multithreaded allocation of resources for simultaneous processing of events, at the neuron level. Based on the causality of events, a distributed solution is proposed for solving the complex problem of scheduling without synchronization barrier.
Alternating Timed Automata
Venue: arXiv cs.LO 2006
Year: 2006

A notion of alternating timed automata is proposed. It is shown that such automata with only one clock have decidable emptiness problem over finite words. This gives a new class of timed languages which is closed under boolean operations and which has an effective presentation. We prove that the complexity of the emptiness problem for alternating timed automata with one clock is non-primitive recursive. The proof gives also the same lower bound for the universality problem for nondeterministic timed automata with one clock. We investigate extension of the model with epsilon-transitions and prove that emptiness is undecidable. Over infinite words, we show undecidability of the universality problem.
Fundamental Limits and Scaling Behavior of Cooperative Multicasting in Wireless Networks
Venue: arXiv cs.IT 2006
Year: 2006

A framework is developed for analyzing capacity gains from user cooperation in slow fading wireless networks when the number of nodes (network size) is large. The framework is illustrated for the case of a simple multipath-rich Rayleigh fading channel model. Both unicasting (one source and one destination) and multicasting (one source and several destinations) scenarios are considered. We introduce a meaningful notion of Shannon capacity for such systems, evaluate this capacity as a function of signal-to-noise ratio (SNR), and develop a simple two-phase cooperative network protocol that achieves it. We observe that the resulting capacity is the same for both unicasting and multicasting, but show that the network size required to achieve any target error probability is smaller for unicasting than for multicasting. Finally, we introduce the notion of a network ``scaling exponent'' to quantify the rate of decay of error probability with network size as a function of the targeted fraction of the capacity. This exponent provides additional insights to system designers by enabling a finer grain comparison of candidate cooperative transmission protocols in even moderately sized networks.
Analyzing language development from a network approach
Venue: arXiv cs.CL 2006
Year: 2006

In this paper we propose some new measures of language development using network analyses, which is inspired by the recent surge of interests in network studies of many real-world systems. Children's and care-takers' speech data from a longitudinal study are represented as a series of networks, word forms being taken as nodes and collocation of words as links. Measures on the properties of the networks, such as size, connectivity, hub and authority analyses, etc., allow us to make quantitative comparison so as to reveal different paths of development. For example, the asynchrony of development in network size and average degree suggests that children cannot be simply classified as early talkers or late talkers by one or two measures. Children follow different paths in a multi-dimensional space. They may develop faster in one dimension but slower in another dimension. The network approach requires little preprocessing of words and analyses on sentence structures, and the characteristics of words and their usage emerge from the network and are independent of any grammatical presumptions. We show that the change of the two articles "the" and "a" in their roles as important nodes in the network reflects the progress of children's syntactic development: the two articles often start in children's networks as hubs and later shift to authorities, while they are authorities constantly in the adult's networks. The network analyses provide a new approach to study language development, and at the same time language development also presents a rich area for network theories to explore.
Multi-Map Orbit Hopping Chaotic Stream Cipher
Venue: arXiv cs.CR 2006
Year: 2006

In this paper we propose a multi-map orbit hopping chaotic stream cipher that utilizes the idea of spread spectrum mechanism for secure digital communications and fundamental chaos characteristics of mixing, unpredictable, and extremely sensitive to initial conditions. The design, key and subkeys, and detail implementation of the system are addressed. A variable number of well studied chaotic maps form a map bank. And the key determines how the system hops between multiple orbits, and it also determines the number of maps, the number of orbits for each map, and the number of sample points for each orbits. A detailed example is provided.
Further Results on the Distinctness of Decimations of l-sequences
Venue: arXiv cs.CR 2006
Year: 2006

Let $\underline{a}$ be an \textit{l}-sequence generated by a feedback-with-carry shift register with connection integer $q=p^{e}$, where $ p$ is an odd prime and $e\geq 1$. Goresky and Klapper conjectured that when $ p^{e}\notin \{5,9,11,13\}$, all decimations of $\underline{a}$ are cyclically distinct. When $e=1$ and $p>13$, they showed that the set of distinct decimations is large and, in some cases, all deciamtions are distinct. In this article, we further show that when $e\geq 2$ and$ p^{e}\neq 9$, all decimations of $\underline{a}$ are also cyclically distinct.
Efficient Open World Reasoning for Planning
Venue: arXiv cs.AI 2006
Year: 2006

We consider the problem of reasoning and planning with incomplete knowledge and deterministic actions. We introduce a knowledge representation scheme called PSIPLAN that can effectively represent incompleteness of an agent's knowledge while allowing for sound, complete and tractable entailment in domains where the set of all objects is either unknown or infinite. We present a procedure for state update resulting from taking an action in PSIPLAN that is correct, complete and has only polynomial complexity. State update is performed without considering the set of all possible worlds corresponding to the knowledge state. As a result, planning with PSIPLAN is done without direct manipulation of possible worlds. PSIPLAN representation underlies the PSIPOP planning algorithm that handles quantified goals with or without exceptions that no other domain independent planner has been shown to achieve. PSIPLAN has been implemented in Common Lisp and used in an application on planning in a collaborative interface.
The density of iterated crossing points and a gap result for triangulations of finite point sets
Venue: arXiv cs.CG 2006
Year: 2006

Consider a plane graph G, drawn with straight lines. For every pair a,b of vertices of G, we compare the shortest-path distance between a and b in G (with Euclidean edge lengths) to their actual distance in the plane. The worst-case ratio of these two values, for all pairs of points, is called the dilation of G. All finite plane graphs of dilation 1 have been classified. They are closely related to the following iterative procedure. For a given point set P in R^2, we connect every pair of points in P by a line segment and then add to P all those points where two such line segments cross. Repeating this process infinitely often, yields a limit point set P*. The main result of this paper is the following gap theorem: For any finite point set P in the plane for which the above P* is infinite, there exists a threshold t > 1 such that P is not contained in the vertex set of any finite plane graph of dilation at most t. We construct a concrete point set Q such that any planar graph that contains this set amongst its vertices must have a dilation larger than 1.0000047.
Deductive Object Programming
Venue: arXiv cs.SE 2006
Year: 2006

We propose some slight additions to O-O languages to implement the necessary features for using Deductive Object Programming (DOP). This way of programming based upon the manipulation of the Production Tree of the Objects of Interest, result in making Persistent these Objects and in sensibly lowering the code complexity.
Combining Relational Algebra, SQL, Constraint Modelling, and Local Search
Venue: arXiv cs.AI 2006
Year: 2006

The goal of this paper is to provide a strong integration between constraint modelling and relational DBMSs. To this end we propose extensions of standard query languages such as relational algebra and SQL, by adding constraint modelling capabilities to them. In particular, we propose non-deterministic extensions of both languages, which are specially suited for combinatorial problems. Non-determinism is introduced by means of a guessing operator, which declares a set of relations to have an arbitrary extension. This new operator results in languages with higher expressive power, able to express all problems in the complexity class NP. Some syntactical restrictions which make data complexity polynomial are shown. The effectiveness of both extensions is demonstrated by means of several examples. The current implementation, written in Java using local search techniques, is described. To appear in Theory and Practice of Logic Programming (TPLP)
Better than the real thing? Iterative pseudo-query processing using cluster-based language models
Venue: arXiv cs.IR 2006
Year: 2006

We present a novel approach to pseudo-feedback-based ad hoc retrieval that uses language models induced from both documents and clusters. First, we treat the pseudo-feedback documents produced in response to the original query as a set of pseudo-queries that themselves can serve as input to the retrieval process. Observing that the documents returned in response to the pseudo-queries can then act as pseudo-queries for subsequent rounds, we arrive at a formulation of pseudo-query-based retrieval as an iterative process. Experiments show that several concrete instantiations of this idea, when applied in conjunction with techniques designed to heighten precision, yield performance results rivaling those of a number of previously-proposed algorithms, including the standard language-modeling approach. The use of cluster-based language models is a key contributing factor to our algorithms' success.
Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective
Venue: arXiv cs.IT 2006
Year: 2006

An interleaver is a critical component for the channel coding performance of turbo codes. Algebraic constructions are important because they admit analytical designs and simple, practical hardware implementation. The spread factor of an interleaver is a common measure for turbo coding applications. Maximum-spread interleavers are interleavers whose spread factors achieve the upper bound. An infinite sequence of quadratic permutation polynomials over integer rings that generate maximum-spread interleavers is presented. New properties of permutation polynomial interleavers are investigated from an algebraic-geometric perspective resulting in a new non-linearity metric for interleavers. A new interleaver metric that is a function of both the non-linearity metric and the spread factor is proposed. It is numerically demonstrated that the spread factor has a diminishing importance with the block length. A table of good interleavers for a variety of interleaver lengths according to the new metric is listed. Extensive computer simulation results with impressive frame error rates confirm the efficacy of the new metric. Further, when tail-biting constituent codes are used, the resulting turbo codes are quasi-cyclic.
Modular Adaptive System Based on a Multi-Stage Neural Structure for Recognition of 2D Objects of Discontinuous Production
Venue: arXiv cs.RO 2006
Year: 2006

This is a presentation of a new system for invariant recognition of 2D objects with overlapping classes, that can not be effectively recognized with the traditional methods. The translation, scale and partial rotation invariant contour object description is transformed in a DCT spectrum space. The obtained frequency spectrums are decomposed into frequency bands in order to feed different BPG neural nets (NNs). The NNs are structured in three stages - filtering and full rotation invariance; partial recognition; general classification. The designed multi-stage BPG Neural Structure shows very good accuracy and flexibility when tested with 2D objects used in the discontinuous production. The reached speed and the opportunuty for an easy restructuring and reprogramming of the system makes it suitable for application in different applied systems for real time work.
Design of Rate-Compatible Serially Concatenated Convolutional Codes
Venue: arXiv cs.IT 2006
Year: 2006

Recently a powerful class of rate-compatible serially concatenated convolutional codes (SCCCs) have been proposed based on minimizing analytical upper bounds on the error probability in the error floor region. Here this class of codes is further investigated by combining analytical upper bounds with extrinsic information transfer charts analysis. Following this approach, we construct a family of rate-compatible SCCCs with good performance in both the error floor and the waterfall regions over a broad range of code rates.
IDBE - An Intelligent Dictionary Based Encoding Algorithm for Text Data Compression for High Speed Data Transmission Over Internet
Venue: arXiv cs.IT 2006
Year: 2006

Compression algorithms reduce the redundancy in data representation to decrease the storage required for that data. Data compression offers an attractive approach to reducing communication costs by using available bandwidth effectively. Over the last decade there has been an unprecedented explosion in the amount of digital data transmitted via the Internet, representing text, images, video, sound, computer programs, etc. With this trend expected to continue, it makes sense to pursue research on developing algorithms that can most effectively use available network bandwidth by maximally compressing data. This research paper is focused on addressing this problem of lossless compression of text files. Lossless compression researchers have developed highly sophisticated approaches, such as Huffman encoding, arithmetic encoding, the Lempel-Ziv family, Dynamic Markov Compression (DMC), Prediction by Partial Matching (PPM), and Burrows-Wheeler Transform (BWT) based algorithms. However, none of these methods has been able to reach the theoretical best-case compression ratio consistently, which suggests that better algorithms may be possible. One approach for trying to attain better compression ratios is to develop new compression algorithms. An alternative approach, however, is to develop intelligent, reversible transformations that can be applied to a source text that improve an existing, or backend, algorithm's ability to compress. The latter strategy has been explored here.
An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture
Venue: arXiv cs.DS 2006
Year: 2006

In this paper we study the Prefix Sum problem introduced by Fredman. We show that it is possible to perform both update and retrieval in O(1) time simultaneously under a memory model in which individual bits may be shared by several words. We also show that two variants (generalizations) of the problem can be solved optimally in $Θ(\lg N)$ time under the comparison based model of computation.
An Algorithm for Constructing All Families of Codes of Arbitrary Requirement in an OCDMA System
Venue: arXiv cs.IT 2006
Year: 2006

A novel code construction algorithm is presented to find all the possible code families for code reconfiguration in an OCDMA system. The algorithm is developed through searching all the complete subgraphs of a constructed graph. The proposed algorithm is flexible and practical for constructing optical orthogonal codes (OOCs) of arbitrary requirement. Simulation results show that one should choose an appropriate code length in order to obtain sufficient number of code families for code reconfiguration with reasonable cost.
Distributed Kernel Regression: An Algorithm for Training Collaboratively
Venue: arXiv cs.LG 2006
Year: 2006

This paper addresses the problem of distributed learning under communication constraints, motivated by distributed signal processing in wireless sensor networks and data mining with distributed databases. After formalizing a general model for distributed learning, an algorithm for collaboratively training regularized kernel least-squares regression estimators is derived. Noting that the algorithm can be viewed as an application of successive orthogonal projection algorithms, its convergence properties are investigated and the statistical behavior of the estimator is discussed in a simplified theoretical setting.
On the Weight Enumerator and the Maximum Likelihood Performance of Linear Product Codes
Venue: arXiv cs.IT 2006
Year: 2006

Product codes are widely used in data-storage, optical and wireless applications. Their analytical performance evaluation usually relies on the truncated union bound, which provides a low error rate approximation based on the minimum distance term only. In fact, the complete weight enumerator of most product codes remains unknown. In this paper, concatenated representations are introduced and applied to compute the complete average enumerators of arbitrary product codes over a field Fq. The split weight enumerators of some important constituent codes (Hamming, Reed-Solomon) are studied and used in the analysis. The average binary weight enumerators of Reed Solomon product codes are also derived. Numerical results showing the enumerator behavior are presented. By using the complete enumerators, Poltyrev bounds on the maximum likelihood performance, holding at both high and low error rates, are finally shown and compared against truncated union bounds and simulation results.
Compression Scheme for Faster and Secure Data Transmission Over Internet
Venue: arXiv cs.PF 2006
Year: 2006

Compression algorithms reduce the redundancy in data representation to decrease the storage required for that data. Data compression offers an attractive approach to reducing communication costs by using available bandwidth effectively. Over the last decade there has been an unprecedented explosion in the amount of digital data transmitted via the Internet, representing text, images, video, sound, computer programs, etc. With this trend expected to continue, it makes sense to pursue research on developing algorithms that can most effectively use available network bandwidth by maximally compressing data. It is also important to consider the security aspects of the data being transmitted while compressing it, as most of the text data transmitted over the Internet is very much vulnerable to a multitude of attacks. This paper is focused on addressing this problem of lossless compression of text files with an added security.
Pseudorandomness and Combinatorial Constructions
Venue: arXiv cs.CC 2006
Year: 2006

In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of objects with such properties are often very difficult, or unknown. In computer science, probabilistic algorithms are sometimes simpler and more efficient than the best known deterministic algorithms for the same problem. Despite this evidence for the power of random choices, the computational theory of pseudorandomness shows that, under certain complexity-theoretic assumptions, every probabilistic algorithm has an efficient deterministic simulation and a large class of applications of the the probabilistic method can be converted into explicit constructions. In this survey paper we describe connections between the conditional ``derandomization'' results of the computational theory of pseudorandomness and unconditional explicit constructions of certain combinatorial objects such as error-correcting codes and ``randomness extractors.''