OpenRaiser/Intern-Atlas huggingface dataset:
A Partial Taxonomy of Substitutability and Interchangeability
Venue: arXiv cs.AI 2010
Year: 2010

Substitutability, interchangeability and related concepts in Constraint Programming were introduced approximately twenty years ago and have given rise to considerable subsequent research. We survey this work, classify, and relate the different concepts, and indicate directions for future work, in particular with respect to making connections with research into symmetry breaking. This paper is a condensed version of a larger work in progress.
Navigating the Topology of 2x2 Games: An Introductory Note on Payoff Families, Normalization, and Natural Order
Venue: arXiv cs.GT 2010
Year: 2010

The Robinson-Goforth topology of swaps in adjoining payoffs elegantly arranges 2x2 ordinal games in accordance with important properties including symmetry, number of dominant strategies and Nash Equilibria, and alignment of interests. Adding payoff families based on Nash Equilibria illustrates an additional aspect of this order and aids visualization of the topology. Making ties through half-swaps not only creates simpler games within the topology, but, in reverse, breaking ties shows the evolution of preferences, yielding a natural ordering for the topology of 2x2 games with ties. An ordinal game not only represents an equivalence class of games with real values, but also a discrete equivalent of the normalized version of those games. The topology provides coordinates which could be used to identify related games in a semantic web ontology and facilitate comparative analysis of agent-based simulations and other research in game theory, as well as charting relationships and potential moves between games as a tool for institutional analysis and design.
Learning under Concept Drift: an Overview
Venue: arXiv cs.AI 2010
Year: 2010

Concept drift refers to a non stationary learning problem over time. The training and the application data often mismatch in real life problems. In this report we present a context of concept drift problem 1. We focus on the issues relevant to adaptive training set formation. We present the framework and terminology, and formulate a global picture of concept drift learners design. We start with formalizing the framework for the concept drifting data in Section 1. In Section 2 we discuss the adaptivity mechanisms of the concept drift learners. In Section 3 we overview the principle mechanisms of concept drift learners. In this chapter we give a general picture of the available algorithms and categorize them based on their properties. Section 5 discusses the related research fields and Section 5 groups and presents major concept drift applications. This report is intended to give a bird's view of concept drift research field, provide a context of the research and position it within broad spectrum of research fields and applications.
S-MATE: Secure Coding-based Multipath Adaptive Traffic Engineering
Venue: arXiv cs.NI 2010
Year: 2010

There have been several approaches to provisioning traffic between core network nodes in Internet Service Provider (ISP) networks. Such approaches aim to minimize network delay, increase network capacity, and enhance network security services. MATE (Multipath Adaptive Traffic Engineering) protocol has been proposed for multipath adaptive traffic engineering between an ingress node (source) and an egress node (destination). Its novel idea is to avoid network congestion and attacks that might exist in edge and node disjoint paths between two core network nodes. This paper builds an adaptive, robust, and reliable traffic engineering scheme for better performance of communication network operations. This will also provision quality of service (QoS) and protection of traffic engineering to maximize network efficiency. Specifically, we present a new approach, S-MATE (secure MATE) is developed to protect the network traffic between two core nodes (routers or switches) in a cloud network. S-MATE secures against a single link attack/failure by adding redundancy in one of the operational paths between the sender and receiver. The proposed scheme can be built to secure core networks such as optical and IP networks.
A Unified Framework for Testing Linear-Invariant Properties
Venue: arXiv cs.DS 2010
Year: 2010

The study of the interplay between the testability of properties of Boolean functions and the invariances acting on their domain which preserve the property was initiated by Kaufman and Sudan (STOC 2008). Invariance with respect to F_2-linear transformations is arguably the most common symmetry exhibited by natural properties of Boolean functions on the hypercube. Hence, an important goal in Property Testing is to describe necessary and sufficient conditions for the testability of linear-invariant properties. This direction was explicitly proposed for investigation in a recent survey of Sudan. We obtain the following results: 1. We show that every linear-invariant property that can be characterized by forbidding induced solutions to a (possibly infinite) set of linear equations can be tested with one-sided error. 2. We show that every linear-invariant property that can be tested with one-sided error can be characterized by forbidding induced solutions to a (possibly infinite) set of systems of linear equations. We conjecture that our result from item (1) can be extended to cover systems of linear equations. We further show that the validity of this conjecture would have the following implications: 1. It would imply that every linear-invariant property that is closed under restrictions to linear subspaces is testable with one-sided error. Such a result would unify several previous results on testing Boolean functions, such as the testability of low-degree polynomials and of Fourier dimensionality. 2. It would imply that a linear-invariant property P is testable with one-sided error if and only if P is closed under restrictions to linear subspaces, thus resolving Sudan's problem.
Yacc is dead
Venue: arXiv cs.PL 2010
Year: 2010

We present two novel approaches to parsing context-free languages. The first approach is based on an extension of Brzozowski's derivative from regular expressions to context-free grammars. The second approach is based on a generalization of the derivative to parser combinators. The payoff of these techniques is a small (less than 250 lines of code), easy-to-implement parsing library capable of parsing arbitrary context-free grammars into lazy parse forests. Implementations for both Scala and Haskell are provided. Preliminary experiments with S-Expressions parsed millions of tokens per second, which suggests this technique is efficient enough for use in practice.
Coarse-Grained Analysis of Microscopic Neuronal Simulators on Networks: Bifurcation and Rare-events computations
Venue: arXiv cs.SI 2010
Year: 2010

We show how the Equation-Free approach for mutliscale computations can be exploited to extract, in a computational strict and systematic way the emergent dynamical attributes, from detailed large-scale microscopic stochastic models, of neurons that interact on complex networks. In particular we show how the Equation-Free approach can be exploited to perform system-level tasks such as bifurcation, stability analysis and estimation of mean appearance times of rare events, bypassing the need for obtaining analytical approximations, providing an "on-demand" model reduction. Using the detailed simulator as a black-box timestepper, we compute the coarse-grained equilibrium bifurcation diagrams, examine the stability of the solution branches and perform a rare-events analysis with respect to certain characteristics of the underlying network topology such as the connectivity degree
Minimization of Automata
Venue: arXiv cs.FL 2010
Year: 2010

This chapter is concerned with the design and analysis of algorithms for minimizing finite automata. Getting a minimal automaton is a fundamental issue in the use and implementation of finite automata tools in frameworks like text processing, image analysis, linguistic computer science, and many other applications. There are two main families of minimization algorithms. The first by a sequence of refinements of a partition of the set of states, the second by a sequence of fusions or merges of states. Hopcroft's and Moore's algorithms belong to the first family, the linear-time minimization of acyclic automata of Revuz belongs to the second family. One of our studies is upon the comparison of the nature of Moore's and Hopcroft's algorithms. This gives some new insight in both algorithms. As we shall see, these algorithms are quite different both in behavior and in complexity. In particular, we show that it is not possible to simulate the computations of one of the algorithm by the other. We describe the minimization algorithm by fusion for so-called local automata. A special case of minimization is the construction o minimal automata for finite sets. We consider briefly this case, and in particular describe incremental algorithms. Finally, we consider the case of updating a minimal automaton when a word is added or removed from the set it recognizes.
Helstrom's Theory on Quantum Binary Decision Revisited
Venue: arXiv cs.IT 2010
Year: 2010

For a binary system specified by the density operators r0 and r1 and by the prior probabilities q0 and q1, Helstrom's theory permits the evaluation of the optimal measurement operators and of the corresponding maximum correct detection probability. The theory is based on the eigendecomposition (EID) of the operator, given by the difference of the weighted density operators, namely D = q1r1-q0r0. In general, this EID is obtained explicitly only with pure states, whereas with mixed states it must be carried out numerically. In this letter we show that the same evaluation can be performed on the basis of a modified version of the Gram matrix. The advantage is due to the fact that the outer products of density operators are replaced by inner product, with a considerable dimensionality reduction. At the limit, in quantum optical communications the density operators have infinite dimensions, whereas the inner products are simply scalar quantities. The Gram matrix approach permits the explicit (not numerical) evaluation of a binary system performance in cases not previously developed.
Achieving near-Capacity on Large Discrete Memoryless Channels
Venue: arXiv cs.IT 2010
Year: 2010

We propose a method to increase the capacity achieved by uniform prior in discrete memoryless channels (DMC) with high input cardinality. It consists in appropriately reducing the input set. Different design criteria of the input subset are discussed. We develop an efficient algorithm to solve this problem based on the maximization of the cut-off rate. The method is applied to a mono-bit transceiver MIMO system, and it is shown that the capacity can be approached within tenths of a dB by employing standard binary codes while avoiding the use of distribution shapers.
A Generalized Coupon Collector Problem
Venue: arXiv cs.IT 2010
Year: 2010

This paper provides analysis to a generalized version of the coupon collector problem, in which the collector gets $d$ distinct coupons each run and she chooses the one that she has the least so far. On the asymptotic case when the number of coupons $n$ goes to infinity, we show that on average $\frac{n\log n}{d} + \frac{n}{d}(m-1)\log\log{n}+O(mn)$ runs are needed to collect $m$ sets of coupons. An efficient exact algorithm is also developed for any finite case to compute the average needed runs exactly. Numerical examples are provided to verify our theoretical predictions.
Rethinking low extra delay background transport protocols
Venue: arXiv cs.NI 2010
Year: 2010

BitTorrent has recently introduced LEDBAT, a novel application-layer congestion control protocol for data exchange. The protocol design starts from the assumption that network bottlenecks are at the access of the network, and that thus user traffic competes creating self-inducing congestion. To relieve from this phenomenon, LEDBAT is designed to quickly infer that self-induced congestion is approaching (by detecting relative changes of the one-way delay in the transmission path), and to react by reducing the sending rate prior that congestion occurs. Prior work has however shown LEDBAT to be affected by a latecomer advantage, where newly arriving connections can starve already existing flows. In this work, we propose modifications to the congestion window update mechanism of the LEDBAT protocol that aim at solving this issue, guaranteeing thus intra-protocol fairness and efficiency. Closed-form expressions for the stationary throughput and queue occupancy are provided via a fluid model, whose accuracy is confirmed by means of ns2 packet level simulations. Our results show that the proposed change can effective solve the latecomer issue, without affecting the other original LEDBAT goals at the same time.
Privacy-Preserving English Auction Protocol with Round Efficiency
Venue: arXiv cs.GT 2010
Year: 2010

A privacy-preserving English auction protocol with round efficiency based on a modified ring signature has been proposed in this paper. The proposed protocol has three appealing characteristic: First, it offers conditional privacy-preservation: on the one hand, the bidder is anonymous to the public, on the other hand, only the collaboration of auctioneer and registration manager can reveal the true identity of a malicious bidder. Second, it does not require to maintain a black list which records the evicted malicious bidders. Finally, it is efficient: it saves the communication round complexity comparing with previously proposed solutions.
Upward Point-Set Embeddability
Venue: arXiv cs.DS 2010
Year: 2010

We study the problem of Upward Point-Set Embeddability, that is the problem of deciding whether a given upward planar digraph $D$ has an upward planar embedding into a point set $S$. We show that any switch tree admits an upward planar straight-line embedding into any convex point set. For the class of $k$-switch trees, that is a generalization of switch trees (according to this definition a switch tree is a $1$-switch tree), we show that not every $k$-switch tree admits an upward planar straight-line embedding into any convex point set, for any $k \geq 2$. Finally we show that the problem of Upward Point-Set Embeddability is NP-complete.
Some Tractable Win-Lose Games
Venue: arXiv cs.GT 2010
Year: 2010

Determining a Nash equilibrium in a $2$-player non-zero sum game is known to be PPAD-hard (Chen and Deng (2006), Chen, Deng and Teng (2009)). The problem, even when restricted to win-lose bimatrix games, remains PPAD-hard (Abbott, Kane and Valiant (2005)). However, there do exist polynomial time tractable classes of win-lose bimatrix games - such as, very sparse games (Codenotti, Leoncini and Resta (2006)) and planar games (Addario-Berry, Olver and Vetta (2007)). We extend the results in the latter work to $K_{3,3}$ minor-free games and a subclass of $K_5$ minor-free games. Both these classes of games strictly contain planar games. Further, we sharpen the upper bound to unambiguous logspace, a small complexity class contained well within polynomial time. Apart from these classes of games, our results also extend to a class of games that contain both $K_{3,3}$ and $K_5$ as minors, thereby covering a large and non-trivial class of win-lose bimatrix games. For this class, we prove an upper bound of nondeterministic logspace, again a small complexity class within polynomial time. Our techniques are primarily graph theoretic and use structural characterizations of the considered minor-closed families.
Analysing the behaviour of robot teams through relational sequential pattern mining
Venue: arXiv cs.AI 2010
Year: 2010

This report outlines the use of a relational representation in a Multi-Agent domain to model the behaviour of the whole system. A desired property in this systems is the ability of the team members to work together to achieve a common goal in a cooperative manner. The aim is to define a systematic method to verify the effective collaboration among the members of a team and comparing the different multi-agent behaviours. Using external observations of a Multi-Agent System to analyse, model, recognize agent behaviour could be very useful to direct team actions. In particular, this report focuses on the challenge of autonomous unsupervised sequential learning of the team's behaviour from observations. Our approach allows to learn a symbolic sequence (a relational representation) to translate raw multi-agent, multi-variate observations of a dynamic, complex environment, into a set of sequential behaviours that are characteristic of the team in question, represented by a set of sequences expressed in first-order logic atoms. We propose to use a relational learning algorithm to mine meaningful frequent patterns among the relational sequences to characterise team behaviours. We compared the performance of two teams in the RoboCup four-legged league environment, that have a very different approach to the game. One uses a Case Based Reasoning approach, the other uses a pure reactive behaviour.
Fast Color Quantization Using Weighted Sort-Means Clustering
Venue: arXiv cs.CV 2010
Year: 2010

Color quantization is an important operation with numerous applications in graphics and image processing. Most quantization methods are essentially based on data clustering algorithms. However, despite its popularity as a general purpose clustering algorithm, k-means has not received much respect in the color quantization literature because of its high computational requirements and sensitivity to initialization. In this paper, a fast color quantization method based on k-means is presented. The method involves several modifications to the conventional (batch) k-means algorithm including data reduction, sample weighting, and the use of triangle inequality to speed up the nearest neighbor search. Experiments on a diverse set of images demonstrate that, with the proposed modifications, k-means becomes very competitive with state-of-the-art color quantization methods in terms of both effectiveness and efficiency.
Reasoning about Cardinal Directions between Extended Objects: The Hardness Result
Venue: arXiv cs.AI 2010
Year: 2010

The cardinal direction calculus (CDC) proposed by Goyal and Egenhofer is a very expressive qualitative calculus for directional information of extended objects. Early work has shown that consistency checking of complete networks of basic CDC constraints is tractable while reasoning with the CDC in general is NP-hard. This paper shows, however, if allowing some constraints unspecified, then consistency checking of possibly incomplete networks of basic CDC constraints is already intractable. This draws a sharp boundary between the tractable and intractable subclasses of the CDC. The result is achieved by a reduction from the well-known 3-SAT problem.
Effects of Sequence Partitioning on Compression Rate
Venue: arXiv cs.IT 2010
Year: 2010

In the paper, a theoretical work is done for investigating effects of splitting data sequence into packs of data set. We proved that a partitioning of data sequence is possible to find such that the entropy rate at each subsequence is lower than entropy rate of the source. Effects of sequence partitioning on overall compression rate are argued on the bases of partitioning statistics, and then, an optimization problem for an optimal partition is defined to improve overall compression rate of a sequence.
Lumpability Abstractions of Rule-based Systems
Venue: arXiv cs.CE 2010
Year: 2010

The induction of a signaling pathway is characterized by transient complex formation and mutual posttranslational modification of proteins. To faithfully capture this combinatorial process in a mathematical model is an important challenge in systems biology. Exploiting the limited context on which most binding and modification events are conditioned, attempts have been made to reduce the combinatorial complexity by quotienting the reachable set of molecular species, into species aggregates while preserving the deterministic semantics of the thermodynamic limit. Recently we proposed a quotienting that also preserves the stochastic semantics and that is complete in the sense that the semantics of individual species can be recovered from the aggregate semantics. In this paper we prove that this quotienting yields a sufficient condition for weak lumpability and that it gives rise to a backward Markov bisimulation between the original and aggregated transition system. We illustrate the framework on a case study of the EGF/insulin receptor crosstalk.
Qualitative modelling and analysis of regulations in multi-cellular systems using Petri nets and topological collections
Venue: arXiv cs.CE 2010
Year: 2010

In this paper, we aim at modelling and analyzing the regulation processes in multi-cellular biological systems, in particular tissues. The modelling framework is based on interconnected logical regulatory networks a la Rene Thomas equipped with information about their spatial relationships. The semantics of such models is expressed through colored Petri nets to implement regulation rules, combined with topological collections to implement the spatial information. Some constraints are put on the the representation of spatial information in order to preserve the possibility of an enumerative and exhaustive state space exploration. This paper presents the modelling framework, its semantics, as well as a prototype implementation that allowed preliminary experimentation on some applications.
Stabilizing knowledge through standards - A perspective for the humanities
Venue: arXiv cs.CL 2010
Year: 2010

It is usual to consider that standards generate mixed feelings among scientists. They are often seen as not really reflecting the state of the art in a given domain and a hindrance to scientific creativity. Still, scientists should theoretically be at the best place to bring their expertise into standard developments, being even more neutral on issues that may typically be related to competing industrial interests. Even if it could be thought of as even more complex to think about developping standards in the humanities, we will show how this can be made feasible through the experience gained both within the Text Encoding Initiative consortium and the International Organisation for Standardisation. By taking the specific case of lexical resources, we will try to show how this brings about new ideas for designing future research infrastructures in the human and social sciences.
Flexible Session Management in a Distributed Environment
Venue: arXiv cs.DC 2010
Year: 2010

Many secure communication libraries used by distributed systems, such as SSL, TLS, and Kerberos, fail to make a clear distinction between the authentication, session, and communication layers. In this paper we introduce CEDAR, the secure communication library used by the Condor High Throughput Computing software, and present the advantages to a distributed computing system resulting from CEDAR's separation of these layers. Regardless of the authentication method used, CEDAR establishes a secure session key, which has the flexibility to be used for multiple capabilities. We demonstrate how a layered approach to security sessions can avoid round-trips and latency inherent in network authentication. The creation of a distinct session management layer allows for optimizations to improve scalability by way of delegating sessions to other components in the system. This session delegation creates a chain of trust that reduces the overhead of establishing secure connections and enables centralized enforcement of system-wide security policies. Additionally, secure channels based upon UDP datagrams are often overlooked by existing libraries; we show how CEDAR's structure accommodates this as well. As an example of the utility of this work, we show how the use of delegated security sessions and other techniques inherent in CEDAR's architecture enables US CMS to meet their scalability requirements in deploying Condor over large-scale, wide-area grid systems.