OpenRaiser/Intern-Atlas huggingface dataset:
Parsimony Principles for Software Components and Metalanguages
Venue: arXiv cs.SE 2007
Year: 2007

Software is a communication system. The usual topic of communication is program behavior, as encoded by programs. Domain-specific libraries are codebooks, domain-specific languages are coding schemes, and so forth. To turn metaphor into method, we adapt toolsfrom information theory--the study of efficient communication--to probe the efficiency with which languages and libraries let us communicate programs. In previous work we developed an information-theoretic analysis of software reuse in problem domains. This new paper uses information theory to analyze tradeoffs in the design of components, generators, and metalanguages. We seek answers to two questions: (1) How can we judge whether a component is over- or under-generalized? Drawing on minimum description length principles, we propose that the best component yields the most succinct representation of the use cases. (2) If we view a programming language as an assemblage of metalanguages, each providing a complementary style of abstraction, how can these metalanguages aid or hinder us in efficiently describing software? We describe a complex triangle of interactions between the power of an abstraction mechanism, the amount of reuse it enables, and the cognitive difficulty of its use.
Reductionism, emergence, and levels of abstractions
Venue: arXiv cs.OH 2007
Year: 2007

Can there be independent higher level laws of nature if everything is reducible to the fundamental laws of physics? The computer science notion of level of abstraction explains why there can -- illustrating how computational thinking can solve one of philosophy's most vexing problems.
Embedded Rank Distance Codes for ISI channels
Venue: arXiv cs.IT 2007
Year: 2007

Designs for transmit alphabet constrained space-time codes naturally lead to questions about the design of rank distance codes. Recently, diversity embedded multi-level space-time codes for flat fading channels have been designed from sets of binary matrices with rank distance guarantees over the binary field by mapping them onto QAM and PSK constellations. In this paper we demonstrate that diversity embedded space-time codes for fading Inter-Symbol Interference (ISI) channels can be designed with provable rank distance guarantees. As a corollary we obtain an asymptotic characterization of the fixed transmit alphabet rate-diversity trade-off for multiple antenna fading ISI channels. The key idea is to construct and analyze properties of binary matrices with a particular structure induced by ISI channels.
Linear-programming Decoding of Non-binary Linear Codes
Venue: arXiv cs.IT 2007
Year: 2007

We develop a framework for linear-programming (LP) decoding of non-binary linear codes over rings. We prove that the resulting LP decoder has the `maximum likelihood certificate' property, and we show that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. LP decoding performance is illustrated for the (11,6,5) ternary Golay code with ternary PSK modulation over AWGN, and in this case it is shown that the LP decoder performance is comparable to codeword-error-rate-optimum hard-decision based decoding.
Blocking a transition in a Free Choice net and what it tells about its throughput
Venue: arXiv cs.OH 2007
Year: 2007

In a live and bounded Free Choice Petri net, pick a non-conflicting transition. Then there exists a unique reachable marking in which no transition is enabled except the selected one. For a routed live and bounded Free Choice net, this property is true for any transition of the net. Consider now a live and bounded stochastic routed Free Choice net, and assume that the routings and the firing times are independent and identically distributed. Using the above results, we prove the existence of asymptotic firing throughputs for all transitions in the net. Furthermore the vector of the throughputs at the different transitions is explicitly computable up to a multiplicative constant.
Separation Logic for Small-step Cminor
Venue: arXiv cs.PL 2007
Year: 2007

Cminor is a mid-level imperative programming language; there are proved-correct optimizing compilers from C to Cminor and from Cminor to machine language. We have redesigned Cminor so that it is suitable for Hoare Logic reasoning and we have designed a Separation Logic for Cminor. In this paper, we give a small-step semantics (instead of the big-step of the proved-correct compiler) that is motivated by the need to support future concurrent extensions. We detail a machine-checked proof of soundness of our Separation Logic. This is the first large-scale machine-checked proof of a Separation Logic w.r.t. a small-step semantics. The work presented in this paper has been carried out in the Coq proof assistant. It is a first step towards an environment in which concurrent Cminor programs can be verified using Separation Logic and also compiled by a proved-correct compiler with formal end-to-end correctness guarantees.
Small weakly universal Turing machines
Venue: arXiv cs.CC 2007
Year: 2007

We give small universal Turing machines with state-symbol pairs of (6, 2), (3, 3) and (2, 4). These machines are weakly universal, which means that they have an infinitely repeated word to the left of their input and another to the right. They simulate Rule 110 and are currently the smallest known weakly universal Turing machines.
Network synchronizability analysis: the theory of subgraphs and complementary graphs
Venue: arXiv cs.NI 2007
Year: 2007

In this paper, subgraphs and complementary graphs are used to analyze the network synchronizability. Some sharp and attainable bounds are provided for the eigenratio of the network structural matrix, which characterizes the network synchronizability, especially when the network's corresponding graph has cycles, chains, bipartite graphs or product graphs as its subgraphs.
Virtual Environments for Training: From Individual Learning to Collaboration with Humanoids
Venue: arXiv cs.GR 2007
Year: 2007

The next generation of virtual environments for training is oriented towards collaborative aspects. Therefore, we have decided to enhance our platform for virtual training environments, adding collaboration opportunities and integrating humanoids. In this paper we put forward a model of humanoid that suits both virtual humans and representations of real users, according to collaborative training activities. We suggest adaptations to the scenario model of our platform making it possible to write collaborative procedures. We introduce a mechanism of action selection made up of a global repartition and an individual choice. These models are currently being integrated and validated in GVT, a virtual training tool for maintenance of military equipments, developed in collaboration with the French company NEXTER-Group.
A Portal Analysis for the Design of a Collaborative Research Environment for Students and Supervisors (CRESS) within the CSCR Domain
Venue: arXiv cs.HC 2007
Year: 2007

In a previous paper the CSCR domain was defined. Here this is taken to the next stage where we consider the design of a particular Collaborative Research Environment to support Students and Supervisors CRESS. Following the CSCR structure a preliminary design for CRESS has been established and a portal framework analysis is undertaken in order to determine the most appropriate set of tools for its implementation.
Nearly MDS expander codes with reduced alphabet size
Venue: arXiv cs.IT 2007
Year: 2007

Recently, Roth and Skachek proposed two methods for constructing nearly maximum-distance separable (MDS) expander codes. We show that through the simple modification of using mixed-alphabet codes derived from MDS codes as constituent codes in their code designs, one can obtain nearly MDS codes of significantly smaller alphabet size, albeit at the expense of a (very slight) reduction in code rate.
Achievable Outage Rates with Improved Decoding of Bicm Multiband Ofdm Under Channel Estimation Errors
Venue: arXiv cs.NI 2007
Year: 2007

We consider the decoding of bit interleaved coded modulation (BICM) applied to multiband OFDM for practical scenarios where only a noisy (possibly very bad) estimate of the channel is available at the receiver. First, a decoding metric based on the channel it a posteriori probability density, conditioned on the channel estimate is derived and used for decoding BICM multiband OFDM. Then, we characterize the limits of reliable information rates in terms of the maximal achievable outage rates associated to the proposed metric. We also compare our results with the outage rates of a system using a theoretical decoder. Our results are useful for designing a communication system where a prescribed quality of service (QoS), in terms of achievable target rates with small error probability, must be satisfied even in the presence of imperfect channel estimation. Numerical results over both realistic UWB and theoretical Rayleigh fading channels show that the proposed method provides significant gain in terms of BER and outage rates compared to the classical mismatched detector, without introducing any additional complexity.
A Data-Parallel Version of Aleph
Venue: arXiv cs.AI 2007
Year: 2007

This is to present work on modifying the Aleph ILP system so that it evaluates the hypothesised clauses in parallel by distributing the data-set among the nodes of a parallel or distributed machine. The paper briefly discusses MPI, the interface used to access message- passing libraries for parallel computers and clusters. It then proceeds to describe an extension of YAP Prolog with an MPI interface and an implementation of data-parallel clause evaluation for Aleph through this interface. The paper concludes by testing the data-parallel Aleph on artificially constructed data-sets.
Construction of a 3-Dimensional MDS code
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we describe a procedure for constructing $q$--ary $[N,3,N-2]$--MDS codes, of length $N\leq q+1$ (for $q$ odd) or $N\leq q+2$ (for $q$ even), using a set of non--degenerate Hermitian forms in $PG(2,q^2)$.
Solving the subset-sum problem with a light-based device
Venue: arXiv cs.AR 2007
Year: 2007

We propose a special computational device which uses light rays for solving the subset-sum problem. The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. The nodes are connected by arcs in a special way which lets us to generate all possible subsets of the given set. To each arc we assign either a number from the given set or a predefined constant. When the light is passing through an arc it is delayed by the amount of time indicated by the number placed in that arc. At the destination node we will check if there is a ray whose total delay is equal to the target value of the subset sum problem (plus some constants).
Who is the best connected EC researcher? Centrality analysis of the complex network of authors in evolutionary computation
Venue: arXiv cs.CY 2007
Year: 2007

Co-authorship graphs (that is, the graph of authors linked by co-authorship of papers) are complex networks, which expresses the dynamics of a complex system. Only recently its study has started to draw interest from the EC community, the first paper dealing with it having been published two years ago. In this paper we will study the co-authorship network of EC at a microscopic level. Our objective is ascertaining which are the most relevant nodes (i.e. authors) in it. For this purpose, we examine several metrics defined in the complex-network literature, and analyze them both in isolation and combined within a Pareto-dominance approach. The result of our analysis indicates that there are some well-known researchers that appear systematically in top rankings. This also provides some hints on the social behavior of our community.
Unsatisfiable Linear k-CNFs Exist, for every k
Venue: arXiv cs.DM 2007
Year: 2007

We call a CNF formula linear if any two clauses have at most one variable in common. Let Linear k-SAT be the problem of deciding whether a given linear k-CNF formula is satisfiable. Here, a k-CNF formula is a CNF formula in which every clause has size exactly k. It was known that for k >= 3, Linear k-SAT is NP-complete if and only if an unsatisfiable linear k-CNF formula exists, and that they do exist for k >= 4. We prove that unsatisfiable linear k-CNF formulas exist for every k. Let f(k) be the minimum number of clauses in an unsatisfiable linear k-CNF formula. We show that f(k) is Omega(k2^k) and O(4^k*k^4), i.e., minimum size unsatisfiable linear k-CNF formulas are significantly larger than minimum size unsatisfiable k-CNF formulas. Finally, we prove that, surprisingly, linear k-CNF formulas do not allow for a larger fraction of clauses to be satisfied than general k-CNF formulas.
A structure from motion inequality
Venue: arXiv cs.CV 2007
Year: 2007

We state an elementary inequality for the structure from motion problem for m cameras and n points. This structure from motion inequality relates space dimension, camera parameter dimension, the number of cameras and number points and global symmetry properties and provides a rigorous criterion for which reconstruction is not possible with probability 1. Mathematically the inequality is based on Frobenius theorem which is a geometric incarnation of the fundamental theorem of linear algebra. The paper also provides a general mathematical formalism for the structure from motion problem. It includes the situation the points can move while the camera takes the pictures.
On Ullman's theorem in computer vision
Venue: arXiv cs.CV 2007
Year: 2007

Both in the plane and in space, we invert the nonlinear Ullman transformation for 3 points and 3 orthographic cameras. While Ullman's theorem assures a unique reconstruction modulo a reflection for 3 cameras and 4 points, we find a locally unique reconstruction for 3 cameras and 3 points. Explicit reconstruction formulas allow to decide whether picture data of three cameras seeing three points can be realized as a point-camera configuration.
Secure Communications over Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

The fading wire-tap channel is investigated, where the source-to-destination channel and the source-to-wire-tapper channel are corrupted by multiplicative fading gain coefficients in addition to additive Gaussian noise terms. The channel state information is assumed to be known at both the transmitter and the receiver. The parallel wire-tap channel with independent subchannels is first studied, which serves as an information-theoretic model for the fading wire-tap channel. The secrecy capacity of the parallel wire-tap channel is established. This result is then specialized to give the secrecy capacity of the fading wire-tap channel, which is achieved with the source node dynamically changing the power allocation according to the channel state realization. An optimal source power allocation is obtained to achieve the secrecy capacity.
On a linear code from a configuration of affine lines
Venue: arXiv cs.IT 2007
Year: 2007

We will show how to obtain a linear code from a configuration of affine lines in general position and a suitable set of rational points. We will also explain a new decoding algorithm based on the configuration, which seems to be quite effective.
Integrating users' needs into multimedia information retrieval system
Venue: arXiv cs.IR 2007
Year: 2007

The exponential growth of multimedia information and the development of various communication media generated new problems at various levels including the rate of flow of information, problems of storage and management. The difficulty which arises is no longer the existence of information but rather the access to this information. When designing multimedia information retrieval system, it is appropriate to bear in mind the potential users and their information needs. We assumed that multimedia information representation which takes into account explicitly the users' needs and the cases of use could contribute to the adaptation potentials of the system for the end-users. We believe also that responses of multimedia information system would be more relevant to the users' needs if the types of results to be used from the system were identified before the design and development of the system. We propose the integration of the users' information needs. More precisely integrating usage contexts of resulting information in an information system (during creation and feedback) should enhance more pertinent users' need. The first section of this study is dedicated to traditional multimedia information systems and specifically the approaches of representing multimedia information. Taking into account the dynamism of users, these approaches do not permit the explicit integration of the users' information needs. In this paper, we will present our proposals based on economic intelligence approach. This approach emphasizes the importance of starting any process of information retrieval witch the user information need.
Efficient FPGA-based multipliers for F_{3^97} and F_{3^{6*97}}
Venue: arXiv cs.CR 2007
Year: 2007

In this work we present a new structure for multiplication in finite fields. This structure is based on a digit-level LFSR (Linear Feedback Shift Register) multiplier in which the area of digit-multipliers are reduced using the Karatsuba method. We compare our results with the other works in the literature for F_{3^97}. We also propose new formulas for multiplication in F_{3^{6*97}}. These new formulas reduce the number of F_{3^97}-multiplications from 18 to 15. The fields F_{3^{97}} and F_{3^{6*97}} are relevant in the context of pairing-based cryptography.
Browsing through 3D representations of unstructured picture collections: an empirical study
Venue: arXiv cs.HC 2007
Year: 2007

The paper presents a 3D interactive representation of fairly large picture collections which facilitates browsing through unstructured sets of icons or pictures. Implementation of this representation implies choosing between two visualization strategies: users may either manipulate the view (OV) or be immersed in it (IV). The paper first presents this representation, then describes an empirical study (17 participants) aimed at assessing the utility and usability of each view. Subjective judgements in questionnaires and debriefings were varied: 7 participants preferred the IV view, 4 the OV one, and 6 could not choose between the two. Visual acuity and visual exploration strategies seem to have exerted a greater influence on participants' preferences than task performance or feeling of immersion.
A Non Parametric Study of the Volatility of the Economy as a Country Risk Predictor
Venue: arXiv cs.CE 2007
Year: 2007

This paper intends to explain Venezuela's country spread behavior through the Neural Networks analysis of a monthly economic activity general index of economic indicators constructed by the Central Bank of Venezuela, a measure of the shocks affecting country risk of emerging markets and the U.S. short term interest rate. The use of non parametric methods allowed the finding of non linear relationship between these inputs and the country risk. The networks performance was evaluated using the method of excess predictability.
Networked Multiple Description Estimation and Compression with Resource Scalability
Venue: arXiv cs.IT 2007
Year: 2007

We present a joint source-channel multiple description (JSC-MD) framework for resource-constrained network communications (e.g., sensor networks), in which one or many deprived encoders communicate a Markov source against bit errors and erasure errors to many heterogeneous decoders, some powerful and some deprived. To keep the encoder complexity at minimum, the source is coded into K descriptions by a simple multiple description quantizer (MDQ) with neither entropy nor channel coding. The code diversity of MDQ and the path diversity of the network are exploited by decoders to correct transmission errors and improve coding efficiency. A key design objective is resource scalability: powerful nodes in the network can perform JSC-MD distributed estimation/decoding under the criteria of maximum a posteriori probability (MAP) or minimum mean-square error (MMSE), while primitive nodes resort to simpler MD decoding, all working with the same MDQ code. The application of JSC-MD to distributed estimation of hidden Markov models in a sensor network is demonstrated. The proposed JSC-MD MAP estimator is an algorithm of the longest path in a weighted directed acyclic graph, while the JSC-MD MMSE decoder is an extension of the well-known forward-backward algorithm to multiple descriptions. Both algorithms simultaneously exploit the source memory, the redundancy of the fixed-rate MDQ, and the inter-description correlations. They outperform the existing hard-decision MDQ decoders by large margins (up to 8dB). For Gaussian Markov sources, the complexity of JSC-MD distributed MAP sequence estimation can be made as low as that of typical single description Viterbi-type algorithms.
On the Distortion of the Eigenvalue Spectrum in MIMO Amplify-and-Forward Multi-Hop Channels
Venue: arXiv cs.IT 2007
Year: 2007

Consider a wireless MIMO multi-hop channel with n_s non-cooperating source antennas and n_d fully cooperating destination antennas, as well as L clusters containing k non-cooperating relay antennas each. The source signal traverses all L clusters of relay antennas, before it reaches the destination. When relay antennas within the same cluster scale their received signals by the same constant before the retransmission, the equivalent channel matrix H relating the input signals at the source antennas to the output signals at the destination antennas is proportional to the product of channel matrices H_l, l=1,...,L+1, corresponding to the individual hops. We perform an asymptotic capacity analysis for this channel as follows: In a first instance we take the limits n_s->infty, n_d->infty and k->infty, but keep both n_s/n_d and k/n_d fixed. Then, we take the limits L->infty and k/n_d->infty. Requiring that the H_l's satisfy the conditions needed for the Marcenko-Pastur law, we prove that the capacity scales linearly in min{n_s,n_d}, as long as the ratio k/n_d scales at least linearly in L. Moreover, we show that up to a noise penalty and a pre-log factor the capacity of a point-to-point MIMO channel is approached, when this scaling is slightly faster than linear. Conversely, almost all spatial degrees of freedom vanish for less than linear scaling.
On the Outage Capacity of a Practical Decoder Accounting for Channel Estimation Inaccuracies
Venue: arXiv cs.IT 2007
Year: 2007

The optimal decoder achieving the outage capacity under imperfect channel estimation is investigated. First, by searching into the family of nearest neighbor decoders, which can be easily implemented on most practical coded modulation systems, we derive a decoding metric that minimizes the average of the transmission error probability over all channel estimation errors. Next, we specialize our general expression to obtain the corresponding decoding metric for fading MIMO channels. According to the notion of estimation-induced outage (EIO) capacity introduced in our previous work and assuming no channel state information (CSI) at the transmitter, we characterize maximal achievable information rates, using Gaussian codebooks, associated to the proposed decoder. In the case of uncorrelated Rayleigh fading, these achievable rates are compared to the rates achieved by the classical mismatched maximum-likelihood (ML) decoder and the ultimate limits given by the EIO capacity. Numerical results show that the derived metric provides significant gains for the considered scenario, in terms of achievable information rates and bit error rate (BER), in a bit interleaved coded modulation (BICM) framework, without introducing any additional decoding complexity.