OpenRaiser/Intern-Atlas huggingface dataset:
An Improved Scheme for Initial Ranging in OFDMA-based Networks
Venue: arXiv cs.IT 2008
Year: 2008

An efficient scheme for initial ranging has recently been proposed by X. Fu et al. in the context of orthogonal frequency-division multiple-access (OFDMA) networks based on the IEEE 802.16e-2005 standard. The proposed solution aims at estimating the power levels and timing offsets of the ranging subscriber stations (RSSs) without taking into account the effect of possible carrier frequency offsets (CFOs) between the received signals and the base station local reference. Motivated by the above problem, in the present work we design a novel ranging scheme for OFDMA in which the ranging signals are assumed to be misaligned both in time and frequency. Our goal is to estimate the timing errors and CFOs of each active RSS. Specifically, CFO estimation is accomplished by resorting to subspacebased methods while a least-squares approach is employed for timing recovery. Computer simulations are used to assess the effectiveness of the proposed solution and to make comparisons with existing alternatives.
Automated Termination Proofs for Logic Programs by Term Rewriting
Venue: arXiv cs.LO 2008
Year: 2008

There are two kinds of approaches for termination analysis of logic programs: "transformational" and "direct" ones. Direct approaches prove termination directly on the basis of the logic program. Transformational approaches transform a logic program into a term rewrite system (TRS) and then analyze termination of the resulting TRS instead. Thus, transformational approaches make all methods previously developed for TRSs available for logic programs as well. However, the applicability of most existing transformations is quite restricted, as they can only be used for certain subclasses of logic programs. (Most of them are restricted to well-moded programs.) In this paper we improve these transformations such that they become applicable for any definite logic program. To simulate the behavior of logic programs by TRSs, we slightly modify the notion of rewriting by permitting infinite terms. We show that our transformation results in TRSs which are indeed suitable for automated termination analysis. In contrast to most other methods for termination of logic programs, our technique is also sound for logic programming without occur check, which is typically used in practice. We implemented our approach in the termination prover AProVE and successfully evaluated it on a large collection of examples.
Mobile Agents for Content-Based WWW Distributed Image Retrieval
Venue: arXiv cs.DC 2008
Year: 2008

At present, the de-facto standard for providing contents in the Internet is the World Wide Web. A technology, which is now emerging on the Web, is Content-Based Image Retrieval (CBIR). CBIR applies methods and algorithms from computer science to analyse and index images based on their visual content. Mobile agents push the flexibility of distributed systems to their limits since not only computations are dynamically distributed but also the code that performs them. The current commercial applet-based methodologies for accessing image database systems offer limited flexibility, scalability and robustness. In this paper the author proposes a new framework for content-based WWW distributed image retrieval based on Java-based mobile agents. The implementation of the framework shows that its performance is comparable to, and in some cases outperforms, the current approach.
A compact topology for sand automata
Venue: arXiv cs.CC 2008
Year: 2008

In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. We show that the existing topological results for sand automata, including the Hedlund-like representation theorem, still hold. In this context, we give a characterization of the cellular automata which are sand automata, and study some dynamical behaviors such as equicontinuity. Furthermore, we deal with the nilpotency. We show that the classical definition is not meaningful for sand automata. Then, we introduce a suitable new notion of nilpotency for sand automata. Finally, we prove that this simple dynamical behavior is undecidable.
A Software Development Methodology for Research and Prototyping in Financial Markets
Venue: arXiv cs.SE 2008
Year: 2008

The objective of this paper is to develop a standardized methodology for software development in the very unique industry and culture of financial markets. The prototyping process we present allows the development team to deliver for review and comment intermediate-level models based upon clearly defined customer requirements. This spreadsheet development methodology is presented within a larger business context, that of trading system development, the subject of an upcoming book by the authors of this paper.
Rapid Spreadsheet Reshaping with Excelsior: multiple drastic changes to content and layout are easy when you represent enough structure
Venue: arXiv cs.SE 2008
Year: 2008

Spreadsheets often need changing in ways made tedious and risky by Excel. For example: simultaneously altering many tables' size, orientation, and position; inserting cross-tabulations; moving data between sheets; splitting and merging sheets. A safer, faster restructuring tool is, we claim, Excelsior. The result of a research project into reducing spreadsheet risk, Excelsior is the first ever tool for modularising spreadsheets; i.e. for building them from components which can be independently created, tested, debugged, and updated. It represents spreadsheets in a way that makes these components explicit, separates them from layout, and allows both components and layout to be changed without breaking dependent formulae. Here, we report experiments to test that this does indeed make such changes easier. In one, we automatically generated a cross-tabulation and added it to a spreadsheet. In the other, we generated new versions of a 10,000-cell housing-finance spreadsheet containing many interconnected 20*40 tables. We varied table sizes from 5*10 to 200*2,000; moved tables between sheets; and flipped table orientations. Each change generated a spreadsheet with different structure but identical outputs; each change took just a few minutes.
Cooperative Spectrum Sensing Using Random Matrix Theory
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, using tools from asymptotic random matrix theory, a new cooperative scheme for frequency band sensing is introduced for both AWGN and fading channels. Unlike previous works in the field, the new scheme does not require the knowledge of the noise statistics or its variance and is related to the behavior of the largest and smallest eigenvalue of random matrices. Remarkably, simulations show that the asymptotic claims hold even for a small number of observations (which makes it convenient for time-varying topologies), outperforming classical energy detection techniques.
Complexity Analysis of Reed-Solomon Decoding over GF(2^m) Without Using Syndromes
Venue: arXiv cs.IT 2008
Year: 2008

For the majority of the applications of Reed-Solomon (RS) codes, hard decision decoding is based on syndromes. Recently, there has been renewed interest in decoding RS codes without using syndromes. In this paper, we investigate the complexity of syndromeless decoding for RS codes, and compare it to that of syndrome-based decoding. Aiming to provide guidelines to practical applications, our complexity analysis differs in several aspects from existing asymptotic complexity analysis, which is typically based on multiplicative fast Fourier transform (FFT) techniques and is usually in big O notation. First, we focus on RS codes over characteristic-2 fields, over which some multiplicative FFT techniques are not applicable. Secondly, due to moderate block lengths of RS codes in practice, our analysis is complete since all terms in the complexities are accounted for. Finally, in addition to fast implementation using additive FFT techniques, we also consider direct implementation, which is still relevant for RS codes with moderate lengths. Comparing the complexities of both syndromeless and syndrome-based decoding algorithms based on direct and fast implementations, we show that syndromeless decoding algorithms have higher complexities than syndrome-based ones for high rate RS codes regardless of the implementation. Both errors-only and errors-and-erasures decoding are considered in this paper. We also derive tighter bounds on the complexities of fast polynomial multiplications based on Cantor's approach and the fast extended Euclidean algorithm.
Toeplitz Block Matrices in Compressed Sensing
Venue: arXiv cs.IT 2008
Year: 2008

Recent work in compressed sensing theory shows that $n\times N$ independent and identically distributed (IID) sensing matrices whose entries are drawn independently from certain probability distributions guarantee exact recovery of a sparse signal with high probability even if $n\ll N$. Motivated by signal processing applications, random filtering with Toeplitz sensing matrices whose elements are drawn from the same distributions were considered and shown to also be sufficient to recover a sparse signal from reduced samples exactly with high probability. This paper considers Toeplitz block matrices as sensing matrices. They naturally arise in multichannel and multidimensional filtering applications and include Toeplitz matrices as special cases. It is shown that the probability of exact reconstruction is also high. Their performance is validated using simulations.
Un Algorithme de Gestion des Adjacences basé sur la Puissance du Signal
Venue: arXiv cs.NI 2008
Year: 2008

In this proposition, we present a link management technique for pro-active routing protocols for ad-hoc networks. This new mechanism is based on signal strength hence cross layer approach is used. The hysteresis mechanism provided by OLSR is improved upon by using signal strength in combination with the hello loss based hysteresis. The signal power is used to determine if the link-quality is improving or deteriorating while packet losses are handled through the hysteresis mechanism specified in OLSR RFC. This not only makes the link management more robust but also helps in anticipating link breakages thereby greatly improving the performance.
Faster Approximate Lossy Generalized Flow via Interior Point Algorithms
Venue: arXiv cs.DS 2008
Year: 2008

We present faster approximation algorithms for generalized network flow problems. A generalized flow is one in which the flow out of an edge differs from the flow into the edge by a constant factor. We limit ourselves to the lossy case, when these factors are at most 1. Our algorithm uses a standard interior-point algorithm to solve a linear program formulation of the network flow problem. The system of linear equations that arises at each step of the interior-point algorithm takes the form of a symmetric M-matrix. We present an algorithm for solving such systems in nearly linear time. The algorithm relies on the Spielman-Teng nearly linear time algorithm for solving linear systems in diagonally-dominant matrices. For a graph with m edges, our algorithm obtains an additive epsilon approximation of the maximum generalized flow and minimum cost generalized flow in time tildeO(m^(3/2) * log(1/epsilon)). In many parameter ranges, this improves over previous algorithms by a factor of approximately m^(1/2). We also obtain a similar improvement for exactly solving the standard min-cost flow problem.
Optimizing Web Sites for Customer Retention
Venue: arXiv cs.HC 2008
Year: 2008

With customer relationship management (CRM) companies move away from a mainly product-centered view to a customer-centered view. Resulting from this change, the effective management of how to keep contact with customers throughout different channels is one of the key success factors in today's business world. Company Web sites have evolved in many industries into an extremely important channel through which customers can be attracted and retained. To analyze and optimize this channel, accurate models of how customers browse through the Web site and what information within the site they repeatedly view are crucial. Typically, data mining techniques are used for this purpose. However, there already exist numerous models developed in marketing research for traditional channels which could also prove valuable to understanding this new channel. In this paper we propose the application of an extension of the Logarithmic Series Distribution (LSD) model repeat-usage of Web-based information and thus to analyze and optimize a Web Site's capability to support one goal of CRM, to retain customers. As an example, we use the university's blended learning web portal with over a thousand learning resources to demonstrate how the model can be used to evaluate and improve the Web site's effectiveness.
The Rate Loss of Single-Letter Characterization: The "Dirty" Multiple Access Channel
Venue: arXiv cs.IT 2008
Year: 2008

For general memoryless systems, the typical information theoretic solution - when exists - has a "single-letter" form. This reflects the fact that optimum performance can be approached by a random code (or a random binning scheme), generated using independent and identically distributed copies of some single-letter distribution. Is that the form of the solution of any (information theoretic) problem? In fact, some counter examples are known. The most famous is the "two help one" problem: Korner and Marton showed that if we want to decode the modulo-two sum of two binary sources from their independent encodings, then linear coding is better than random coding. In this paper we provide another counter example, the "doubly-dirty" multiple access channel (MAC). Like the Korner-Marton problem, this is a multi-terminal scenario where side information is distributed among several terminals; each transmitter knows part of the channel interference but the receiver is not aware of any part of it. We give an explicit solution for the capacity region of a binary version of the doubly-dirty MAC, demonstrate how the capacity region can be approached using a linear coding scheme, and prove that the "best known single-letter region" is strictly contained in it. We also state a conjecture regarding a similar rate loss of single letter characterization in the Gaussian case.
Asymptotic Capacity and Optimal Precoding Strategy of Multi-Level Precode & Forward in Correlated Channels
Venue: arXiv cs.IT 2008
Year: 2008

We analyze a multi-level MIMO relaying system where a multiple-antenna transmitter sends data to a multipleantenna receiver through several relay levels, also equipped with multiple antennas. Assuming correlated fading in each hop, each relay receives a faded version of the signal transmitted by the previous level, performs precoding on the received signal and retransmits it to the next level. Using free probability theory and assuming that the noise power at the relay levels - but not at the receiver - is negligible, a closed-form expression of the end-to-end asymptotic instantaneous mutual information is derived as the number of antennas in all levels grow large with the same rate. This asymptotic expression is shown to be independent from the channel realizations, to only depend on the channel statistics and to also serve as the asymptotic value of the end-to-end average mutual information. We also provide the optimal singular vectors of the precoding matrices that maximize the asymptotic mutual information : the optimal transmit directions represented by the singular vectors of the precoding matrices are aligned on the eigenvectors of the channel correlation matrices, therefore they can be determined only using the known statistics of the channel matrices and do not depend on a particular channel realization.
Non-Singular Assembly-mode Changing Motions for 3-RPR Parallel Manipulators
Venue: arXiv cs.RO 2008
Year: 2008

When moving from one arbitrary location at another, a parallel manipulator may change its assembly-mode without crossing a singularity. Because the non-singular change of assembly-mode cannot be simply detected, the actual assembly-mode during motion is difficult to track. This paper proposes a global explanatory approach to help better understand non-singular assembly-mode changing motions for 3-RPR planar parallel manipulators. The approach consists in fixing one of the actuated joints and analyzing the configuration-space as a surface in a 3-dimensional space. Such a global description makes it possible to display all possible non-singular assembly-mode changing trajectories.
A Game Theoretic Framework for Decentralized Power Allocation in IDMA Systems
Venue: arXiv cs.IT 2008
Year: 2008

In this contribution we present a decentralized power allocation algorithm for the uplink interleave division multiple access (IDMA) channel. Within the proposed optimal strategy for power allocation, each user aims at selfishly maximizing its own utility function. An iterative chip by chip (CBC) decoder at the receiver and a rational selfish behavior of all the users according to a classical game-theoretical framework are the underlying assumptions of this work. This approach leads to a power allocation based on a channel inversion policy where the optimal power level is set locally at each terminal based on the knowledge of its own channel realization, the noise level at the receiver and the number of active users in the network.
Hybrid Reasoning and the Future of Iconic Representations
Venue: arXiv cs.AI 2008
Year: 2008

We give a brief overview of the main characteristics of diagrammatic reasoning, analyze a case of human reasoning in a mastermind game, and explain why hybrid representation systems (HRS) are particularly attractive and promising for Artificial General Intelligence and Computer Science in general.
Dempster-Shafer for Anomaly Detection
Venue: arXiv cs.NE 2008
Year: 2008

In this paper, we implement an anomaly detection system using the Dempster-Shafer method. Using two standard benchmark problems we show that by combining multiple signals it is possible to achieve better results than by using a single signal. We further show that by applying this approach to a real-world email dataset the algorithm works for email worm detection. Dempster-Shafer can be a promising method for anomaly detection problems with multiple features (data sources), and two or more classes.
Using Intelligent Agents to understand organisational behaviour
Venue: arXiv cs.NE 2008
Year: 2008

This paper introduces two ongoing research projects which seek to apply computer modelling techniques in order to simulate human behaviour within organisations. Previous research in other disciplines has suggested that complex social behaviours are governed by relatively simple rules which, when identified, can be used to accurately model such processes using computer technology. The broad objective of our research is to develop a similar capability within organisational psychology.
TellTable Spreadsheet Audit: from Technical Possibility to Operating Prototype
Venue: arXiv cs.SE 2008
Year: 2008

At the 2003 EuSpRIG meeting, we presented a framework and software infrastructure to generate and analyse an audit trail for a spreadsheet file. This report describes the results of a pilot implementation of this software (now called TellTable; see www.telltable.com), along with developments in the server infrastructure and availability, extensions to other "Office Suite" files, integration of the audit tool into the server interface, and related developments, licensing and reports. We continue to seek collaborators and partners in what is primarily an open-source project with some shared-source components.
Achievable Rates and Optimal Resource Allocation for Imperfectly-Known Fading Relay Channels
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, achievable rates and optimal resource allocation strategies for imperfectly-known fading relay channels are studied. It is assumed that communication starts with the network training phase in which the receivers estimate the fading coefficients of their respective channels. In the data transmission phase, amplify-and-forward and decode-and-forward relaying schemes with different degrees of cooperation are considered, and the corresponding achievable rate expressions are obtained. Three resource allocation problems are addressed: 1) power allocation between data and training symbols; 2) time/bandwidth allocation to the relay; 3) power allocation between the source and relay in the presence of total power constraints. The achievable rate expressions are employed to identify the optimal resource allocation strategies. Finally, energy efficiency is investigated by studying the bit energy requirements in the low-SNR regime.
Improved Squeaky Wheel Optimisation for Driver Scheduling
Venue: arXiv cs.NE 2008
Year: 2008

This paper presents a technique called Improved Squeaky Wheel Optimisation for driver scheduling problems. It improves the original Squeaky Wheel Optimisations effectiveness and execution speed by incorporating two additional steps of Selection and Mutation which implement evolution within a single solution. In the ISWO, a cycle of Analysis-Selection-Mutation-Prioritization-Construction continues until stopping conditions are reached. The Analysis step first computes the fitness of a current solution to identify troublesome components. The Selection step then discards these troublesome components probabilistically by using the fitness measure, and the Mutation step follows to further discard a small number of components at random. After the above steps, an input solution becomes partial and thus the resulting partial solution needs to be repaired. The repair is carried out by using the Prioritization step to first produce priorities that determine an order by which the following Construction step then schedules the remaining components. Therefore, the optimisation in the ISWO is achieved by solution disruption, iterative improvement and an iterative constructive repair process performed. Encouraging experimental results are reported.
Problem Solving and Complex Systems
Venue: arXiv cs.NE 2008
Year: 2008

The observation and modeling of natural Complex Systems (CSs) like the human nervous system, the evolution or the weather, allows the definition of special abilities and models reusable to solve other problems. For instance, Genetic Algorithms or Ant Colony Optimizations are inspired from natural CSs to solve optimization problems. This paper proposes the use of ant-based systems to solve various problems with a non assessing approach. This means that solutions to some problem are not evaluated. They appear as resultant structures from the activity of the system. Problems are modeled with graphs and such structures are observed directly on these graphs. Problems of Multiple Sequences Alignment and Natural Language Processing are addressed with this approach.
Science mapping with asymmetrical paradigmatic proximity
Venue: arXiv cs.OH 2008
Year: 2008

We propose a series of methods to represent the evolution of a field of science at different levels: namely micro, meso and macro levels. We use a previously introduced asymmetric measure of paradigmatic proximity between terms that enables us to extract structure from a large publications database. We apply our set of methods on a case study from the complex systems community through the mapping of more than 400 complex systems science concepts indexed from a database as large as several millions of journal papers. We will first summarize the main properties of our asymmetric proximity measure. Then we show how salient paradigmatic fields can be embedded into a 2-dimensional visualization into which the terms are plotted according to their relative specificity and generality index. This meso-level helps us producing macroscopic maps of the field of science studied featuring the former paradigmatic fields.