OpenRaiser/Intern-Atlas huggingface dataset:
Building and displaying name relations using automatic unsupervised analysis of newspaper articles
Venue: arXiv cs.CL 2006
Year: 2006

We present a tool that, from automatically recognised names, tries to infer inter-person relations in order to present associated people on maps. Based on an in-house Named Entity Recognition tool, applied on clusters of an average of 15,000 news articles per day, in 15 different languages, we build a knowledge base that allows extracting statistical co-occurrences of persons and visualising them on a per-person page or in various graphs.
Non-photorealistic image rendering with a labyrinthine tiling
Venue: arXiv cs.GR 2006
Year: 2006

The paper describes a new image processing for a non-photorealistic rendering. The algorithm is based on a random generation of gray tones and competing statistical requirements. The gray tone value of each pixel in the starting image is replaced selecting among randomly generated tone values, according to the statistics of nearest-neighbor and next-nearest-neighbor pixels. Two competing conditions for replacing the tone values - one position on the local mean value the other on the local variance - produce a peculiar pattern on the image. This pattern has a labyrinthine tiling aspect. For certain subjects, the pattern enhances the look of the image.
A comparative analysis of the geometrical surface texture of a real and virtual model of a tooth flank of a cylindrical gear
Venue: arXiv cs.CE 2006
Year: 2006

The paper presents the methodology of modelling tooth flanks of cylindrical gears in the Cad environment. The modelling consists in a computer simulation of gear generation. A model of tooth flanks is an envelope curve of a family of envelopes that originate from the rolling motion of a solid tool model in relation to a solid model of the cylindrical gear. The surface stereometry and topography of the tooth flanks, hobbed and chiselled by Fellows method, are compared to their numerical models. Metrological measurements of the real gears were carried out using a coordinated measuring machine and a two - and a three-dimensional profilometer. A computer simulation of the gear generation was performed in the Mechanical Desktop environment.
An Improved Sphere-Packing Bound Targeting Codes of Short to Moderate Block Lengths and Applications
Venue: arXiv cs.IT 2006
Year: 2006

This paper derives an improved sphere-packing (ISP) bound targeting codes of short to moderate block lengths. We first review the 1967 sphere-packing (SP67) bound for discrete memoryless channels, and a recent improvement by Valembois and Fossorier. These concepts are used for the derivation of a new lower bound on the decoding error probability (referred to as the ISP bound) which is uniformly tighter than the SP67 bound and its recent improved version. Under a mild condition, the ISP bound is applicable to general memoryless channels, and some of its applications are exemplified. Its tightness is studied by comparing it with bounds on the ML decoding error probability. It is exemplified that the ISP bound suggests an interesting alternative to the 1959 sphere-packing (SP59) bound of Shannon for the Gaussian channel, especially for digital modulations of high spectral efficiency.
Binomial multichannel algorithm
Venue: arXiv cs.CR 2006
Year: 2006

The binomial multichannel algorithm is proposed. Some its properties are discussed.
An application-oriented terminology evaluation: the case of back-of-the book indexes
Venue: arXiv cs.AI 2006
Year: 2006

This paper addresses the problem of computational terminology evaluation not per se but in a specific application context. This paper describes the evaluation procedure that has been used to assess the validity of our overall indexing approach and the quality of the IndDoc indexing tool. Even if user-oriented extended evaluation is irreplaceable, we argue that early evaluations are possible and they are useful for development guidance.
Modular self-organization
Venue: arXiv cs.AI 2006
Year: 2006

The aim of this paper is to provide a sound framework for addressing a difficult problem: the automatic construction of an autonomous agent's modular architecture. We combine results from two apparently uncorrelated domains: Autonomous planning through Markov Decision Processes and a General Data Clustering Approach using a kernel-like method. Our fundamental idea is that the former is a good framework for addressing autonomy whereas the latter allows to tackle self-organizing problems.
Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes
Venue: arXiv cs.IT 2006
Year: 2006

We illustrate the utility of the recently developed loop calculus for improving the Belief Propagation (BP) algorithm. If the algorithm that minimizes the Bethe free energy fails we modify the free energy by accounting for a critical loop in a graphical representation of the code. The log-likelihood specific critical loop is found by means of the loop calculus. The general method is tested using an example of the Linear Programming (LP) decoding, that can be viewed as a special limit of the BP decoding. Considering the (155,64,20) code that performs over Additive-White-Gaussian-Noise channel we show that the loop calculus improves the LP decoding and corrects all previously found dangerous configurations of log-likelihoods related to pseudo-codewords with low effective distance, thus reducing the code's error-floor.
Labeling Schemes with Queries
Venue: arXiv cs.DC 2006
Year: 2006

We study the question of ``how robust are the known lower bounds of labeling schemes when one increases the number of consulted labels''. Let $f$ be a function on pairs of vertices. An $f$-labeling scheme for a family of graphs $\cF$ labels the vertices of all graphs in $\cF$ such that for every graph $G\in\cF$ and every two vertices $u,v\in G$, the value $f(u,v)$ can be inferred by merely inspecting the labels of $u$ and $v$. This paper introduces a natural generalization: the notion of $f$-labeling schemes with queries, in which the value $f(u,v)$ can be inferred by inspecting not only the labels of $u$ and $v$ but possibly the labels of some additional vertices. We show that inspecting the label of a single additional vertex (one {\em query}) enables us to reduce the label size of many labeling schemes significantly.
Private Approximate Heavy Hitters
Venue: arXiv cs.CR 2006
Year: 2006

We consider the problem of private computation of approximate Heavy Hitters. Alice and Bob each hold a vector and, in the vector sum, they want to find the B largest values along with their indices. While the exact problem requires linear communication, protocols in the literature solve this problem approximately using polynomial computation time, polylogarithmic communication, and constantly many rounds. We show how to solve the problem privately with comparable cost, in the sense that nothing is learned by Alice and Bob beyond what is implied by their input, the ideal top-B output, and goodness of approximation (equivalently, the Euclidean norm of the vector sum). We give lower bounds showing that the Euclidean norm must leak by any efficient algorithm.
Updates in Answer Set Programming: An Approach Based on Basic Structural Properties
Venue: arXiv cs.LO 2006
Year: 2006

We have studied the update operator defined for update sequences by Eiter et al. without tautologies and we have observed that it satisfies an interesting property This property, which we call Weak Independence of Syntax (WIS), is similar to one of the postulates proposed by Alchourron, Gardenfors, and Makinson (AGM); only that in this case it applies to nonmonotonic logic. In addition, we consider other five additional basic properties about update programs and we show that the operator of Eiter et al. satisfies them. This work continues the analysis of the AGM postulates under a refined view that considers nelson logic as a monotonic logic which allows us to expand our understanding of answer sets. Moreover, nelson logic helped us to derive an alternative definition of the operator defined by Eiter et al. avoiding the use of unnecessary extra atoms.
Raisonnement stratifié à base de normes pour inférer les causes dans un corpus textuel
Venue: arXiv cs.AI 2006
Year: 2006

To understand texts written in natural language (LN), we use our knowledge about the norms of the domain. Norms allow to infer more implicit information from the text. This kind of information can, in general, be defeasible, but it remains useful and acceptable while the text do not contradict it explicitly. In this paper we describe a non-monotonic reasoning system based on the norms of the car crash domain. The system infers the cause of an accident from its textual description. The cause of an accident is seen as the most specific norm which has been violated. The predicates and the rules of the system are stratified: organized on layers in order to obtain an efficient reasoning.
Memory and compiler optimizations for low-power and -energy
Venue: arXiv cs.PL 2006
Year: 2006

Embedded systems become more and more widespread, especially autonomous ones, and clearly tend to be ubiquitous. In such systems, low-power and low-energy usage get ever more crucial. Furthermore, these issues also become paramount in (massively) multi-processors systems, either in one machine or more widely in a grid. The various problems faced pertain to autonomy, power supply possibilities, thermal dissipation, or even sheer energy cost. Although it has since long been studied in harware, energy optimization is more recent in software. In this paper, we thus aim at raising awareness to low-power and low-energy issues in the language and compilation community. We thus broadly but briefly survey techniques and solutions to this energy issue, focusing on a few specific aspects in the context of compiler optimizations and memory management.
A kernel for time series based on global alignments
Venue: arXiv cs.CV 2006
Year: 2006

We propose in this paper a new family of kernels to handle times series, notably speech data, within the framework of kernel methods which includes popular algorithms such as the Support Vector Machine. These kernels elaborate on the well known Dynamic Time Warping (DTW) family of distances by considering the same set of elementary operations, namely substitutions and repetitions of tokens, to map a sequence onto another. Associating to each of these operations a given score, DTW algorithms use dynamic programming techniques to compute an optimal sequence of operations with high overall score. In this paper we consider instead the score spanned by all possible alignments, take a smoothed version of their maximum and derive a kernel out of this formulation. We prove that this kernel is positive definite under favorable conditions and show how it can be tuned effectively for practical applications as we report encouraging results on a speech recognition task.
Crosstalk-free Conjugate Networks for Optical Multicast Switching
Venue: arXiv cs.NI 2006
Year: 2006

High-speed photonic switching networks can switch optical signals at the rate of several terabits per second. However, they suffer from an intrinsic crosstalk problem when two optical signals cross at the same switch element. To avoid crosstalk, active connections must be node-disjoint in the switching network. In this paper, we propose a sequence of decomposition and merge operations, called conjugate transformation, performed on each switch element to tackle this problem. The network resulting from this transformation is called conjugate network. By using the numbering-schemes of networks, we prove that if the route assignments in the original network are link-disjoint, their corresponding ones in the conjugate network would be node-disjoint. Thus, traditional nonblocking switching networks can be transformed into crosstalk-free optical switches in a routine manner. Furthermore, we show that crosstalk-free multicast switches can also be obtained from existing nonblocking multicast switches via the same conjugate transformation.
A Computational Model of Spatial Memory Anticipation during Visual Search
Venue: arXiv cs.NE 2006
Year: 2006

Some visual search tasks require to memorize the location of stimuli that have been previously scanned. Considerations about the eye movements raise the question of how we are able to maintain a coherent memory, despite the frequent drastically changes in the perception. In this article, we present a computational model that is able to anticipate the consequences of the eye movements on the visual perception in order to update a spatial memory
Towards a Bayesian framework for option pricing
Venue: arXiv cs.CE 2006
Year: 2006

In this paper, we describe a general method for constructing the posterior distribution of an option price. Our framework takes as inputs the prior distributions of the parameters of the stochastic process followed by the underlying, as well as the likelihood function implied by the observed price history for the underlying. Our work extends that of Karolyi (1993) and Darsinos and Satchell (2001), but with the crucial difference that the likelihood function we use for inference is that which is directly implied by the underlying, rather than imposed in an ad hoc manner via the introduction of a function representing "measurement error." As such, an important problem still relevant for our method is that of model risk, and we address this issue by describing how to perform a Bayesian averaging of parameter inferences based on the different models considered using our framework.
Extending the Calculus of Constructions with Tarski's fix-point theorem
Venue: arXiv cs.LO 2006
Year: 2006

We propose to use Tarski's least fixpoint theorem as a basis to define recursive functions in the calculus of inductive constructions. This widens the class of functions that can be modeled in type-theory based theorem proving tool to potentially non-terminating functions. This is only possible if we extend the logical framework by adding the axioms that correspond to classical logic. We claim that the extended framework makes it possible to reason about terminating and non-terminating computations and we show that common facilities of the calculus of inductive construction, like program extraction can be extended to also handle the new functions.
Properties of codes in rank metric
Venue: arXiv cs.DM 2006
Year: 2006

We study properties of rank metric and codes in rank metric over finite fields. We show that in rank metric perfect codes do not exist. We derive an existence bound that is the equivalent of the Gilbert--Varshamov bound in Hamming metric. We study the asymptotic behavior of the minimum rank distance of codes satisfying GV. We derive the probability distribution of minimum rank distance for random and random $\F{q}$-linear codes. We give an asymptotic equivalent of their average minimum rank distance and show that random $\F{q}$-linear codes are on GV bound for rank metric. We show that the covering density of optimum codes whose codewords can be seen as square matrices is lower bounded by a function depending only on the error-correcting capability of the codes. We show that there are quasi-perfect codes in rank metric over fields of characteristic 2.
Language, logic and ontology: uncovering the structure of commonsense knowledge
Venue: arXiv cs.AI 2006
Year: 2006

The purpose of this paper is twofold: (i) we argue that the structure of commonsense knowledge must be discovered, rather than invented; and (ii) we argue that natural language, which is the best known theory of our (shared) commonsense knowledge, should itself be used as a guide to discovering the structure of commonsense knowledge. In addition to suggesting a systematic method to the discovery of the structure of commonsense knowledge, the method we propose seems to also provide an explanation for a number of phenomena in natural language, such as metaphor, intensionality, and the semantics of nominal compounds. Admittedly, our ultimate goal is quite ambitious, and it is no less than the systematic 'discovery' of a well-typed ontology of commonsense knowledge, and the subsequent formulation of the long-awaited goal of a meaning algebra.
Inductive types in the Calculus of Algebraic Constructions
Venue: arXiv cs.LO 2006
Year: 2006

In a previous work, we proved that almost all of the Calculus of Inductive Constructions (CIC), which is the basis of the proof assistant Coq, can be seen as a Calculus of Algebraic Constructions (CAC), an extension of the Calculus of Constructions with functions and predicates defined by higher-order rewrite rules. In this paper, we not only prove that CIC as a whole can be seen as a CAC, but also that it can be extended with non-free constructors, pattern-matching on defined symbols, non-strictly positive types and inductive-recursive types.
An Enhanced Covering Lemma for Multiterminal Source Coding
Venue: arXiv cs.IT 2006
Year: 2006

An enhanced covering lemma for a Markov chain is proved in this paper, and then the distributed source coding problem of correlated general sources with one average distortion criterion under fixed-length coding is investigated. Based on the enhanced lemma, a sufficient and necessary condition for determining the achievability of rate-distortion triples is given.
Estimation of the traffic in the binary channel for data networks
Venue: arXiv cs.IT 2006
Year: 2006

It is impossible to provide an effective utilization of communication networks without the analysis of the quantitative characteristics of the traffic in real time. The constant supervision of all channels of the data practically is impracticable because requires transfer of the significant additional information on a network and large resources expenses for devices of the control. Thus, the task on traffic estimation with small expenses in real time is the urgent.
The central nature of the Hidden Subgroup problem
Venue: arXiv cs.CC 2006
Year: 2006

We show that several problems that figure prominently in quantum computing, including Hidden Coset, Hidden Shift, and Orbit Coset, are equivalent or reducible to Hidden Subgroup for a large variety of groups. We also show that, over permutation groups, the decision version and search version of Hidden Subgroup are polynomial-time equivalent. For Hidden Subgroup over dihedral groups, such an equivalence can be obtained if the order of the group is smooth. Finally, we give nonadaptive program checkers for Hidden Subgroup and its decision version.
Reversible Logic to Cryptographic Hardware: A New Paradigm
Venue: arXiv cs.CR 2006
Year: 2006

Differential Power Analysis (DPA) presents a major challenge to mathematically-secure cryptographic protocols. Attackers can break the encryption by measuring the energy consumed in the working digital circuit. To prevent this type of attack, this paper proposes the use of reversible logic for designing the ALU of a cryptosystem. Ideally, reversible circuits dissipate zero energy. Thus, it would be of great significance to apply reversible logic to designing secure cryptosystems. As far as is known, this is the first attempt to apply reversible logic to developing secure cryptosystems. In a prototype of a reversible ALU for a crypto-processor, reversible designs of adders and Montgomery multipliers are presented. The reversible designs of a carry propagate adder, four-to-two and five-to-two carry save adders are presented using a reversible TSG gate. One of the important properties of the TSG gate is that it can work singly as a reversible full adder. In order to design the reversible Montgomery multiplier, novel reversible sequential circuits are also proposed which are integrated with the proposed adders to design a reversible modulo multiplier. It is intended that this paper will provide a starting point for developing cryptosystems secure against DPA attacks.
Properties of Codes with the Rank Metric
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, we study properties of rank metric codes in general and maximum rank distance (MRD) codes in particular. For codes with the rank metric, we first establish Gilbert and sphere-packing bounds, and then obtain the asymptotic forms of these two bounds and the Singleton bound. Based on the asymptotic bounds, we observe that asymptotically Gilbert-Varsharmov bound is exceeded by MRD codes and sphere-packing bound cannot be attained. We also establish bounds on the rank covering radius of maximal codes, and show that all MRD codes are maximal codes and all the MRD codes known so far achieve the maximum rank covering radius.
A Mobile Transient Internet Architecture
Venue: arXiv cs.NI 2006
Year: 2006

This paper describes a new architecture for transient mobile networks destined to merge existing and future network architectures, communication implementations and protocol operations by introducing a new paradigm to data delivery and identification. The main goal of our research is to enable seamless end-to-end communication between mobile and stationary devices across multiple networks and through multiple communication environments. The architecture establishes a set of infrastructure components and protocols that set the ground for a Persistent Identification Network (PIN). The basis for the operation of PIN is an identification space consisting of unique location independent identifiers similar to the ones implemented in the Handle system. Persistent Identifiers are used to identify and locate Digital Entities which can include devices, services, users and even traffic. The architecture establishes a primary connection independent logical structure that can operate over conventional networks or more advanced peer-to-peer aggregation networks. Communication is based on routing pools and novel protocols for routing data across several abstraction levels of the network, regardless of the end-points' current association and state...
Quantifier elimination for the reals with a predicate for the powers of two
Venue: arXiv cs.LO 2006
Year: 2006

In 1985, van den Dries showed that the theory of the reals with a predicate for the integer powers of two admits quantifier elimination in an expanded language, and is hence decidable. He gave a model-theoretic argument, which provides no apparent bounds on the complexity of a decision procedure. We provide a syntactic argument that yields a procedure that is primitive recursive, although not elementary. In particular, we show that it is possible to eliminate a single block of existential quantifiers in time $2^0_{O(n)}$, where $n$ is the length of the input formula and $2_k^x$ denotes $k$-fold iterated exponentiation.
Fitness Uniform Optimization
Venue: arXiv cs.NE 2006
Year: 2006

In evolutionary algorithms, the fitness of a population increases with time by mutating and recombining individuals and by a biased selection of more fit individuals. The right selection pressure is critical in ensuring sufficient optimization progress on the one hand and in preserving genetic diversity to be able to escape from local optima on the other hand. Motivated by a universal similarity relation on the individuals, we propose a new selection scheme, which is uniform in the fitness values. It generates selection pressure toward sparsely populated fitness regions, not necessarily toward higher fitness, as is the case for all other selection schemes. We show analytically on a simple example that the new selection scheme can be much more effective than standard selection schemes. We also propose a new deletion scheme which achieves a similar result via deletion and show how such a scheme preserves genetic diversity more effectively than standard approaches. We compare the performance of the new schemes to tournament selection and random deletion on an artificial deceptive problem and a range of NP-hard problems: traveling salesman, set covering and satisfiability.