OpenRaiser/Intern-Atlas huggingface dataset:
Equivalence Classes of Optimal Structures in HP Protein Models Including Side Chains
Venue: arXiv cs.CE 2009
Year: 2009

Lattice protein models, as the Hydrophobic-Polar (HP) model, are a common abstraction to enable exhaustive studies on structure, function, or evolution of proteins. A main issue is the high number of optimal structures, resulting from the hydrophobicity-based energy function applied. We introduce an equivalence relation on protein structures that correlates to the energy function. We discuss the efficient enumeration of optimal representatives of the corresponding equivalence classes and the application of the results.
How to Complete an Interactive Configuration Process?
Venue: arXiv cs.SE 2009
Year: 2009

When configuring customizable software, it is useful to provide interactive tool-support that ensures that the configuration does not breach given constraints. But, when is a configuration complete and how can the tool help the user to complete it? We formalize this problem and relate it to concepts from non-monotonic reasoning well researched in Artificial Intelligence. The results are interesting for both practitioners and theoreticians. Practitioners will find a technique facilitating an interactive configuration process and experiments supporting feasibility of the approach. Theoreticians will find links between well-known formal concepts and a concrete practical application.
Singularity Analysis of Lower-Mobility Parallel Manipulators Using Grassmann-Cayley Algebra
Venue: arXiv cs.RO 2009
Year: 2009

This paper introduces a methodology to analyze geometrically the singularities of manipulators, of which legs apply both actuation forces and constraint moments to their moving platform. Lower-mobility parallel manipulators and parallel manipulators, of which some legs do not have any spherical joint, are such manipulators. The geometric conditions associated with the dependency of six Plücker vectors of finite lines or lines at infinity constituting the rows of the inverse Jacobian matrix are formulated using Grassmann-Cayley Algebra. Accordingly, the singularity conditions are obtained in vector form. This study is illustrated with the singularity analysis of four manipulators.
Virtual-Threading: Advanced General Purpose Processors Architecture
Venue: arXiv cs.AR 2009
Year: 2009

The paper describes the new computers architecture, the main features of which has been claimed in the Russian Federation patent 2312388 and in the US patent application 11/991331. This architecture is intended to effective support of the General Purpose Parallel Computing (GPPC), the essence of which is extremely frequent switching of threads between states of activity and states of viewed in the paper the algorithmic latency. To emphasize the same impact of the architectural latency and the algorithmic latency upon GPPC, is introduced the new notion of the generalized latency and is defined its quantitative measure - the Generalized Latency Tolerance (GLT). It is shown that a well suited for GPPC implementation architecture should have high level of GLT and is described such architecture, which is called the Virtual-Threaded Machine. This architecture originates a processor virtualization in the direction of activities virtualization, which is orthogonal to the well-known direction of memory virtualization. The key elements of the architecture are 1) the distributed fine grain representation of the architectural register file, which elements are hardware swapped through levels of a microarchitectural memory, 2) the prioritized fine grain direct hardware multiprogramming, 3) the access controlled virtual addressing and 4) the hardware driven semaphores. The composition of these features lets to introduce new styles of operating system (OS) programming, which is free of interruptions, and of applied programming with a very rare using the OS services.
A User Model for Information Erasure
Venue: arXiv cs.CR 2009
Year: 2009

Hunt and Sands (ESOP'08) studied a notion of information erasure for systems which receive secrets intended for limited-time use. Erasure demands that once a secret has fulfilled its purpose the subsequent behaviour of the system should reveal no information about the erased data. In this paper we address a shortcoming in that work: for erasure to be possible the user who provides data must also play his part, but previously that role was only specified informally. Here we provide a formal model of the user and a collection of requirements called erasure friendliness. We prove that an erasure-friendly user can be composed with an erasing system (in the sense of Hunt and Sands) to obtain a combined system which is jointly erasing in an appropriate sense. In doing so we identify stronger requirements on the user than those informally described in the previous work.
Complementary Space for Enhanced Uncertainty and Dynamics Visualization
Venue: arXiv cs.CG 2009
Year: 2009

Given a computer model of a physical object, it is often quite difficult to visualize and quantify any global effects on the shape representation caused by local uncertainty and local errors in the data. This problem is further amplified when dealing with hierarchical representations containing varying levels of detail and / or shapes undergoing dynamic deformations. In this paper, we compute, quantify and visualize the complementary topological and geometrical features of 3D shape models, namely, the tunnels, pockets and internal voids of the object. We find that this approach sheds a unique light on how a model is affected by local uncertainty, errors or modifications and show how the presence or absence of complementary shape features can be essential to an object's structural form and function.
Piercing translates and homothets of a convex body
Venue: arXiv cs.CG 2009
Year: 2009

According to a classical result of Grünbaum, the transversal number $τ(\F)$ of any family $\F$ of pairwise-intersecting translates or homothets of a convex body $C$ in $\RR^d$ is bounded by a function of $d$. Denote by $α(C)$ (resp. $β(C)$) the supremum of the ratio of the transversal number $τ(\F)$ to the packing number $ν(\F)$ over all families $\F$ of translates (resp. homothets) of a convex body $C$ in $\RR^d$. Kim et al. recently showed that $α(C)$ is bounded by a function of $d$ for any convex body $C$ in $\RR^d$, and gave the first bounds on $α(C)$ for convex bodies $C$ in $\RR^d$ and on $β(C)$ for convex bodies $C$ in the plane. Here we show that $β(C)$ is also bounded by a function of $d$ for any convex body $C$ in $\RR^d$, and present new or improved bounds on both $α(C)$ and $β(C)$ for various convex bodies $C$ in $\RR^d$ for all dimensions $d$. Our techniques explore interesting inequalities linking the covering and packing densities of a convex body. Our methods for obtaining upper bounds are constructive and lead to efficient constant-factor approximation algorithms for finding a minimum-cardinality point set that pierces a set of translates or homothets of a convex body.
Congestion games with resource reuse and applications in spectrum sharing
Venue: arXiv cs.GT 2009
Year: 2009

In this paper we consider an extension to the classical definition of congestion games (CG) in which multiple users share the same set of resources and their payoff for using any resource is a function of the total number of users sharing it. The classical congestion games enjoy some very appealing properties, including the existence of a Nash equilibrium and that every improvement path is finite and leads to such a NE (also called the finite improvement property or FIP), which is also a local optimum to a potential function. On the other hand, this class of games does not model well the congestion or resource sharing in a wireless context, a prominent feature of which is spatial reuse. What this translates to in the context of a congestion game is that a users payoff for using a resource (interpreted as a channel) is a function of the its number of its interfering users sharing that channel, rather than the total number among all users. This makes the problem quite different. We will call this the congestion game with resource reuse (CG-RR). In this paper we study intrinsic properties of such a game; in particular, we seek to address under what conditions on the underlying network this game possesses the FIP or NE. We also discuss the implications of these results when applied to wireless spectrum sharing
A Geometric Approach to Solve Fuzzy Linear Systems of Differential Equations
Venue: arXiv cs.NA 2009
Year: 2009

In this paper, systems of linear differential equations with crisp real coefficients and with initial condition described by a vector of fuzzy numbers are studied. A new method based on the geometric representations of linear transformations is proposed to find a solution. The most important difference between this method and methods offered in previous papers is that the solution is considered to be a fuzzy set of real vector-functions rather than a fuzzy vector-function. Each member of the set satisfies the given system with a certain possibility. It is shown that at any time the solution constitutes a fuzzy region in the coordinate space, alfa-cuts of which are nested parallelepipeds. Proposed method is illustrated on examples.
Wiener index of binomial trees and Fibonacci trees
Venue: arXiv cs.DM 2009
Year: 2009

We obtain a closed-form expression for the Wiener index of binomial trees. We outline efficient algorithms for computing the Wiener indices of Fibonacci and binary Fibonacci trees.
Quickest detection in coupled systems
Venue: arXiv cs.IT 2009
Year: 2009

This work considers the problem of quickest detection of signals in a coupled system of N sensors, which receive continuous sequential observations from the environment. It is assumed that the signals, which are modeled a general Ito processes, are coupled across sensors, but that their onset times may differ from sensor to sensor. The objective is the optimal detection of the first time at which any sensor in the system receives a signal. The problem is formulated as a stochastic optimization problem in which an extended average Kullback- Leibler divergence criterion is used as a measure of detection delay, with a constraint on the mean time between false alarms. The case in which the sensors employ cumulative sum (CUSUM) strategies is considered, and it is proved that the minimum of N CUSUMs is asymptotically optimal as the mean time between false alarms increases without bound.
Artificial Immune Systems
Venue: arXiv cs.AI 2009
Year: 2009

The biological immune system is a robust, complex, adaptive system that defends the body from foreign pathogens. It is able to categorize all cells (or molecules) within the body as self-cells or non-self cells. It does this with the help of a distributed task force that has the intelligence to take action from a local and also a global perspective using its network of chemical messengers for communication. There are two major branches of the immune system. The innate immune system is an unchanging mechanism that detects and destroys certain invading organisms, whilst the adaptive immune system responds to previously unknown foreign cells and builds a response to them that can remain in the body over a long period of time. This remarkable information processing biological system has caught the attention of computer science in recent years. A novel computational intelligence technique, inspired by immunology, has emerged, called Artificial Immune Systems. Several concepts from the immune have been extracted and applied for solution to real world science and engineering problems. In this tutorial, we briefly describe the immune system metaphors that are relevant to existing Artificial Immune Systems methods. We will then show illustrative real-world problems suitable for Artificial Immune Systems and give a step-by-step algorithm walkthrough for one such problem. A comparison of the Artificial Immune Systems to other well-known algorithms, areas for future work, tips & tricks and a list of resources will round this tutorial off. It should be noted that as Artificial Immune Systems is still a young and evolving field, there is not yet a fixed algorithm template and hence actual implementations might differ somewhat from time to time and from those examples given here.
Distortion Exponent in MIMO Channels with Feedback
Venue: arXiv cs.IT 2009
Year: 2009

The transmission of a Gaussian source over a block-fading multiple antenna channel in the presence of a feedback link is considered. The feedback link is assumed to be an error and delay free link of capacity 1 bit per channel use. Under the short-term power constraint, the optimal exponential behavior of the end-to-end average distortion is characterized for all source-channel bandwidth ratios. It is shown that the optimal transmission strategy is successive refinement source coding followed by progressive transmission over the channel, in which the channel block is allocated dynamically among the layers based on the channel state using the feedback link as an instantaneous automatic repeat request (ARQ) signal.
A Dialogue Concerning Two World Systems: Info-Computational vs. Mechanistic
Venue: arXiv cs.GL 2009
Year: 2009

The dialogue develops arguments for and against adopting a new world system, info-computationalist naturalism, that is poised to replace the traditional mechanistic world system. We try to figure out what the info-computational paradigm would mean, in particular its pancomputationalism. We make some steps towards developing the notion of computing that is necessary here, especially in relation to traditional notions. We investigate whether pancomputationalism can possibly provide the basic causal structure to the world, whether the overall research programme appears productive and whether it can revigorate computationalism in the philosophy of mind.
A Note on Gradually Varied Functions and Harmonic Functions
Venue: arXiv cs.DM 2009
Year: 2009

Any constructive continuous function must have a gradually varied approximation in compact space. However, the refinement of domain for $σ-$-net might be very small. Keeping the original discretization (square or triangulation), can we get some interesting properties related to gradual variation? In this note, we try to prove that many harmonic functions are gradually varied or near gradually varied; this means that the value of the center point differs from that of its neighbor at most by 2. It is obvious that most of the gradually varied functions are not harmonic.This note discusses some of the basic harmonic functions in relation to gradually varied functions.
Approximation Algorithms for Link Scheduling with Physical Interference Model in Wireless Multi-hop Networks
Venue: arXiv cs.NI 2009
Year: 2009

The link scheduling in wireless multi-hop networks is addressed. Different from most of work that adopt the protocol interference model which merely take consideration of packet collisions, our proposed algorithms use the physical interference model to reflect the aggregated signal to interference and noise ratio (SINR), which is a more accurate abstraction of the real scenario. We first propose a centralized scheduling method based on the Integer Linear Programming (ILP) and resolve it by an approximate solution based on the randomized rounding method. The probability bound of getting a guaranteed approximate factor is given. We then extend the centralized algorithm to a distributed solution, which is favorable in wireless networks. It is proven that with the distributed scheduling method, all links can transmit without interference, and the approximate ratio of the algorithm is also given.
Artificial Immune Tissue using Self-Orgamizing Networks
Venue: arXiv cs.AI 2009
Year: 2009

As introduced by Bentley et al. (2005), artificial immune systems (AIS) are lacking tissue, which is present in one form or another in all living multi-cellular organisms. Some have argued that this concept in the context of AIS brings little novelty to the already saturated field of the immune inspired computational research. This article aims to show that such a component of an AIS has the potential to bring an advantage to a data processing algorithm in terms of data pre-processing, clustering and extraction of features desired by the immune inspired system. The proposed tissue algorithm is based on self-organizing networks, such as self-organizing maps (SOM) developed by Kohonen (1996) and an analogy of the so called Toll-Like Receptors (TLR) affecting the activation function of the clusters developed by the SOM.
Word Sense Disambiguation Based on Mutual Information and Syntactic Patterns
Venue: arXiv cs.CL 2009
Year: 2009

This paper describes a hybrid system for WSD, presented to the English all-words and lexical-sample tasks, that relies on two different unsupervised approaches. The first one selects the senses according to mutual information proximity between a context word a variant of the sense. The second heuristic analyzes the examples of use in the glosses of the senses so that simple syntactic patterns are inferred. This patterns are matched against the disambiguation contexts. We show that the first heuristic obtains a precision and recall of .58 and .35 respectively in the all words task while the second obtains .80 and .25. The high precision obtained recommends deeper research of the techniques. Results for the lexical sample task are also provided.
On the characterization of the regions of feasible trajectories in the workspace of parallel manipulators
Venue: arXiv cs.RO 2009
Year: 2009

It was shown recently that parallel manipulators with several inverse kinematic solutions have the ability to avoid parallel singularities [Chablat 1998a] and self-collisions [Chablat 1998b] by choosing appropriate joint configurations for the legs. In effect, depending on the joint configurations of the legs, a given configuration of the end-effector may or may not be free of singularity and collision. Characterization of the collision/singularity-free workspace is useful but may be insufficient since two configurations can be accessible without collisions nor singularities but it may not exist a feasible trajectory between them. The goal of this paper is to define the maximal regions of the workspace where it is possible to execute trajectories. Twodifferent families of regions are defined : 1. those regions where the end-effector can move between any set of points, and 2. the regions where any continuous path can be tracked. These regions are characterized from the notion of aspects and free-aspects recently defined for parallel manipulators [Chablat 1998b]. The construction of these regions is achieved by enrichment techniques and using an extension of the octree structures to spaces of dimension greater than three. Illustrative examples show the interest of this study to the optimization of trajectories and the design of parallel manipulators.
Word Sense Disambiguation Using English-Spanish Aligned Phrases over Comparable Corpora
Venue: arXiv cs.CL 2009
Year: 2009

In this paper we describe a WSD experiment based on bilingual English-Spanish comparable corpora in which individual noun phrases have been identified and aligned with their respective counterparts in the other language. The evaluation of the experiment has been carried out against SemCor. We show that, with the alignment algorithm employed, potential precision is high (74.3%), however the coverage of the method is low (2.7%), due to alignments being far less frequent than we expected. Contrary to our intuition, precision does not rise consistently with the number of alignments. The coverage is low due to several factors; there are important domain differences, and English and Spanish are too close languages for this approach to be able to discriminate efficiently between senses, rendering it unsuitable for WSD, although the method may prove more productive in machine translation.
Distributed Abstract Optimization via Constraints Consensus: Theory and Applications
Venue: arXiv cs.DC 2009
Year: 2009

Distributed abstract programs are a novel class of distributed optimization problems where (i) the number of variables is much smaller than the number of constraints and (ii) each constraint is associated to a network node. Abstract optimization programs are a generalization of linear programs that captures numerous geometric optimization problems. We propose novel constraints consensus algorithms for distributed abstract programs: as each node iteratively identifies locally active constraints and exchanges them with its neighbors, the network computes the active constraints determining the global optimum. The proposed algorithms are appropriate for networks with weak time-dependent connectivity requirements and tight memory constraints. We show how suitable target localization and formation control problems can be tackled via constraints consensus.
On Pebble Automata for Data Languages with Decidable Emptiness Problem
Venue: arXiv cs.FL 2009
Year: 2009

In this paper we study a subclass of pebble automata (PA) for data languages for which the emptiness problem is decidable. Namely, we introduce the so-called top view weak PA. Roughly speaking, top view weak PA are weak PA where the equality test is performed only between the data values seen by the two most recently placed pebbles. The emptiness problem for this model is decidable. We also show that it is robust: alternating, nondeterministic and deterministic top view weak PA have the same recognition power. Moreover, this model is strong enough to accept all data languages expressible in Linear Temporal Logic with the future-time operators, augmented with one register freeze quantifier.
Limits on the Robustness of MIMO Joint Source-Channel Codes
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, the theoretical limits on the robustness of MIMO joint source channel codes is investigated. The case in which a single joint source channel code is used for the entire range of SNRs and for all levels of required fidelity is considered. Limits on the asymptotic performance of such a system are characterized in terms of upper bounds on the diversity-fidelity tradeoff, which can be viewed as an analog version of the diversity-multiplexing tradeoff. In particular, it is shown that there is a considerable gap between the diversity-fidelity tradeoff of robust joint source-channel codes and the optimum tradeoff (without the constraint of robustness).
Impact of Obstacles on the Degree of Mobile Ad Hoc Connection Graphs
Venue: arXiv cs.NI 2009
Year: 2009

What is the impact of obstacles on the graphs of connections between stations in Mobile Ad hoc Networks? In order to answer, at least partially, this question, the first step is to define both an environment with obstacles and a mobility model for the stations in such an environment. The present paper focuses on a new way of considering the mobility within environments with obstacles, while keeping the core ideas of the well-known Random WayPoint mobility model (a.k.a RWP). Based on a mesh-partitioning of the space, we propose a new model called RSP-O-G for which we compute the spatial distribution of stations and analyse how the presence of obstacles impacts this distribution compared to the distribution when no obstacles are present. Coupled with a simple model of radio propagation, and according to the density of stations in the environment, we study the mean degree of the connection graphs corresponding to such mobile ad hoc networks.