OpenRaiser/Intern-Atlas huggingface dataset:
On Universally Decodable Matrices for Space-Time Coding
Venue: arXiv cs.IT 2006
Year: 2006

The notion of universally decodable matrices (UDMs) was recently introduced by Tavildar and Viswanath while studying slow fading channels. It turns out that the problem of constructing UDMs is tightly connected to the problem of constructing maximum distance separable (MDS) codes. In this paper, we first study the properties of UDMs in general and then we discuss an explicit construction of a class of UDMs, a construction which can be seen as an extension of Reed-Solomon codes. In fact, we show that this extension is, in a sense to be made more precise later on, unique. Moreover, the structure of this class of UDMs allows us to answer some open conjectures by Tavildar, Viswanath, and Doshi in the positive, and it also allows us to formulate an efficient decoding algorithm for this class of UDMs. It turns out that our construction yields a coding scheme that is essentially equivalent to a class of codes that was proposed by Rosenbloom and Tsfasman. Moreover, we point out connections to so-called repeated-root cyclic codes.
Exploring high performance distributed file storage using LDPC codes
Venue: arXiv cs.DC 2006
Year: 2006

We explore the feasibility of implementing a reliable, high performance, distributed storage system on a commodity computing cluster. Files are distributed across storage nodes using erasure coding with small Low-Density Parity-Check (LDPC) codes which provide high reliability while keeping the storage and performance overhead small. We present performance measurements done on a prototype system comprising 50 nodes which are self organised using a peer-to-peer overlay.
On Measure Theoretic definitions of Generalized Information Measures and Maximum Entropy Prescriptions
Venue: arXiv cs.IT 2006
Year: 2006

Though Shannon entropy of a probability measure $P$, defined as $- \int_{X} \frac{\ud P}{\ud μ} \ln \frac{\ud P}{\udμ} \ud μ$ on a measure space $(X, \mathfrak{M},μ)$, does not qualify itself as an information measure (it is not a natural extension of the discrete case), maximum entropy (ME) prescriptions in the measure-theoretic case are consistent with that of discrete case. In this paper, we study the measure-theoretic definitions of generalized information measures and discuss the ME prescriptions. We present two results in this regard: (i) we prove that, as in the case of classical relative-entropy, the measure-theoretic definitions of generalized relative-entropies, Rényi and Tsallis, are natural extensions of their respective discrete cases, (ii) we show that, ME prescriptions of measure-theoretic Tsallis entropy are consistent with the discrete case.
Search in Complex Networks : a New Method of Naming
Venue: arXiv cs.NI 2006
Year: 2006

We suggest a method for routing when the source does not posses full information about the shortest path to the destination. The method is particularly useful for scale-free networks, and exploits its unique characteristics. By assigning new (short) names to nodes (aka labelling) we are able to reduce significantly the memory requirement at the routers, yet we succeed in routing with high probability through paths very close in distance to the shortest ones.
A Formal Foundation for ODRL
Venue: arXiv cs.LO 2006
Year: 2006

ODRL is a popular XML-based language for stating the conditions under which resources can be accessed legitimately. The language is described in English and, as a result, agreements written in ODRL are open to interpretation. To address this problem, we propose a formal semantics for a representative fragment of the language. We use this semantics to determine precisely when a permission is implied by a set of ODRL statements and show that answering such questions is a decidable NP-hard problem. Finally, we define a tractable fragment of ODRL that is also fairly expressive.
Comments on Beckmann's Uniform Reducts
Venue: arXiv cs.CC 2006
Year: 2006

Arnold Beckmann defined the uniform reduct of a propositional proof system f to be the set of those bounded arithmetical formulas whose propositional translations have polynomial size f-proofs. We prove that the uniform reduct of f + Extended Frege consists of all true bounded arithmetical formulas iff f + Extended Frege simulates every proof system.
Mutual Information Games in Multi-user Channels with Correlated Jamming
Venue: arXiv cs.IT 2006
Year: 2006

We investigate the behavior of two users and one jammer in an AWGN channel with and without fading when they participate in a non-cooperative zero-sum game, with the channel's input/output mutual information as the objective function. We assume that the jammer can eavesdrop the channel and can use the information obtained to perform correlated jamming. Under various assumptions on the channel characteristics, and the extent of information available at the users and the jammer, we show the existence, or otherwise non-existence of a simultaneously optimal set of strategies for the users and the jammer. In all the cases where the channel is non-fading, we show that the game has a solution, and the optimal strategies are Gaussian signalling for the users and linear jamming for the jammer. In fading channels, we envision each player's strategy as a power allocation function over the channel states, together with the signalling strategies at each channel state. We reduce the game solution to a set of power allocation functions for the players and show that when the jammer is uncorrelated, the game has a solution, but when the jammer is correlated, a set of simultaneously optimal power allocation functions for the users and the jammer does not always exist. In this case, we characterize the max-min user power allocation strategies and the corresponding jammer power allocation strategy.
A Formal Architecture-Centric Model-Driven Approach for the Automatic Generation of Grid Applications
Venue: arXiv cs.SE 2006
Year: 2006

This paper discusses the concept of model-driven software engineering applied to the Grid application domain. As an extension to this concept, the approach described here, attempts to combine both formal architecture-centric and model-driven paradigms. It is a commonly recognized statement that Grid systems have seldom been designed using formal techniques although from past experience such techniques have shown advantages. This paper advocates a formal engineering approach to Grid system developments in an effort to contribute to the rigorous development of Grids software architectures. This approach addresses quality of service and cross-platform developments by applying the model-driven paradigm to a formal architecture-centric engineering method. This combination benefits from a formal semantic description power in addition to model-based transformations. The result of such a novel combined concept promotes the re-use of design models and facilitates developments in Grid computing.
Engineering Conceptual Data Models from Domain Ontologies: A Critical Evaluation
Venue: arXiv cs.SE 2006
Year: 2006

This paper studies the differences and similarities between domain ontologies and conceptual data models and the role that ontologies can play in establishing conceptual data models during the process of information systems development. A mapping algorithm has been proposed and embedded in a special purpose Transformation Engine to generate a conceptual data model from a given domain ontology. Both quantitative and qualitative methods have been adopted to critically evaluate this new approach. In addition, this paper focuses on evaluating the quality of the generated conceptual data model elements using Bunge-Wand-Weber and OntoClean ontologies. The results of this evaluation indicate that the generated conceptual data model provides a high degree of accuracy in identifying the substantial domain entities along with their attributes and relationships being derived from the consensual semantics of domain knowledge. The results are encouraging and support the potential role that this approach can take part in process of information system development.
Conjunctive Queries over Trees
Venue: arXiv cs.DB 2006
Year: 2006

We study the complexity and expressive power of conjunctive queries over unranked labeled trees represented using a variety of structure relations such as ``child'', ``descendant'', and ``following'' as well as unary relations for node labels. We establish a framework for characterizing structures representing trees for which conjunctive queries can be evaluated efficiently. Then we completely chart the tractability frontier of the problem and establish a dichotomy theorem for our axis relations, i.e., we find all subset-maximal sets of axes for which query evaluation is in polynomial time and show that for all other cases, query evaluation is NP-complete. All polynomial-time results are obtained immediately using the proof techniques from our framework. Finally, we study the expressiveness of conjunctive queries over trees and show that for each conjunctive query, there is an equivalent acyclic positive query (i.e., a set of acyclic conjunctive queries), but that in general this query is not of polynomial size.
Reducing Tile Complexity for Self-Assembly Through Temperature Programming
Venue: arXiv cs.CC 2006
Year: 2006

We consider the tile self-assembly model and how tile complexity can be eliminated by permitting the temperature of the self-assembly system to be adjusted throughout the assembly process. To do this, we propose novel techniques for designing tile sets that permit an arbitrary length $m$ binary number to be encoded into a sequence of $O(m)$ temperature changes such that the tile set uniquely assembles a supertile that precisely encodes the corresponding binary number. As an application, we show how this provides a general tile set of size O(1) that is capable of uniquely assembling essentially any $n\times n$ square, where the assembled square is determined by a temperature sequence of length $O(\log n)$ that encodes a binary description of $n$. This yields an important decrease in tile complexity from the required $Ω(\frac{\log n}{\log\log n})$ for almost all $n$ when the temperature of the system is fixed. We further show that for almost all $n$, no tile system can simultaneously achieve both $o(\log n)$ temperature complexity and $o(\frac{\log n}{\log\log n})$ tile complexity, showing that both versions of an optimal square building scheme have been discovered. This work suggests that temperature change can constitute a natural, dynamic method for providing input to self-assembly systems that is potentially superior to the current technique of designing large tile sets with specific inputs hardwired into the tileset.
Game theoretic aspects of distributed spectral coordination with application to DSL networks
Venue: arXiv cs.IT 2006
Year: 2006

In this paper we use game theoretic techniques to study the value of cooperation in distributed spectrum management problems. We show that the celebrated iterative water-filling algorithm is subject to the prisoner's dilemma and therefore can lead to severe degradation of the achievable rate region in an interference channel environment. We also provide thorough analysis of a simple two bands near-far situation where we are able to provide closed form tight bounds on the rate region of both fixed margin iterative water filling (FM-IWF) and dynamic frequency division multiplexing (DFDM) methods. This is the only case where such analytic expressions are known and all previous studies included only simulated results of the rate region. We then propose an alternative algorithm that alleviates some of the drawbacks of the IWF algorithm in near-far scenarios relevant to DSL access networks. We also provide experimental analysis based on measured DSL channels of both algorithms as well as the centralized optimum spectrum management.
Information theory and Thermodynamics
Venue: arXiv cs.IT 2006
Year: 2006

A communication theory for a transmitter broadcasting to many receivers is presented. In this case energetic considerations cannot be neglected as in Shannon theory. It is shown that, when energy is assigned to the information bit, information theory complies with classical thermodynamic and is part of it. To provide a thermodynamic theory of communication it is necessary to define equilibrium for informatics systems that are not in thermal equilibrium and to calculate temperature, heat, and entropy with accordance to Clausius inequality. It is shown that for a binary file the temperature is proportional to the bit energy and that information is thermodynamic entropy. Equilibrium exists in random files that cannot be compressed. Thermodynamic bounds on the computing power of a physical device, and the maximum information that an antenna can broadcast are calculated.
Classifying Signals with Local Classifiers
Venue: arXiv cs.AI 2006
Year: 2006

This paper deals with the problem of classifying signals. The new method for building so called local classifiers and local features is presented. The method is a combination of the lifting scheme and the support vector machines. Its main aim is to produce effective and yet comprehensible classifiers that would help in understanding processes hidden behind classified signals. To illustrate the method we present the results obtained on an artificial and a real dataset.
Finite-State Dimension and Real Arithmetic
Venue: arXiv cs.CC 2006
Year: 2006

We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+alpha, and q*alpha all have the same finite-state dimension and the same finite-state strong dimension. This extends, and gives a new proof of, Wall's 1949 theorem stating that the sum or product of a nonzero rational number and a Borel normal number is always Borel normal.
Cryptanalysis of the CFVZ cryptosystem
Venue: arXiv cs.CR 2006
Year: 2006

The paper analyzes a new public key cryptosystem whose security is based on a matrix version of the discrete logarithm problem over an elliptic curve. It is shown that the complexity of solving the underlying problem for the proposed system is dominated by the complexity of solving a fixed number of discrete logarithm problems in the group of an elliptic curve. Using an adapted Pollard rho algorithm it is shown that this problem is essentially as hard as solving one discrete logarithm problem in the group of an elliptic curve.
PLTL Partitioned Model Checking for Reactive Systems under Fairness Assumptions
Venue: arXiv cs.LO 2006
Year: 2006

We are interested in verifying dynamic properties of finite state reactive systems under fairness assumptions by model checking. The systems we want to verify are specified through a top-down refinement process. In order to deal with the state explosion problem, we have proposed in previous works to partition the reachability graph, and to perform the verification on each part separately. Moreover, we have defined a class, called Bmod, of dynamic properties that are verifiable by parts, whatever the partition. We decide if a property P belongs to Bmod by looking at the form of the Buchi automaton that accepts the negation of P. However, when a property P belongs to Bmod, the property f => P, where f is a fairness assumption, does not necessarily belong to Bmod. In this paper, we propose to use the refinement process in order to build the parts on which the verification has to be performed. We then show that with such a partition, if a property P is verifiable by parts and if f is the expression of the fairness assumptions on a system, then the property f => P is still verifiable by parts. This approach is illustrated by its application to the chip card protocol T=1 using the B engineering design language.
Multilevel Thresholding for Image Segmentation through a Fast Statistical Recursive Algorithm
Venue: arXiv cs.CV 2006
Year: 2006

A novel algorithm is proposed for segmenting an image into multiple levels using its mean and variance. Starting from the extreme pixel values at both ends of the histogram plot, the algorithm is applied recursively on sub-ranges computed from the previous step, so as to find a threshold level and a new sub-range for the next step, until no significant improvement in image quality can be achieved. The method makes use of the fact that a number of distributions tend towards Dirac delta function, peaking at the mean, in the limiting condition of vanishing variance. The procedure naturally provides for variable size segmentation with bigger blocks near the extreme pixel values and finer divisions around the mean or other chosen value for better visualization. Experiments on a variety of images show that the new algorithm effectively segments the image in computationally very less time.
Bisimulations of enrichments
Venue: arXiv cs.LO 2006
Year: 2006

In this paper we show that classical notions from automata theory such as simulation and bisimulation can be lifted to the context of enriched categories. The usual properties of bisimulation are nearly all preserved in this new context. The class of enriched functors that correspond to functionnal bisimulations surjective on objects is investigated and appears "nearly" open in the sense of Joyal and Moerdijk. Seeing the change of base techniques as a convenient means to define process refinement/abstractions, we give sufficient conditions for the change of base categories to preserve bisimularity. We apply these concepts to Betti's generalized automata, categorical transition systems, and other exotic categories.
Pseudo-Codeword Analysis of Tanner Graphs from Projective and Euclidean Planes
Venue: arXiv cs.IT 2006
Year: 2006

In order to understand the performance of a code under maximum-likelihood (ML) decoding, one studies the codewords, in particular the minimal codewords, and their Hamming weights. In the context of linear programming (LP) decoding, one's attention needs to be shifted to the pseudo-codewords, in particular to the minimal pseudo-codewords, and their pseudo-weights. In this paper we investigate some families of codes that have good properties under LP decoding, namely certain families of low-density parity-check (LDPC) codes that are derived from projective and Euclidean planes: we study the structure of their minimal pseudo-codewords and give lower bounds on their pseudo-weight.
Feedback Capacity of Stationary Gaussian Channels
Venue: arXiv cs.IT 2006
Year: 2006

The feedback capacity of additive stationary Gaussian noise channels is characterized as the solution to a variational problem. Toward this end, it is proved that the optimal feedback coding scheme is stationary. When specialized to the first-order autoregressive moving average noise spectrum, this variational characterization yields a closed-form expression for the feedback capacity. In particular, this result shows that the celebrated Schalkwijk-Kailath coding scheme achieves the feedback capacity for the first-order autoregressive moving average Gaussian channel, positively answering a long-standing open problem studied by Butman, Schalkwijk-Tiernan, Wolfowitz, Ozarow, Ordentlich, Yang-Kavcic-Tatikonda, and others. More generally, it is shown that a k-dimensional generalization of the Schalkwijk-Kailath coding scheme achieves the feedback capacity for any autoregressive moving average noise spectrum of order k. Simply put, the optimal transmitter iteratively refines the receiver's knowledge of the intended message.
Epsilon-Unfolding Orthogonal Polyhedra
Venue: arXiv cs.CG 2006
Year: 2006

An unfolding of a polyhedron is produced by cutting the surface and flattening to a single, connected, planar piece without overlap (except possibly at boundary points). It is a long unsolved problem to determine whether every polyhedron may be unfolded. Here we prove, via an algorithm, that every orthogonal polyhedron (one whose faces meet at right angles) of genus zero may be unfolded. Our cuts are not necessarily along edges of the polyhedron, but they are always parallel to polyhedron edges. For a polyhedron of n vertices, portions of the unfolding will be rectangular strips which, in the worst case, may need to be as thin as epsilon = 1/2^{Omega(n)}.
Complete Enumeration of Stopping Sets of Full-Rank Parity-Check Matrices of Hamming Codes
Venue: arXiv cs.IT 2006
Year: 2006

Stopping sets, and in particular their numbers and sizes, play an important role in determining the performance of iterative decoders of linear codes over binary erasure channels. In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this correspondence, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix.
An Achievability Result for the General Relay Channel
Venue: arXiv cs.IT 2006
Year: 2006

See cs.IT/0605135: R. Dabora, S. D. Servetto; On the Role of Estimate-and-Forward with Time-Sharing in Cooperative Communications.
A Measure of Space for Computing over the Reals
Venue: arXiv cs.CC 2006
Year: 2006

We propose a new complexity measure of space for the BSS model of computation. We define LOGSPACE\_W and PSPACE\_W complexity classes over the reals. We prove that LOGSPACE\_W is included in NC^2\_R and in P\_W, i.e. is small enough for being relevant. We prove that the Real Circuit Decision Problem is P\_R-complete under LOGSPACE\_W reductions, i.e. that LOGSPACE\_W is large enough for containing natural algorithms. We also prove that PSPACE\_W is included in PAR\_R.
The Snowblower Problem
Venue: arXiv cs.DS 2006
Year: 2006

We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower passes over each region along the tour, it displaces snow into a nearby region. The constraint is that if the snow is piled too high, then the snowblower cannot clear the pile. We give an algorithmic study of the SBP. We show that in general, the problem is NP-complete, and we present polynomial-time approximation algorithms for removing snow under various assumptions about the operation of the snowblower. Most commercially-available snowblowers allow the user to control the direction in which the snow is thrown. We differentiate between the cases in which the snow can be thrown in any direction, in any direction except backwards, and only to the right. For all cases, we give constant-factor approximation algorithms; the constants increase as the throw direction becomes more restricted. Our results are also applicable to robotic vacuuming (or lawnmowing) with bounded capacity dust bin and to some versions of material-handling problems, in which the goal is to rearrange cartons on the floor of a warehouse.