OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Modal Human-Machine Communication for Instructing Robot Grasping Tasks
Venue: arXiv cs.HC 2005
Year: 2005

A major challenge for the realization of intelligent robots is to supply them with cognitive abilities in order to allow ordinary users to program them easily and intuitively. One way of such programming is teaching work tasks by interactive demonstration. To make this effective and convenient for the user, the machine must be capable to establish a common focus of attention and be able to use and integrate spoken instructions, visual perceptions, and non-verbal clues like gestural commands. We report progress in building a hybrid architecture that combines statistical methods, neural networks, and finite state machines into an integrated system for instructing grasping tasks by man-machine interaction. The system combines the GRAVIS-robot for visual attention and gestural instruction with an intelligent interface for speech recognition and linguistic interpretation, and an modality fusion module to allow multi-modal task-oriented man-machine communication with respect to dextrous robot manipulation of objects.
Optimizing semiconductor devices by self-organizing particle swarm
Venue: arXiv cs.NE 2005
Year: 2005

A self-organizing particle swarm is presented. It works in dissipative state by employing the small inertia weight, according to experimental analysis on a simplified model, which with fast convergence. Then by recognizing and replacing inactive particles according to the process deviation information of device parameters, the fluctuation is introduced so as to driving the irreversible evolution process with better fitness. The testing on benchmark functions and an application example for device optimization with designed fitness function indicates it improves the performance effectively.
Efficient Approximation of Convex Recolorings
Venue: arXiv cs.DS 2005
Year: 2005

A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring of trees arise in areas such as phylogenetics, linguistics, etc. eg, a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree. Research on perfect phylogeny is usually focused on finding a tree so that few predetermined partial colorings of its vertices are convex. When a coloring of a tree is not convex, it is desirable to know "how far" it is from a convex one. In [19], a natural measure for this distance, called the recoloring distance was defined: the minimal number of color changes at the vertices needed to make the coloring convex. This can be viewed as minimizing the number of "exceptional vertices" w.r.t. to a closest convex coloring. The problem was proved to be NP-hard even for colored string. In this paper we continue the work of [19], and present a 2-approximation algorithm of convex recoloring of strings whose running time O(cn), where c is the number of colors and n is the size of the input, and an O(cn^2)-time 3-approximation algorithm for convex recoloring of trees.
Dominance Based Crossover Operator for Evolutionary Multi-objective Algorithms
Venue: arXiv cs.AI 2005
Year: 2005

In spite of the recent quick growth of the Evolutionary Multi-objective Optimization (EMO) research field, there has been few trials to adapt the general variation operators to the particular context of the quest for the Pareto-optimal set. The only exceptions are some mating restrictions that take in account the distance between the potential mates - but contradictory conclusions have been reported. This paper introduces a particular mating restriction for Evolutionary Multi-objective Algorithms, based on the Pareto dominance relation: the partner of a non-dominated individual will be preferably chosen among the individuals of the population that it dominates. Coupled with the BLX crossover operator, two different ways of generating offspring are proposed. This recombination scheme is validated within the well-known NSGA-II framework on three bi-objective benchmark problems and one real-world bi-objective constrained optimization problem. An acceleration of the progress of the population toward the Pareto set is observed on all problems.
An explicit formula for the number of tunnels in digital objects
Venue: arXiv cs.DM 2005
Year: 2005

An important concept in digital geometry for computer imagery is that of tunnel. In this paper we obtain a formula for the number of tunnels as a function of the number of the object vertices, pixels, holes, connected components, and 2x2 grid squares. It can be used to test for tunnel-freedom a digital object, in particular a digital curve.
On the Ancestral Compatibility of Two Phylogenetic Trees with Nested Taxa
Venue: arXiv cs.DM 2005
Year: 2005

Compatibility of phylogenetic trees is the most important concept underlying widely-used methods for assessing the agreement of different phylogenetic trees with overlapping taxa and combining them into common supertrees to reveal the tree of life. The notion of ancestral compatibility of phylogenetic trees with nested taxa was introduced by Semple et al in 2004. In this paper we analyze in detail the meaning of this compatibility from the points of view of the local structure of the trees, of the existence of embeddings into a common supertree, and of the joint properties of their cluster representations. Our analysis leads to a very simple polynomial-time algorithm for testing this compatibility, which we have implemented and is freely available for download from the BioPerl collection of Perl modules for computational biology.
HepToX: Heterogeneous Peer to Peer XML Databases
Venue: arXiv cs.DB 2005
Year: 2005

We study a collection of heterogeneous XML databases maintaining similar and related information, exchanging data via a peer to peer overlay network. In this setting, a mediated global schema is unrealistic. Yet, users/applications wish to query the databases via one peer using its schema. We have recently developed HepToX, a P2P Heterogeneous XML database system. A key idea is that whenever a peer enters the system, it establishes an acquaintance with a small number of peer databases, possibly with different schema. The peer administrator provides correspondences between the local schema and the acquaintance schema using an informal and intuitive notation of arrows and boxes. We develop a novel algorithm that infers a set of precise mapping rules between the schemas from these visual annotations. We pin down a semantics of query translation given such mapping rules, and present a novel query translation algorithm for a simple but expressive fragment of XQuery, that employs the mapping rules in either direction. We show the translation algorithm is correct. Finally, we demonstrate the utility and scalability of our ideas and algorithms with a detailed set of experiments on top of the Emulab, a large scale P2P network emulation testbed.
A batch scheduler with high level components
Venue: arXiv cs.DC 2005
Year: 2005

In this article we present the design choices and the evaluation of a batch scheduler for large clusters, named OAR. This batch scheduler is based upon an original design that emphasizes on low software complexity by using high level tools. The global architecture is built upon the scripting language Perl and the relational database engine Mysql. The goal of the project OAR is to prove that it is possible today to build a complex system for ressource management using such tools without sacrificing efficiency and scalability. Currently, our system offers most of the important features implemented by other batch schedulers such as priority scheduling (by queues), reservations, backfilling and some global computing support. Despite the use of high level tools, our experiments show that our system has performances close to other systems. Furthermore, OAR is currently exploited for the management of 700 nodes (a metropolitan GRID) and has shown good efficiency and robustness.
The OAI Data-Provider Registration and Validation Service
Venue: arXiv cs.DL 2005
Year: 2005

I present a summary of recent use of the Open Archives Initiative (OAI) registration and validation services for data-providers. The registration service has seen a steady stream of registrations since its launch in 2002, and there are now over 220 registered repositories. I examine the validation logs to produce a breakdown of reasons why repositories fail validation. This breakdown highlights some common problems and will be used to guide work to improve the validation service.
A Non-Cooperative Power Control Game in Delay-Constrained Multiple-Access Networks
Venue: arXiv cs.IT 2005
Year: 2005

A game-theoretic approach for studying power control in multiple-access networks with transmission delay constraints is proposed. A non-cooperative power control game is considered in which each user seeks to choose a transmit power that maximizes its own utility while satisfying the user's delay requirements. The utility function measures the number of reliable bits transmitted per joule of energy and the user's delay constraint is modeled as an upper bound on the delay outage probability. The Nash equilibrium for the proposed game is derived, and its existence and uniqueness are proved. Using a large-system analysis, explicit expressions for the utilities achieved at equilibrium are obtained for the matched filter, decorrelating and minimum mean square error multiuser detectors. The effects of delay constraints on the users' utilities (in bits/Joule) and network capacity (i.e., the maximum number of users that can be supported) are quantified.
Treillis de concepts et ontologies pour l'interrogation d'un annuaire de sources de données biologiques (BioRegistry)
Venue: arXiv cs.DB 2005
Year: 2005

Bioinformatic data sources available on the web are multiple and heterogenous. The lack of documentation and the difficulty of interaction with these data sources require users competence in both informatics and biological fields for an optimal use of sources contents that remain rather under exploited. In this paper we present an approach based on formal concept analysis to classify and search relevant bioinformatic data sources for a given query. It consists in building the concept lattice from the binary relation between bioinformatic data sources and their associated metadata. The concept built from a given query is then merged into the concept lattice. The result is given by the extraction of the set of sources belonging to the extents of the query concept subsumers in the resulting concept lattice. The sources ranking is given by the concept specificity order in the concept lattice. An improvement of the approach consists in automatic query refinement thanks to domain ontologies. Two forms of refinement are possible by generalisation and by specialisation. ----- Les sources de données biologiques disponibles sur le web sont multiples et hétérogènes. L'utilisation optimale de ces ressources nécessite aujourd'hui de la part des utilisateurs des compétences à la fois en informatique et en biologie, du fait du manque de documentation et des difficultés d'interaction avec les sources de données. De fait, les contenus de ces ressources restent souvent sous-exploités. Nous présentons ici une approche basée sur l'analyse de concepts formels, pour organiser et rechercher des sources de données biologiques pertinentes pour une requête donnée. Le travail consiste à construire un treillis de concepts à partir des méta-données associées aux sources. Le concept construit à partir d'une requête donnée est alors intégré au treillis. La réponse à la requête est ensuite fournie par l'extraction des sources de données appartenant aux extensions des concepts subsumant le concept requête dans le treillis. Les sources ainsi retournées peuvent être triées selon l'ordre de spécificité des concepts dans le treillis. Une procédure de raffinement de requête, basée sur des ontologies du domaine, permet d'améliorer le rappel par généralisation ou par spécialisation
Analysis of Relationship between Strategic and Aggregate Energy Minimization in Delay-Constrained Wireless Networks
Venue: arXiv cs.NI 2005
Year: 2005

We formulate two versions of the power control problem for wireless networks with latency constraints arising from duty cycle allocations In the first version, strategic power optimization, wireless nodes are modeled as rational agents in a power game, who strategically adjust their powers to minimize their own energy. In the other version, joint power optimization, wireless nodes jointly minimize the aggregate energy expenditure. Our analysis of these models yields insights into the different energy outcomes of strategic versus joint power optimization. We derive analytical solutions for power allocation under both models and study how they are affected by data loads and channel quality. We derive simple necessary conditions for the existence of Nash equilibria in the power game and also provide numerical examples of optimal power allocation under both models. Finally, we show that joint optimization can (sometimes) be Pareto-optimal and dominate strategic optimization, i.e the energy expenditure of all nodes is lower than if they were using strategic optimization.
Fast Recompilation of Object Oriented Modules
Venue: arXiv cs.PL 2005
Year: 2005

Once a program file is modified, the recompilation time should be minimized, without sacrificing execution speed or high level object oriented features. The recompilation time is often a problem for the large graphical interactive distributed applications tackled by modern OO languages. A compilation server and fast code generator were developed and integrated with the SRC Modula-3 compiler and Linux ELF dynamic linker. The resulting compilation and recompilation speedups are impressive. The impact of different language features, processor speed, and application size are discussed.
A Fixed-Length Coding Algorithm for DNA Sequence Compression
Venue: arXiv cs.IT 2005
Year: 2005

While achieving a compression ratio of 2.0 bits/base, the new algorithm codes non-N bases in fixed length. It dramatically reduces the time of coding and decoding than previous DNA compression algorithms and some universal compression programs.
Minimal Network Coding for Multicast
Venue: arXiv cs.IT 2005
Year: 2005

We give an information flow interpretation for multicasting using network coding. This generalizes the fluid model used to represent flows to a single receiver. Using the generalized model, we present a decentralized algorithm to minimize the number of packets that undergo network coding. We also propose a decentralized algorithm to construct capacity achieving multicast codes when the processing at some nodes is restricted to routing. The proposed algorithms can be coupled with existing decentralized schemes to achieve minimum cost muticast.
Comments on `Bit Interleaved Coded Modulation'
Venue: arXiv cs.IT 2005
Year: 2005

Caire, Taricco and Biglieri presented a detailed analysis of bit interleaved coded modulation, a simple and popular technique used to improve system performance, especially in the context of fading channels. They derived an upper bound to the probability of error, called the expurgated bound. In this correspondence, the proof of the expurgated bound is shown to be flawed. A new upper bound is also derived. It is not known whether the original expurgated bound is valid for the important special case of square QAM with Gray labeling, but the new bound is very close to, and slightly tighter than, the original bound for a numerical example.
The Complexity of Kings
Venue: arXiv cs.CC 2005
Year: 2005

A king in a directed graph is a node from which each node in the graph can be reached via paths of length at most two. There is a broad literature on tournaments (completely oriented digraphs), and it has been known for more than half a century that all tournaments have at least one king [Lan53]. Recently, kings have proven useful in theoretical computer science, in particular in the study of the complexity of the semifeasible sets [HNP98,HT05] and in the study of the complexity of reachability problems [Tan01,NT02]. In this paper, we study the complexity of recognizing kings. For each succinctly specified family of tournaments, the king problem is known to belong to $Π_2^p$ [HOZZ]. We prove that this bound is optimal: We construct a succinctly specified tournament family whose king problem is $Π_2^p$-complete. It follows easily from our proof approach that the problem of testing kingship in succinctly specified graphs (which need not be tournaments) is $Π_2^p$-complete. We also obtain $Π_2^p$-completeness results for k-kings in succinctly specified j-partite tournaments, $k,j \geq 2$, and we generalize our main construction to show that $Π_2^p$-completeness holds for testing k-kingship in succinctly specified families of tournaments for all $k \geq 2$.
Strongly secure ramp secret sharing schemes for general access structures
Venue: arXiv cs.CR 2005
Year: 2005

Ramp secret sharing (SS) schemes can be classified into strong ramp SS schemes and weak ramp SS schemes. The strong ramp SS schemes do not leak out any part of a secret explicitly even in the case where some information about the secret leaks from a non-qualified set of shares, and hence, they are more desirable than weak ramp SS schemes. However, it is not known how to construct the strong ramp SS schemes in the case of general access structures. In this paper, it is shown that a strong ramp SS scheme can always be constructed from a SS scheme with plural secrets for any feasible general access structure. As a byproduct, it is pointed out that threshold ramp SS schemes based on Shamir's polynomial interpolation method are {\em not} always strong.
Measuring Woody: The Size of Debian 3.0
Venue: arXiv cs.SE 2005
Year: 2005

Debian is possibly the largest free software distribution, with well over 4,500 source packages in the latest stable release (Debian 3.0) and more than 8,000 source packages in the release currently in preparation. However, we wish to know what these numbers mean. In this paper, we use David A. Wheeler's SLOCCount system to determine the number of physical source lines of code (SLOC) of Debian 3.0 (aka woody). We show that Debian 3.0 includes more than 105,000,000 physical SLOC (almost twice than Red Hat 9, released about 8 months later), showing that the Debian development model (based on the work of a large group of voluntary developers spread around the world) is at least as capable as other development methods (like the more centralized one, based on the work of employees, used by Red Hat or Microsoft) to manage distributions of this size. It is also shown that if Debian had been developed using traditional proprietary methods, the COCOMO model estimates that its cost would be close to $6.1 billion USD to develop Debian 3.0. In addition, we offer both an analysis of the programming languages used in the distribution (C amounts for about 65%, C++ for about 12%, Shell for about 8% and LISP is around 4%, with many others to follow), and the largest packages (The Linux kernel, Mozilla, XFree86, PM3, etc.)
Data Visualization on Shared Usage Multi-Screen Environment
Venue: arXiv cs.MM 2005
Year: 2005

The modern multimedia technologies based on the whole palette of hardware and software facilities of real-time high-speed information processing, in a combination with effective facilities of the remote access to information resources, allow us to visualize diverse types of information. Data visualization facilities – is the face of the Automated Control System on whom often judge about their efficiency. They take a special place, providing visualization of the diverse information necessary for decision-making by a final control link - the person allocated by certain powers.
Stability of Scheduled Multi-access Communication over Quasi-static Flat Fading Channels with Random Coding and Independent Decoding
Venue: arXiv cs.IT 2005
Year: 2005

The stability of scheduled multiaccess communication with random coding and independent decoding of messages is investigated. The number of messages that may be scheduled for simultaneous transmission is limited to a given maximum value, and the channels from transmitters to receiver are quasi-static, flat, and have independent fades. Requests for message transmissions are assumed to arrive according to an i.i.d. arrival process. Then, we show the following: (1) in the limit of large message alphabet size, the stability region has an interference limited information-theoretic capacity interpretation, (2) state-independent scheduling policies achieve this asymptotic stability region, and (3) in the asymptotic limit corresponding to immediate access, the stability region for non-idling scheduling policies is shown to be identical irrespective of received signal powers.
Maxwell Construction: The Hidden Bridge between Iterative and Maximum a Posteriori Decoding
Venue: arXiv cs.IT 2005
Year: 2005

There is a fundamental relationship between belief propagation and maximum a posteriori decoding. A decoding algorithm, which we call the Maxwell decoder, is introduced and provides a constructive description of this relationship. Both, the algorithm itself and the analysis of the new decoder are reminiscent of the Maxwell construction in thermodynamics. This paper investigates in detail the case of transmission over the binary erasure channel, while the extension to general binary memoryless channels is discussed in a companion paper.
Field geology with a wearable computer: 1st results of the Cyborg Astrobiologist System
Venue: arXiv cs.CV 2005
Year: 2005

We present results from the first geological field tests of the `Cyborg Astrobiologist', which is a wearable computer and video camcorder system that we are using to test and train a computer-vision system towards having some of the autonomous decision-making capabilities of a field-geologist. The Cyborg Astrobiologist platform has thus far been used for testing and development of these algorithms and systems: robotic acquisition of quasi-mosaics of images, real-time image segmentation, and real-time determination of interesting points in the image mosaics. This work is more of a test of the whole system, rather than of any one part of the system. However, beyond the concept of the system itself, the uncommon map (despite its simplicity) is the main innovative part of the system. The uncommon map helps to determine interest-points in a context-free manner. Overall, the hardware and software systems function reliably, and the computer-vision algorithms are adequate for the first field tests. In addition to the proof-of-concept aspect of these field tests, the main result of these field tests is the enumeration of those issues that we can improve in the future, including: dealing with structural shadow and microtexture, and also, controlling the camera's zoom lens in an intelligent manner. Nonetheless, despite these and other technical inadequacies, this Cyborg Astrobiologist system, consisting of a camera-equipped wearable-computer and its computer-vision algorithms, has demonstrated its ability of finding genuinely interesting points in real-time in the geological scenery, and then gathering more information about these interest points in an automated manner. We use these capabilities for autonomous guidance towards geological points-of-interest.