OpenRaiser/Intern-Atlas huggingface dataset:
A Testing Framework for P Systems
Venue: arXiv cs.LO 2011
Year: 2011

Testing equivalence was originally defined by De Nicola and Hennessy in a process algebraic setting (CCS) with the aim of defining an equivalence relation between processes being less discriminating than bisimulation and with a natural interpretation in the practice of system development. Finite characterizations of the defined preorders and relations led to the possibility of verification by comparing an implementation with a specification in a setting where systems were seen as black boxes with input and output capabilities, thus neglecting internal undetectable behaviours. In this paper, we start defining a porting of the well-established testing theory into membrane computing, in order to investigate possible benefits in terms of inherited analysis/verification techniques and interesting biological applications. P Algebra, a process algebra for describing P Systems, is used as a natural candidate for the porting since it enjoys the desirable property of being compositional and comes with other observational equivalences already defined and studied.
Multiscale Modelling: A Mobile Membrane Approach
Venue: arXiv cs.FL 2011
Year: 2011

Nowadays, multiscale modelling is recognized as the most suitable way to study biological processes. Indeed, almost every phenomenon in nature exhibits a multiscale behaviour, i.e., it is the outcome of interactions that occur at different spatial and temporal scales. Although several ways to provide "multilayer" models have been proposed, only Complex Automata naturally embed spatial information and realize the multiscale approach with well-established inter-scale integration schemas. Recently, such approach has been restated in terms of Spatial P systems - a variant of P systems with a more geometric concept of space. In this work we discuss how mobile membranes, a variant of membrane systems inspired by the biological movements of endocytosis and exocytosis, can be efficaciously exploited to define a uniform multiscale coupling scheme relying only on the features of the formalism itself.
Hamiltonian Streamline Guided Feature Extraction with Applications to Face Detection
Venue: arXiv cs.CV 2011
Year: 2011

We propose a new feature extraction method based on two dynamical systems induced by intensity landscape: the negative gradient system and the Hamiltonian system. We build features based on the Hamiltonian streamlines. These features contain nice global topological information about the intensity landscape, and can be used for object detection. We show that for training images of same size, our feature space is much smaller than that generated by Haar-like features. The training time is extremely short, and detection speed and accuracy is similar to Haar-like feature based classifiers.
Applications of Zigzag Persistence to Topological Data Analysis
Venue: arXiv cs.CG 2011
Year: 2011

The theory of zigzag persistence is a substantial extension of persistent homology, and its development has enabled the investigation of several unexplored avenues in the area of topological data analysis. In this paper, we discuss three applications of zigzag persistence: topological bootstrapping, parameter thresholding, and the comparison of witness complexes.
Circular words and applications
Venue: arXiv cs.FL 2011
Year: 2011

We define the notion of circular words, then consider on such words a constraint derived from the Fibonacci condition. We give several results on the structure of these circular words, then mention possible applications to various situations: periodic expansion of numbers in numeration systems, "gcd-property" of integer sequences, partition of the prefix of the fixed point of the Fibonacci substitution, spanning trees of a wheel. Eventually, we mention some open questions.
Uniformly balanced words with linear complexity and prescribed letter frequencies
Venue: arXiv cs.FL 2011
Year: 2011

We consider the following problem. Let us fix a finite alphabet A; for any given d-uple of letter frequencies, how to construct an infinite word u over the alphabet A satisfying the following conditions: u has linear complexity function, u is uniformly balanced, the letter frequencies in u are given by the given d-uple. This paper investigates a construction method for such words based on the use of mixed multidimensional continued fraction algorithms.
Recurrent Partial Words
Venue: arXiv cs.DM 2011
Year: 2011

Partial words are sequences over a finite alphabet that may contain wildcard symbols, called holes, which match or are compatible with all letters; partial words without holes are said to be full words (or simply words). Given an infinite partial word w, the number of distinct full words over the alphabet that are compatible with factors of w of length n, called subwords of w, refers to a measure of complexity of infinite partial words so-called subword complexity. This measure is of particular interest because we can construct partial words with subword complexities not achievable by full words. In this paper, we consider the notion of recurrence over infinite partial words, that is, we study whether all of the finite subwords of a given infinite partial word appear infinitely often, and we establish connections between subword complexity and recurrence in this more general framework.
From Regular to Strictly Locally Testable Languages
Venue: arXiv cs.FL 2011
Year: 2011

A classical result (often credited to Y. Medvedev) states that every language recognized by a finite automaton is the homomorphic image of a local language, over a much larger so-called local alphabet, namely the alphabet of the edges of the transition graph. Local languages are characterized by the value k=2 of the sliding window width in the McNaughton and Papert's infinite hierarchy of strictly locally testable languages (k-slt). We generalize Medvedev's result in a new direction, studying the relationship between the width and the alphabetic ratio telling how much larger the local alphabet is. We prove that every regular language is the image of a k-slt language on an alphabet of doubled size, where the width logarithmically depends on the automaton size, and we exhibit regular languages for which any smaller alphabetic ratio is insufficient. More generally, we express the trade-off between alphabetic ratio and width as a mathematical relation derived from a careful encoding of the states. At last we mention some directions for theoretical development and application.
Constructing Premaximal Binary Cube-free Words of Any Level
Venue: arXiv cs.FL 2011
Year: 2011

We study the structure of the language of binary cube-free words. Namely, we are interested in the cube-free words that cannot be infinitely extended preserving cube-freeness. We show the existence of such words with arbitrarily long finite extensions, both to one side and to both sides.
Coordination using Implicit Communication
Venue: arXiv cs.IT 2011
Year: 2011

We explore a basic noise-free signaling scenario where coordination and communication are naturally merged. A random signal X_1,...,X_n is processed to produce a control signal or action sequence A_1,...,A_n, which is observed and further processed (without access to X_1,...,X_n) to produce a third sequence B_1,...,B_n. The object of interest is the set of empirical joint distributions p(x,a,b) that can be achieved in this setting. We show that H(A) >= I(X;A,B) is the necessary and sufficient condition for achieving p(x,a,b) when no causality constraints are enforced on the encoders. We also give results for various causality constraints. This setting sheds light on the embedding of digital information in analog signals, a concept that is exploited in digital watermarking, steganography, cooperative communication, and strategic play in team games such as bridge.
Substring Range Reporting
Venue: arXiv cs.DS 2011
Year: 2011

We revisit various string indexing problems with range reporting features, namely, position-restricted substring searching, indexing substrings with gaps, and indexing substrings with intervals. We obtain the following main results. {itemize} We give efficient reductions for each of the above problems to a new problem, which we call \emph{substring range reporting}. Hence, we unify the previous work by showing that we may restrict our attention to a single problem rather than studying each of the above problems individually. We show how to solve substring range reporting with optimal query time and little space. Combined with our reductions this leads to significantly improved time-space trade-offs for the above problems. In particular, for each problem we obtain the first solutions with optimal time query and $O(n\log^{O(1)} n)$ space, where $n$ is the length of the indexed string. We show that our techniques for substring range reporting generalize to \emph{substring range counting} and \emph{substring range emptiness} variants. We also obtain non-trivial time-space trade-offs for these problems. {itemize} Our bounds for substring range reporting are based on a novel combination of suffix trees and range reporting data structures. The reductions are simple and general and may apply to other combinations of string indexing with range reporting.
Policy Iteration is well suited to optimize PageRank
Venue: arXiv cs.GT 2011
Year: 2011

The question of knowing whether the policy Iteration algorithm (PI) for solving Markov Decision Processes (MDPs) has exponential or (strongly) polynomial complexity has attracted much attention in the last 50 years. Recently, Fearnley proposed an example on which PI needs an exponential number of iterations to converge. Though, it has been observed that Fearnley's example leaves open the possibility that PI behaves well in many particular cases, such as in problems that involve a fixed discount factor, or that are restricted to deterministic actions. In this paper, we analyze a large class of MDPs and we argue that PI is efficient in that case. The problems in this class are obtained when optimizing the PageRank of a particular node in the Markov chain. They are motivated by several practical applications. We show that adding natural constraints to this PageRank Optimization problem (PRO) makes it equivalent to the problem of optimizing the length of a stochastic path, which is a widely studied family of MDPs. Finally, we conjecture that PI runs in a polynomial number of iterations when applied to PRO. We give numerical arguments as well as the proof of our conjecture in a number of particular cases of practical importance.
Exact Regenerating Codes for Byzantine Fault Tolerance in Distributed Storage
Venue: arXiv cs.IT 2011
Year: 2011

Due to the use of commodity software and hardware, crash-stop and Byzantine failures are likely to be more prevalent in today's large-scale distributed storage systems. Regenerating codes have been shown to be a more efficient way to disperse information across multiple nodes and recover crash-stop failures in the literature. In this paper, we present the design of regeneration codes in conjunction with integrity check that allows exact regeneration of failed nodes and data reconstruction in presence of Byzantine failures. A progressive decoding mechanism is incorporated in both procedures to leverage computation performed thus far. The fault-tolerance and security properties of the schemes are also analyzed.
Backpressure with Adaptive Redundancy (BWAR)
Venue: arXiv cs.NI 2011
Year: 2011

Backpressure scheduling and routing, in which packets are preferentially transmitted over links with high queue differentials, offers the promise of throughput-optimal operation for a wide range of communication networks. However, when the traffic load is low, due to the corresponding low queue occupancy, backpressure scheduling/routing experiences long delays. This is particularly of concern in intermittent encounter-based mobile networks which are already delay-limited due to the sparse and highly dynamic network connectivity. While state of the art mechanisms for such networks have proposed the use of redundant transmissions to improve delay, they do not work well when the traffic load is high. We propose in this paper a novel hybrid approach that we refer to as backpressure with adaptive redundancy (BWAR), which provides the best of both worlds. This approach is highly robust and distributed and does not require any prior knowledge of network load conditions. We evaluate BWAR through both mathematical analysis and simulations based on cell-partitioned model. We prove theoretically that BWAR does not perform worse than traditional backpressure in terms of the maximum throughput, while yielding a better delay bound. The simulations confirm that BWAR outperforms traditional backpressure at low load, while outperforming a state of the art encounter-routing scheme (Spray and Wait) at high load.
Convergence Properties of Two (μ + λ) Evolutionary Algorithms On OneMax and Royal Roads Test Functions
Venue: arXiv cs.NE 2011
Year: 2011

We present a number of bounds on convergence time for two elitist population-based Evolutionary Algorithms using a recombination operator k-Bit-Swap and a mainstream Randomized Local Search algorithm. We study the effect of distribution of elite species and population size.
A Deterministic Equivalent for the Analysis of Non-Gaussian Correlated MIMO Multiple Access Channels
Venue: arXiv cs.IT 2011
Year: 2011

Large dimensional random matrix theory (RMT) has provided an efficient analytical tool to understand multiple-input multiple-output (MIMO) channels and to aid the design of MIMO wireless communication systems. However, previous studies based on large dimensional RMT rely on the assumption that the transmit correlation matrix is diagonal or the propagation channel matrix is Gaussian. There is an increasing interest in the channels where the transmit correlation matrices are generally nonnegative definite and the channel entries are non-Gaussian. This class of channel models appears in several applications in MIMO multiple access systems, such as small cell networks (SCNs). To address these problems, we use the generalized Lindeberg principle to show that the Stieltjes transforms of this class of random matrices with Gaussian or non-Gaussian independent entries coincide in the large dimensional regime. This result permits to derive the deterministic equivalents (e.g., the Stieltjes transform and the ergodic mutual information) for non-Gaussian MIMO channels from the known results developed for Gaussian MIMO channels, and is of great importance in characterizing the spectral efficiency of SCNs.
A New Enforcement on Declassification with Reachability Analysis
Venue: arXiv cs.CR 2011
Year: 2011

Language-based information flow security aims to decide whether an action-observable program can unintentionally leak confidential information if it has the authority to access confidential data. Recent concerns about declassification polices have provided many choices for practical intended information release, but more precise enforcement mechanism for these policies is insufficiently studied. In this paper, we propose a security property on the where-dimension of declassification and present an enforcement based on automated verification. The approach automatically transforms the abstract model with a variant of self-composition, and checks the reachability of illegal-flow state of the model after transformation. The self-composition is equipped with a store-match pattern to reduce the state space and to model the equivalence of declassified expressions in the premise of property. The evaluation shows that our approach is more precise than type-based enforcement.
Biomimetic use of genetic algorithms
Venue: arXiv cs.AI 2011
Year: 2011

Genetic algorithms are considered as an original way to solve problems, probably because of their generality and of their "blind" nature. But GAs are also unusual since the features of many implementations (among all that could be thought of) are principally led by the biological metaphor, while efficiency measurements intervene only afterwards. We propose here to examine the relevance of these biomimetic aspects, by pointing out some fundamental similarities and divergences between GAs and the genome of living beings shaped by natural selection. One of the main differences comes from the fact that GAs rely principally on the so-called implicit parallelism, while giving to the mutation/selection mechanism the second role. Such differences could suggest new ways of employing GAs on complex problems, using complex codings and starting from nearly homogeneous populations.
A Dynamical Systems Approach for Static Evaluation in Go
Venue: arXiv cs.AI 2011
Year: 2011

In the paper arguments are given why the concept of static evaluation has the potential to be a useful extension to Monte Carlo tree search. A new concept of modeling static evaluation through a dynamical system is introduced and strengths and weaknesses are discussed. The general suitability of this approach is demonstrated.
Research on Wireless Multi-hop Networks: Current State and Challenges
Venue: arXiv cs.NI 2011
Year: 2011

Wireless multi-hop networks, in various forms and under various names, are being increasingly used in military and civilian applications. Studying connectivity and capacity of these networks is an important problem. The scaling behavior of connectivity and capacity when the network becomes sufficiently large is of particular interest. In this position paper, we briefly overview recent development and discuss research challenges and opportunities in the area, with a focus on the network connectivity.
Manipulation Can Be Hard in Tractable Voting Systems Even for Constant-Sized Coalitions
Venue: arXiv cs.GT 2011
Year: 2011

Voting theory has become increasingly integrated with computational social choice and multiagent systems. Computational complexity has been extensively used as a shield against manipulation of voting systems, however for several voting schemes this complexity may cause calculating the winner to be computationally difficult. Of the many voting systems that have been studied with regard to election manipulation, a few have been found to have an unweighted coalitional manipulation problem that is NP-hard for a constant number of manipulators despite having a winner problem that is in P. We survey this interesting class of voting systems and the work that has analyzed their complexity.
SNF Project Locomotion: Progress report 2008-2009
Venue: arXiv cs.RO 2011
Year: 2011

Summary of results (project period 1. 10. 2008 - 30. 9. 2009) of SNFS Project "From locomotion to cognition" The research that we have been involved in, and will continue to do, starts from the insight that in order to understand and design intelligent behavior, we must adopt an embodied perspective, i.e. we must take the entire agent, including its shape or morphology, the materials out of which it is built, and its interaction with the environment into account, in addition to the neural control. A lot of our research in the past has been on relatively low-level sensory-motor tasks such as locomotion (e.g. walking, running, jumping), navigation, and grasping. While this research is of interest in itself, in the context of artificial intelligence and cognitive science, this leads to the question of what these kinds of tasks have to do with higher levels of cognition, or to put it more provocatively, "What does walking have to do with thinking?" This question is of course reminiscent of the notorious "symbol grounding problem". In contrast to most of the research on symbol grounding, we propose to exploit the dynamic interaction between the embodied agent and the environment as the basis for grounding. We use the term "morphological computation" to designate the fact that some of the control or computation can be taken over by the dynamic interaction derived from morphological properties (e.g. the passive forward swing of the leg in walking, the spring-like properties of the muscles, and the weight distribution). By taking morphological computation into account, an agent will be able to achieve not only faster, more robust, and more energy-efficient behavior, but also more situated exploration by the agent for the comprehensive understanding of the environment.
The fuzzy gene filter: A classifier performance assesment
Venue: arXiv cs.LG 2011
Year: 2011

The Fuzzy Gene Filter (FGF) is an optimised Fuzzy Inference System designed to rank genes in order of differential expression, based on expression data generated in a microarray experiment. This paper examines the effectiveness of the FGF for feature selection using various classification architectures. The FGF is compared to three of the most common gene ranking algorithms: t-test, Wilcoxon test and ROC curve analysis. Four classification schemes are used to compare the performance of the FGF vis-a-vis the standard approaches: K Nearest Neighbour (KNN), Support Vector Machine (SVM), Naive Bayesian Classifier (NBC) and Artificial Neural Network (ANN). A nested stratified Leave-One-Out Cross Validation scheme is used to identify the optimal number top ranking genes, as well as the optimal classifier parameters. Two microarray data sets are used for the comparison: a prostate cancer data set and a lymphoma data set.
XML content warehousing: Improving sociological studies of mailing lists and web data
Venue: arXiv cs.DB 2011
Year: 2011

In this paper, we present the guidelines for an XML-based approach for the sociological study of Web data such as the analysis of mailing lists or databases available online. The use of an XML warehouse is a flexible solution for storing and processing this kind of data. We propose an implemented solution and show possible applications with our case study of profiles of experts involved in W3C standard-setting activity. We illustrate the sociological use of semi-structured databases by presenting our XML Schema for mailing-list warehousing. An XML Schema allows many adjunctions or crossings of data sources, without modifying existing data sets, while allowing possible structural evolution. We also show that the existence of hidden data implies increased complexity for traditional SQL users. XML content warehousing allows altogether exhaustive warehousing and recursive queries through contents, with far less dependence on the initial storage. We finally present the possibility of exporting the data stored in the warehouse to commonly-used advanced software devoted to sociological analysis.
Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Short)
Venue: arXiv cs.SI 2011
Year: 2011

A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad-hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon.