OpenRaiser/Intern-Atlas huggingface dataset:
The Asymptotic Bit Error Probability of LDPC Codes for the Binary Erasure Channel with Finite Iteration Number
Venue: arXiv cs.IT 2008
Year: 2008

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. The bit error probability for infinite block length is known by density evolution and it is well known that a difference between the bit error probability at finite iteration number for finite block length $n$ and for infinite block length is asymptotically $α/n$, where $α$ is a specific constant depending on the degree distribution, the iteration number and the erasure probability. Our main result is to derive an efficient algorithm for calculating $α$ for regular ensembles. The approximation using $α$ is accurate for $(2,r)$-regular ensembles even in small block length.
On the Refinement of Liveness Properties of Distributed Systems
Venue: arXiv cs.LO 2008
Year: 2008

We present a new approach for reasoning about liveness properties of distributed systems, represented as automata. Our approach is based on simulation relations, and requires reasoning only over finite execution fragments. Current simulation-relation based methods for reasoning about liveness properties of automata require reasoning over entire executions, since they involve a proof obligation of the form: if a concrete and abstract execution ``correspond'' via the simulation, and the concrete execution is live, then so is the abstract execution. Our contribution consists of (1) a formalism for defining liveness properties, (2) a proof method for liveness properties based on that formalism, and (3) two expressive completeness results: firstly, our formalism can express any liveness property which satisfies a natural ``robustness'' condition, and secondly, our formalism can express any liveness property at all, provided that history variables can be used
Le terme et le concept : fondements d'une ontoterminologie
Venue: arXiv cs.AI 2008
Year: 2008

Most definitions of ontology, viewed as a "specification of a conceptualization", agree on the fact that if an ontology can take different forms, it necessarily includes a vocabulary of terms and some specification of their meaning in relation to the domain's conceptualization. And as domain knowledge is mainly conveyed through scientific and technical texts, we can hope to extract some useful information from them for building ontology. But is it as simple as this? In this article we shall see that the lexical structure, i.e. the network of words linked by linguistic relationships, does not necessarily match the domain conceptualization. We have to bear in mind that writing documents is the concern of textual linguistics, of which one of the principles is the incompleteness of text, whereas building ontology - viewed as task-independent knowledge - is concerned with conceptualization based on formal and not natural languages. Nevertheless, the famous Sapir and Whorf hypothesis, concerning the interdependence of thought and language, is also applicable to formal languages. This means that the way an ontology is built and a concept is defined depends directly on the formal language which is used; and the results will not be the same. The introduction of the notion of ontoterminology allows to take into account epistemological principles for formal ontology building.
Teaching spreadsheet development using peer audit and self-audit methods for reducing error
Venue: arXiv cs.CY 2008
Year: 2008

Recent research has highlighted the high incidence of errors in spreadsheet models used in industry. In an attempt to reduce the incidence of such errors, a teaching approach has been devised which aids students to reduce their likelihood of making common errors during development. The approach comprises of spreadsheet checking methods based on the commonly accepted educational paradigms of peer assessment and self-assessment. However, these paradigms are here based upon practical techniques commonly used by the internal audit function such as peer audit and control and risk self-assessment. The result of this symbiosis between educational assessment and professional audit is a method that educates students in a set of structured, transferable skills for spreadsheet error-checking which are useful for increasing error-awareness in the classroom and for reducing business risk in the workplace.
Computational Solutions for Today's Navy
Venue: arXiv cs.MA 2008
Year: 2008

New methods are being employed to meet the Navy's changing software-development environment.
On Breaching Enterprise Data Privacy Through Adversarial Information Fusion
Venue: arXiv cs.DB 2008
Year: 2008

Data privacy is one of the key challenges faced by enterprises today. Anonymization techniques address this problem by sanitizing sensitive data such that individual privacy is preserved while allowing enterprises to maintain and share sensitive data. However, existing work on this problem make inherent assumptions about the data that are impractical in day-to-day enterprise data management scenarios. Further, application of existing anonymization schemes on enterprise data could lead to adversarial attacks in which an intruder could use information fusion techniques to inflict a privacy breach. In this paper, we shed light on the shortcomings of current anonymization schemes in the context of enterprise data. We define and experimentally demonstrate Web-based Information- Fusion Attack on anonymized enterprise data. We formulate the problem of Fusion Resilient Enterprise Data Anonymization and propose a prototype solution to address this problem.
Achieving the Quadratic Gaussian Rate-Distortion Function for Source Uncorrelated Distortions
Venue: arXiv cs.IT 2008
Year: 2008

We prove achievability of the recently characterized quadratic Gaussian rate-distortion function (RDF) subject to the constraint that the distortion is uncorrelated to the source. This result is based on shaped dithered lattice quantization in the limit as the lattice dimension tends to infinity and holds for all positive distortions. It turns out that this uncorrelated distortion RDF can be realized causally. This feature, which stands in contrast to Shannon's RDF, is illustrated by causal transform coding. Moreover, we prove that by using feedback noise shaping the uncorrelated distortion RDF can be achieved causally and with memoryless entropy coding. Whilst achievability relies upon infinite dimensional quantizers, we prove that the rate loss incurred in the finite dimensional case can be upper-bounded by the space filling loss of the quantizer and, thus, is at most 0.254 bit/dimension.
An omega-power of a context-free language which is Borel above Delta^0_omega
Venue: arXiv cs.CC 2008
Year: 2008

We use erasers-like basic operations on words to construct a set that is both Borel and above Delta^0_omega, built as a set V^ωwhere V is a language of finite words accepted by a pushdown automaton. In particular, this gives a first example of an omega-power of a context free language which is a Borel set of infinite rank.
Interpretation as a factor in understanding flawed spreadsheets
Venue: arXiv cs.CY 2008
Year: 2008

The spreadsheet has been used by the business community for many years and yet still raises a number of significant concerns. As educators our concern is to try to develop the students skills in both the development of spreadsheets and in taking a critical view of their potential defects. In this paper we consider both the problems of mechanical production and the problems of translation of problem to spreadsheet representation.
On the Boundedness of the Support of Optimal Input Measures for Rayleigh Fading Channels
Venue: arXiv cs.IT 2008
Year: 2008

We consider transmission over a wireless multiple antenna communication system operating in a Rayleigh flat fading environment with no channel state information at the receiver and the transmitter with coherence time T=1. We show that, subject to the average power constraint, the support of the capacity achieving input distribution is bounded. Moreover, we show by a simple example concerning the identity theorem (or uniqueness theorem) from the complex analysis in several variables that some of the existing results in the field are not rigorous.
A Comparison of natural (english) and artificial (esperanto) languages. A Multifractal method based analysis
Venue: arXiv cs.CL 2008
Year: 2008

We present a comparison of two english texts, written by Lewis Carroll, one (Alice in wonderland) and the other (Through a looking glass), the former translated into esperanto, in order to observe whether natural and artificial languages significantly differ from each other. We construct one dimensional time series like signals using either word lengths or word frequencies. We use the multifractal ideas for sorting out correlations in the writings. In order to check the robustness of the methods we also write the corresponding shuffled texts. We compare characteristic functions and e.g. observe marked differences in the (far from parabolic) f(alpha) curves, differences which we attribute to Tsallis non extensive statistical features in the ''frequency time series'' and ''length time series''. The esperanto text has more extreme vallues. A very rough approximation consists in modeling the texts as a random Cantor set if resulting from a binomial cascade of long and short words (or words and blanks). This leads to parameters characterizing the text style, and most likely in fine the author writings.
Coding and Decoding for the Dynamic Decode and Forward Relay Protocol
Venue: arXiv cs.IT 2008
Year: 2008

We study the Dynamic Decode and Forward (DDF) protocol for a single half-duplex relay, single-antenna channel with quasi-static fading. The DDF protocol is well-known and has been analyzed in terms of the Diversity-Multiplexing Tradeoff (DMT) in the infinite block length limit. We characterize the finite block length DMT and give new explicit code constructions. The finite block length analysis illuminates a few key aspects that have been neglected in the previous literature: 1) we show that one dominating cause of degradation with respect to the infinite block length regime is the event of decoding error at the relay; 2) we explicitly take into account the fact that the destination does not generally know a priori the relay decision time at which the relay switches from listening to transmit mode. Both the above problems can be tackled by a careful design of the decoding algorithm. In particular, we introduce a decision rejection criterion at the relay based on Forney's decision rule (a variant of the Neyman-Pearson rule), such that the relay triggers transmission only when its decision is reliable. Also, we show that a receiver based on the Generalized Likelihood Ratio Test rule that jointly decodes the relay decision time and the information message achieves the optimal DMT. Our results show that no cyclic redundancy check (CRC) for error detection or additional protocol overhead to communicate the decision time are needed for DDF. Finally, we investigate the use of minimum mean squared error generalized decision feedback equalizer (MMSE-GDFE) lattice decoding at both the relay and the destination, and show that it provides near optimal performance at moderate complexity.
Survey of Technologies for Web Application Development
Venue: arXiv cs.SE 2008
Year: 2008

Web-based application developers face a dizzying array of platforms, languages, frameworks and technical artifacts to choose from. We survey, classify, and compare technologies supporting Web application development. The classification is based on (1) foundational technologies; (2)integration with other information sources; and (3) dynamic content generation. We further survey and classify software engineering techniques and tools that have been adopted from traditional programming into Web programming. We conclude that, although the infrastructure problems of the Web have largely been solved, the cacophony of technologies for Web-based applications reflects the lack of a solid model tailored for this domain.
Categorisation of Spreadsheet Use within Organisations, Incorporating Risk: A Progress Report
Venue: arXiv cs.CY 2008
Year: 2008

There has been a significant amount of research into spreadsheets over the last two decades. Errors in spreadsheets are well documented. Once used mainly for simple functions such as logging, tracking and totalling information, spreadsheets with enhanced formulas are being used for complex calculative models. There are many software packages and tools which assist in detecting errors within spreadsheets. There has been very little evidence of investigation into the spreadsheet risks associated with the main stream operations within an organisation. This study is a part of the investigation into the means of mitigating risks associated with spreadsheet use within organisations. In this paper the authors present and analyse three proposed models for categorisation of spreadsheet use and the level of risks involved. The models are analysed in the light of current knowledge and the general risks associated with organisations.
The Danger Theory and Its Application to Artificial Immune Systems
Venue: arXiv cs.NE 2008
Year: 2008

Over the last decade, a new idea challenging the classical self-non-self viewpoint has become popular amongst immunologists. It is called the Danger Theory. In this conceptual paper, we look at this theory from the perspective of Artificial Immune System practitioners. An overview of the Danger Theory is presented with particular emphasis on analogies in the Artificial Immune Systems world. A number of potential application areas are then used to provide a framing for a critical assessment of the concept, and its relevance for Artificial Immune Systems.
Ensuring Spreadsheet Integrity with Model Master
Venue: arXiv cs.PL 2008
Year: 2008

We have developed the Model Master (MM) language for describing spreadsheets, and tools for converting MM programs to and from spreadsheets. The MM decompiler translates a spreadsheet into an MM program which gives a concise summary of its calculations, layout, and styling. This is valuable when trying to understand spreadsheets one has not seen before, and when checking for errors. The MM compiler goes the other way, translating an MM program into a spreadsheet. This makes possible a new style of development, in which spreadsheets are generated from textual specifications. This can reduce error rates compared to working directly with the raw spreadsheet, and gives important facilities for code reuse. MM programs also offer advantages over Excel files for the interchange of spreadsheets.
3D-Ultrasound probe calibration for computer-guided diagnosis and therapy
Venue: arXiv cs.OH 2008
Year: 2008

With the emergence of swept-volume ultrasound (US) probes, precise and almost real-time US volume imaging has become available. This offers many new opportunities for computer guided diagnosis and therapy, 3-D images containing significantly more information than 2-D slices. However, computer guidance often requires knowledge about the exact position of US voxels relative to a tracking reference, which can only be achieved through probe calibration. In this paper we present a 3-D US probe calibration system based on a membrane phantom. The calibration matrix is retrieved by detection of a membrane plane in a dozen of US acquisitions of the phantom. Plane detection is robustly performed with the 2-D Hough transformation. The feature extraction process is fully automated, calibration requires about 20 minutes and the calibration system can be used in a clinical context. The precision of the system was evaluated to a root mean square (RMS) distance error of 1.15mm and to an RMS angular error of 0.61 degrees. The point reconstruction accuracy was evaluated to 0.9mm and the angular reconstruction accuracy to 1.79 degrees.
Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra
Venue: arXiv cs.CC 2008
Year: 2008

Given a graph $G=(V,E)$ and a weight function on the edges $w:E\mapsto\RR$, we consider the polyhedron $P(G,w)$ of negative-weight flows on $G$, and get a complete characterization of the vertices and extreme directions of $P(G,w)$. As a corollary, we show that, unless $P=NP$, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (2006) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes \cite{BL98} [Bussieck and Lübbecke (1998)].
Between conjecture and memento: shaping a collective emotional perception of the future
Venue: arXiv cs.CL 2008
Year: 2008

Large scale surveys of public mood are costly and often impractical to perform. However, the web is awash with material indicative of public mood such as blogs, emails, and web queries. Inexpensive content analysis on such extensive corpora can be used to assess public mood fluctuations. The work presented here is concerned with the analysis of the public mood towards the future. Using an extension of the Profile of Mood States questionnaire, we have extracted mood indicators from 10,741 emails submitted in 2006 to futureme.org, a web service that allows its users to send themselves emails to be delivered at a later date. Our results indicate long-term optimism toward the future, but medium-term apprehension and confusion.
Spectral efficiency and optimal medium access control of random access systems over large random spreading CDMA
Venue: arXiv cs.IT 2008
Year: 2008

This paper analyzes the spectral efficiency as a function of medium access control (MAC) for large random spreading CDMA random access systems that employ a linear receiver. It is shown that located at higher than the physical layer, MAC along with spreading and power allocation can effectively perform spectral efficiency maximization and near-far mitigation.
On the Continuity Set of an omega Rational Function
Venue: arXiv cs.CC 2008
Year: 2008

In this paper, we study the continuity of rational functions realized by Büchi finite state transducers. It has been shown by Prieur that it can be decided whether such a function is continuous. We prove here that surprisingly, it cannot be decided whether such a function F has at least one point of continuity and that its continuity set C(F) cannot be computed. In the case of a synchronous rational function, we show that its continuity set is rational and that it can be computed. Furthermore we prove that any rational Pi^0_2-subset of X^omega for some alphabet X is the continuity set C(F) of an omega-rational synchronous function F defined on X^omega.
Set-based complexity and biological information
Venue: arXiv cs.IT 2008
Year: 2008

It is not obvious what fraction of all the potential information residing in the molecules and structures of living systems is significant or meaningful to the system. Sets of random sequences or identically repeated sequences, for example, would be expected to contribute little or no useful information to a cell. This issue of quantitation of information is important since the ebb and flow of biologically significant information is essential to our quantitative understanding of biological function and evolution. Motivated specifically by these problems of biological information, we propose here a class of measures to quantify the contextual nature of the information in sets of objects, based on Kolmogorov's intrinsic complexity. Such measures discount both random and redundant information and are inherent in that they do not require a defined state space to quantify the information. The maximization of this new measure, which can be formulated in terms of the universal information distance, appears to have several useful and interesting properties, some of which we illustrate with examples.
Bounded Mean-Delay Throughput and Non-Starvation Conditions in Aloha Network
Venue: arXiv cs.NI 2008
Year: 2008

This paper considers the requirements to ensure bounded mean queuing delay and non-starvation in a slotted Aloha network operating the exponential backoff protocol. It is well-known that the maximum possible throughput of a slotted Aloha system with a large number of nodes is 1/e = 0.3679. Indeed, a saturation throughput of 1/e can be achieved with an exponential backoff factor of r = e/(e-1)=1.5820. The binary backoff factor of r = 2 is assumed in the majority of prior work, and in many practical multiple-access networks such as the Ethernet and WiFi. For slotted Aloha, the saturation throughput 0.3466 for r = 2 is reasonably close to the maximum of 1/e, and one could hardly raise objection to adopting r = 2 in the system. However, this paper shows that if mean queuing delay is to be bounded, then the sustainable throughput when r = 2 is only 0.2158, a drastic 41% drop from 1/e . Fortunately, the optimal setting of r = 1.3757 under the bounded mean-delay requirement allows us to achieve sustainable throughput of 0.3545, a penalty of only less than 4% relative to 1/e. A general conclusion is that the value of r may significantly affect the queuing delay performance. Besides analyzing mean queuing delay, this paper also delves into the phenomenon of starvation, wherein some nodes are deprived of service for an extended period of time while other nodes hog the system. Specifically, we propose a quantitative definition for starvation and show that the conditions to guarantee bounded mean delay and non-starved operation are one of the same, thus uniting these two notions. Finally, we show that when mean delay is large and starvation occurs, the performance results obtained from simulation experiments may not converge. A quantitative discussion of this issue is provided in this paper.
The optimal assignment kernel is not positive definite
Venue: arXiv cs.LG 2008
Year: 2008

We prove that the optimal assignment kernel, proposed recently as an attempt to embed labeled graphs and more generally tuples of basic data to a Hilbert space, is in fact not always positive definite.
Microscopic Analysis for Decoupling Principle of Linear Vector Channel
Venue: arXiv cs.IT 2008
Year: 2008

This paper studies the decoupling principle of a linear vector channel, which is an extension of CDMA and MIMO channels. We show that the scalar-channel characterization obtained via the decoupling principle is valid not only for collections of a large number of elements of input vector, as discussed in previous studies, but also for individual elements of input vector, i.e. the linear vector channel for individual elements of channel input vector is decomposed into a bank of independent scalar Gaussian channels in the large-system limit, where dimensions of channel input and output are both sent to infinity while their ratio fixed.
Spreadsheet Debugging
Venue: arXiv cs.SE 2008
Year: 2008

Spreadsheet programs, artifacts developed by non-programmers, are used for a variety of important tasks and decisions. Yet a significant proportion of them have severe quality problems. To address this issue, our previous work presented an interval-based testing methodology for spreadsheets. Interval-based testing rests on the observation that spreadsheets are mainly used for numerical computations. It also incorporates ideas from symbolic testing and interval analysis. This paper addresses the issue of efficiently debugging spreadsheets. Based on the interval-based testing methodology, this paper presents a technique for tracing faults in spreadsheet programs. The fault tracing technique proposed uses the dataflow information and cell marks to identify the most influential faulty cell(s) for a given formula cell containing a propagated fault.