OpenRaiser/Intern-Atlas huggingface dataset:
On Tuning the Bad-Character Rule: the Worst-Character Rule
Venue: arXiv cs.DS 2010
Year: 2010

In this note we present the worst-character rule, an efficient variation of the bad-character heuristic for the exact string matching problem, firstly introduced in the well-known Boyer-Moore algorithm. Our proposed rule selects a position relative to the current shift which yields the largest average advancement, according to the characters distribution in the text. Experimental results show that the worst-character rule achieves very good results especially in the case of long patterns or small alphabets in random texts and in the case of texts in natural languages.
Considerate Equilibrium
Venue: arXiv cs.GT 2010
Year: 2010

We consider the existence and computational complexity of coalitional stability concepts based on social networks. Our concepts represent a natural and rich combinatorial generalization of a recent approach termed partition equilibrium. We assume that players in a strategic game are embedded in a social network, and there are coordination constraints that restrict the potential coalitions that can jointly deviate in the game to the set of cliques in the social network. In addition, players act in a "considerate" fashion to ignore potentially profitable (group) deviations if the change in their strategy may cause a decrease of utility to their neighbors. We study the properties of such considerate equilibria in application to the class of resource selection games (RSG). Our main result proves existence of a considerate equilibrium in all symmetric RSG with strictly increasing delays, for any social network among the players. The existence proof is constructive and yields an efficient algorithm. In fact, the computed considerate equilibrium is a Nash equilibrium for the standard RSG showing that there exists a state that is stable against selfish and considerate behavior simultaneously. In addition, we show results on convergence of considerate dynamics.
Bridging the Gap between Reinforcement Learning and Knowledge Representation: A Logical Off- and On-Policy Framework
Venue: arXiv cs.AI 2010
Year: 2010

Knowledge Representation is important issue in reinforcement learning. In this paper, we bridge the gap between reinforcement learning and knowledge representation, by providing a rich knowledge representation framework, based on normal logic programs with answer set semantics, that is capable of solving model-free reinforcement learning problems for more complex do-mains and exploits the domain-specific knowledge. We prove the correctness of our approach. We show that the complexity of finding an offline and online policy for a model-free reinforcement learning problem in our approach is NP-complete. Moreover, we show that any model-free reinforcement learning problem in MDP environment can be encoded as a SAT problem. The importance of that is model-free reinforcement
A Survey on Data Warehouse Evolution
Venue: arXiv cs.DB 2010
Year: 2010

The data warehouse (DW) technology was developed to integrate heterogeneous information sources for analysis purposes. Information sources are more and more autonomous and they often change their content due to perpetual transactions (data changes) and may change their structure due to continual users' requirements evolving (schema changes). Handling properly all type of changes is a must. In fact, the DW which is considered as the core component of the modern decision support systems has to be update according to different type of evolution of information sources to reflect the real world subject to analysis. The goal of this paper is to propose an overview and a comparative study between different works related to the DW evolution problem.
Linked Environment Data for the Life Sciences
Venue: arXiv cs.OH 2010
Year: 2010

Environment Agencies from Europe and the US are setting up a network of Linked Environment Data and are looking to crosslink it with Linked Data contributions from the life sciences.
FreePub: Collecting and Organizing Scientific Material Using Mindmaps
Venue: arXiv cs.HC 2010
Year: 2010

This paper presents a creativity support tool, called FreePub, to collect and organize scientific material using mindmaps. Mindmaps are visual, graph-based represenations of concepts, ideas, notes, tasks, etc. They generally take a hierarchical or tree branch format, with ideas branching into their subsections. FreePub supports creativity cycles. A user starts such a cycle by setting up her domain of interest using mindmaps. Then, she can browse mindmaps and launch search tasks to gather relevant publications from several data sources. FreePub, besides publications, identifies helpful supporting material (e.g., blog posts, presentations). All retrieved information from FreePub can be imported and organized in mindmaps. FreePub has been fully implemented on top of FreeMind, a popular open-source, mindmapping tool.
ChemCloud: Chemical e-Science Information Cloud
Venue: arXiv cs.DB 2010
Year: 2010

Our Chemical e-Science Information Cloud (ChemCloud) - a Semantic Web based eScience infrastructure - integrates and automates a multitude of databases, tools and services in the domain of chemistry, pharmacy and bio-chemistry available at the Fachinformationszentrum Chemie (FIZ Chemie), at the Freie Universitaet Berlin (FUB), and on the public Web. Based on the approach of the W3C Linked Open Data initiative and the W3C Semantic Web technologies for ontologies and rules it semantically links and integrates knowledge from our W3C HCLS knowledge base hosted at the FUB, our multi-domain knowledge base DBpedia (Deutschland) implemented at FUB, which is extracted from Wikipedia (De) providing a public semantic resource for chemistry, and our well-established databases at FIZ Chemie such as ChemInform for organic reaction data, InfoTherm the leading source for thermophysical data, Chemisches Zentralblatt, the complete chemistry knowledge from 1830 to 1969, and ChemgaPedia the largest and most frequented e-Learning platform for Chemistry and related sciences in German language.
A Concept Annotation System for Clinical Records
Venue: arXiv cs.IR 2010
Year: 2010

Unstructured information comprises a valuable source of data in clinical records. For text mining in clinical records, concept extraction is the first step in finding assertions and relationships. This study presents a system developed for the annotation of medical concepts, including medical problems, tests, and treatments, mentioned in clinical records. The system combines six publicly available named entity recognition system into one framework, and uses a simple voting scheme that allows to tune precision and recall of the system to specific needs. The system provides both a web service interface and a UIMA interface which can be easily used by other systems. The system was tested in the fourth i2b2 challenge and achieved an F-score of 82.1% for the concept exact match task, a score which is among the top-ranking systems. To our knowledge, this is the first publicly available clinical record concept annotation system.
Designing Incentive Schemes Based on Intervention: The Case of Perfect Monitoring
Venue: arXiv cs.GT 2010
Year: 2010

This paper studies a class of incentive schemes based on intervention, where there exists an intervention device that is able to monitor the actions of users and to take an action that affects the payoffs of users. We consider the case of perfect monitoring, where the intervention device can immediately observe the actions of users without errors. We also assume that there exist actions of the intervention device that are most and least preferred by all the users and the intervention device, regardless of the actions of users. We derive analytical results about the outcomes achievable with intervention, and illustrate our results with an example based on the Cournot model.
On the Capacity of Memoryless Finite-State Multiple-Access Channels with Asymmetric State Information at the Encoders
Venue: arXiv cs.IT 2010
Year: 2010

A single-letter characterization is provided for the capacity region of finite-state multiple-access channels, when the channel state process is an independent and identically distributed sequence, the transmitters have access to partial (quantized) state information, and complete channel state information is available at the receiver. The partial channel state information is assumed to be asymmetric at the encoders. As a main contribution, a tight converse coding theorem is presented. The difficulties associated with the case when the channel state has memory are discussed and connections to decentralized stochastic control theory are presented.
Sparse motion segmentation using multiple six-point consistencies
Venue: arXiv cs.CV 2010
Year: 2010

We present a method for segmenting an arbitrary number of moving objects in image sequences using the geometry of 6 points in 2D to infer motion consistency. The method has been evaluated on the Hopkins 155 database and surpasses current state-of-the-art methods such as SSC, both in terms of overall performance on two and three motions but also in terms of maximum errors. The method works by finding initial clusters in the spatial domain, and then classifying each remaining point as belonging to the cluster that minimizes a motion consistency score. In contrast to most other motion segmentation methods that are based on an affine camera model, the proposed method is fully projective.
A collective of stateless automata in a $n$-dimensional environment as a distributed dynamic automaton-like object: a model and its corollaries
Venue: arXiv cs.FL 2010
Year: 2010

In this work a collective of interacting stateless automata in a discrete geometric $n$-dimenstional environment is considered as an integral automaton-like computational dynamic object. For such distributed on the environment object different approaches to definition of the measure of state transition are possible. We propose an approach for defining what a state is. The approach is based on the concept of relativity in Poincaré's interpretation.
Conditional coloring of some parameterized graphs
Venue: arXiv cs.DM 2010
Year: 2010

For integers k>0 and r>0, a conditional (k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex v of degree d(v) in G is adjacent to vertices with at least min{r,d(v)} different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is called the rth order conditional chromatic number, denoted by $χ_r(G)$. For different values of r we obtain $χ_r(G)$ of certain parameterized graphs viz., Windmill graph, line graph of Windmill graph, middle graph of Friendship graph, middle graph of a cycle, line graph of Friendship graph, middle graph of complete k-partite graph and middle graph of a bipartite graph.
A year in the life of a large scale experimental distributed system: the Grid'5000 platform in 2008
Venue: arXiv cs.NI 2010
Year: 2010

This report presents the usage results of Grid'5000 over year 2008. Usage of the main operationnal Grid'5000 sites (Bordeaux, Lille, Lyon, Nancy, Orsay, Rennes, Sophia-Antipolis, Toulouse) is presented and analyzed.
Covering Cubes and the Closest Vector Problem
Venue: arXiv cs.DS 2010
Year: 2010

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest vector problem in the infinity norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2^O(n) (log 1/epsilon)^O(n)$ which improves upon the (2+1/epsilon)^O(n) running time of the previously best algorithm by Blömer and Naewe. Our algorithm is based on a solution of the following geometric covering problem that is of interest of its own: Given epsilon in (0,1), how many ellipsoids are necessary to cover the cube [-1+epsilon, 1-epsilon]^n such that all ellipsoids are contained in the standard unit cube [-1,1]^n? We provide an almost optimal bound for the case where the ellipsoids are restricted to be axis-parallel. We then apply our covering scheme to a variation of this covering problem where one wants to cover [-1+epsilon,1-epsilon]^n with parallelepipeds that, if scaled by two, are still contained in the unit cube. Thereby, we obtain a method to boost any 2-approximation algorithm for closest-vector in the infinity norm to a (1+epsilon)-approximation algorithm that has the desired running time.
Aligned Interference Neutralization and the Degrees of Freedom of the 2x2x2 Interference Channel
Venue: arXiv cs.IT 2010
Year: 2010

We show that the 2x2x2 interference channel, i.e., the multihop interference channel formed by concatenation of two 2-user interference channels achieves the min-cut outer bound value of 2 DoF, for almost all values of channel coefficients, for both time-varying or fixed channel coefficients. The key to this result is a new idea, called aligned interference neutralization, that provides a way to align interference terms over each hop in a manner that allows them to be cancelled over the air at the last hop.
NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets
Venue: arXiv cs.CC 2010
Year: 2010

A long standing open problem in the computational complexity theory is to separate NE from BPP, which is a subclass of $NP_T(NP\cap P/poly)$. In this paper, we show that $NE\not\subseteq NP_(NP \cap$ Nonexponentially-Dense-Class), where Nonexponentially-Dense-Class is the class of languages A without exponential density (for each constant c>0,$|A^{\le n}|\le 2^{n^c}$ for infinitely many integers n). Our result implies $NE\not\subseteq NP_T({pad(NP, g(n))})$ for every time constructible super-polynomial function g(n) such as $g(n)=n^{\ceiling{\log\ceiling{\log n}}}$, where Pad(NP, g(n)) is class of all languages $L_B=\{s10^{g(|s|)-|s|-1}:s\in B\}$ for $B\in NP$. We also show $NE\not\subseteq NP_T(P_{tt}(NP)\cap Tally)$.
Nonadaptive Mastermind Algorithms for String and Vector Databases, with Case Studies
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we study sparsity-exploiting Mastermind algorithms for attacking the privacy of an entire database of character strings or vectors, such as DNA strings, movie ratings, or social network friendship data. Based on reductions to nonadaptive group testing, our methods are able to take advantage of minimal amounts of privacy leakage, such as contained in a single bit that indicates if two people in a medical database have any common genetic mutations, or if two people have any common friends in an online social network. We analyze our Mastermind attack algorithms using theoretical characterizations that provide sublinear bounds on the number of queries needed to clone the database, as well as experimental tests on genomic information, collaborative filtering data, and online social networks. By taking advantage of the generally sparse nature of these real-world databases and modulating a parameter that controls query sparsity, we demonstrate that relatively few nonadaptive queries are needed to recover a large majority of each database.
A Secure Aggregation Protocol for Wireless Sensor Networks
Venue: arXiv cs.CR 2010
Year: 2010

The purpose of a wireless sensor network (WSN) is to provide the users with access to the information of interest from data gathered by spatially distributed sensors. Generally the users require only certain aggregate functions of this distributed data. Computation of this aggregate data under the end-to-end information flow paradigm by communicating all the relevant data to a central collector node is a highly inefficient solution for this purpose. An alternative proposition is to perform in-network computation. This, however, raises questions such as: what is the optimal way to compute an aggregate function from a set of statistically correlated values stored in different nodes; what is the security of such aggregation as the results sent by a compromised or faulty node in the network can adversely affect the accuracy of the computed result. In this paper, we have presented an energy-efficient aggregation algorithm for WSNs that is secure and robust against malicious insider attack by any compromised or faulty node in the network. In contrast to the traditional snapshot aggregation approach in WSNs, a node in the proposed algorithm instead of unicasting its sensed information to its parent node, broadcasts its estimate to all its neighbors. This makes the system more fault-tolerant and increase the information availability in the network. The simulations conducted on the proposed algorithm have produced results that demonstrate its effectiveness.
Study of Throughput and Latency in Finite-buffer Coded Networks
Venue: arXiv cs.IT 2010
Year: 2010

Exact queueing analysis of erasure networks with network coding in a finite buffer regime is an extremely hard problem due to the large number of states in the network. In such networks, packets are lost due to either link erasures or due to blocking due to full buffers. In this paper, a block-by-block random linear network coding scheme with feedback on the links is selected for reliability and more importantly guaranteed decoding of each block. We propose a novel method that iteratively estimates the performance parameters of the network and more importantly reduces the computational complexity compared to the exact analysis. The proposed framework yields an accurate estimate of the distribution of buffer occupancies at the intermediate nodes using which we obtain analytical expressions for network throughput and delay distribution of a block of packets.
Distributed XML Design
Venue: arXiv cs.DB 2010
Year: 2010

A distributed XML document is an XML document that spans several machines. We assume that a distribution design of the document tree is given, consisting of an XML kernel-document T[f1,...,fn] where some leaves are "docking points" for external resources providing XML subtrees (f1,...,fn, standing, e.g., for Web services or peers at remote locations). The top-down design problem consists in, given a type (a schema document that may vary from a DTD to a tree automaton) for the distributed document, "propagating" locally this type into a collection of types, that we call typing, while preserving desirable properties. We also consider the bottom-up design which consists in, given a type for each external resource, exhibiting a global type that is enforced by the local types, again with natural desirable properties. In the article, we lay out the fundamentals of a theory of distributed XML design, analyze problems concerning typing issues in this setting, and study their complexity.
Categorial Minimalist Grammar
Venue: arXiv cs.CL 2010
Year: 2010

We first recall some basic notions on minimalist grammars and on categorial grammars. Next we shortly introduce partially commutative linear logic, and our representation of minimalist grammars within this categorial system, the so-called categorial minimalist grammars. Thereafter we briefly present λμ-DRT (Discourse Representation Theory) an extension of λ-DRT (compositional DRT) in the framework of λμcalculus: it avoids type raising and derives different readings from a single semantic representation, in a setting which follows discourse structure. We run a complete example which illustrates the various structures and rules that are needed to derive a semantic representation from the categorial view of a transformational syntactic analysis.
Dense locally testable codes cannot have constant rate and distance
Venue: arXiv cs.CC 2010
Year: 2010

A q-query locally testable code (LTC) is an error correcting code that can be tested by a randomized algorithm that reads at most q symbols from the given word. An important question is whether there exist LTCs that have the ccc-property: constant relative rate, constant relative distance, and that can be tested with a constant number of queries. Such codes are sometimes referred to as "asymptotically good". We show that dense LTCs cannot be ccc. The density of a tester is roughly the average number of distinct local views in which a coordinate participates. An LTC is dense if it has a tester with density >> 1. More precisely, we show that a 3-query locally testable code with a tester of density >> 1 cannot be ccc. Moreover, we show that a q-query locally testable code (q>3) with a tester of density >> n^{q-2} cannot be ccc. Our results hold when the tester has the following two properties: 1) "no weights": Every q-tuple of queries occurs with the same probability. 2) "last-one-fixed": In every `test' of the tester, the value to any q-1 of the symbols determines the value of the last symbol. (Linear codes have constraints of this type). We also show that several natural ways to quantitatively improve our results would already resolve the general ccc-question, i.e. also for non-dense LTCs.
Symmetry invariance for adapting biological systems
Venue: arXiv cs.SY 2010
Year: 2010

We study in this paper certain properties of the responses of dynamical systems to external inputs. The motivation arises from molecular systems biology. and, in particular, the recent discovery of an important transient property, related to Weber's law in psychophysics: "fold-change detection" in adapting systems, the property that scale uncertainty does not affect responses. FCD appears to play an important role in key signaling transduction mechanisms in eukaryotes, including the ERK and Wnt pathways, as well as in E.coli and possibly other prokaryotic chemotaxis pathways. In this paper, we provide further theoretical results regarding this property. Far more generally, we develop a necessary and sufficient characterization of adapting systems whose transient behaviors are invariant under the action of a set (often, a group) of symmetries in their sensory field. A particular instance is FCD, which amounts to invariance under the action of the multiplicative group of positive real numbers. Our main result is framed in terms of a notion which extends equivariant actions of compact Lie groups. Its proof relies upon control theoretic tools, and in particular the uniqueness theorem for minimal realizations.
Comparison of Planar Parallel Manipulator Architectures based on a Multi-objective Design Optimization Approach
Venue: arXiv cs.RO 2010
Year: 2010

This paper deals with the comparison of planar parallel manipulator architectures based on a multi-objective design optimization approach. The manipulator architectures are compared with regard to their mass in motion and their regular workspace size, i.e., the objective functions. The optimization problem is subject to constraints on the manipulator dexterity and stiffness. For a given external wrench, the displacements of the moving platform have to be smaller than given values throughout the obtained maximum regular dexterous workspace. The contributions of the paper are highlighted with the study of 3-RPR, 3-RPR and 3-RPR planar parallel manipulator architectures, which are compared by means of their Pareto frontiers obtained with a genetic algorithm.
Should Corpora be Big, Rich, or Dense?
Venue: arXiv cs.SD 2010
Year: 2010

In this paper, we ask what properties makes a large corpus more or less useful. We suggest that size, by itself, should not be the ultimate goal of building a corpus. Large-scale corpora are considered desirable because they offer statistical stability and rich variation. But this rich variation means more factors to control and evaluate, which can limit the advantages of size. We discuss the use of multi-channel data to complement large-scale speech corpora. Even though multi-channel data may limit the scale of a corpus (due to the complex and labor-intensive nature of data collection) they can offer information that allows us to tease apart various factors related to speech production.