OpenRaiser/Intern-Atlas huggingface dataset:
Secure Routing in Wireless Mesh Networks
Venue: arXiv cs.CR 2011
Year: 2011

Wireless mesh networks (WMNs) have emerged as a promising concept to meet the challenges in next-generation networks such as providing flexible, adaptive, and reconfigurable architecture while offering cost-effective solutions to the service providers. Unlike traditional Wi-Fi networks, with each access point (AP) connected to the wired network, in WMNs only a subset of the APs are required to be connected to the wired network. The APs that are connected to the wired network are called the Internet gateways (IGWs), while the APs that do not have wired connections are called the mesh routers (MRs). The MRs are connected to the IGWs using multi-hop communication. The IGWs provide access to conventional clients and interconnect ad hoc, sensor, cellular, and other networks to the Internet. However, most of the existing routing protocols for WMNs are extensions of protocols originally designed for mobile ad hoc networks (MANETs) and thus they perform sub-optimally. Moreover, most routing protocols for WMNs are designed without security issues in mind, where the nodes are all assumed to be honest. In practical deployment scenarios, this assumption does not hold. This chapter provides a comprehensive overview of security issues in WMNs and then particularly focuses on secure routing in these networks. First, it identifies security vulnerabilities in the medium access control (MAC) and the network layers. Various possibilities of compromising data confidentiality, data integrity, replay attacks and offline cryptanalysis are also discussed. Then various types of attacks in the MAC and the network layers are discussed. After enumerating the various types of attacks on the MAC and the network layer, the chapter briefly discusses on some of the preventive mechanisms for these attacks.
Type Classes for Mathematics in Type Theory
Venue: arXiv cs.LO 2011
Year: 2011

The introduction of first-class type classes in the Coq system calls for re-examination of the basic interfaces used for mathematical formalization in type theory. We present a new set of type classes for mathematics and take full advantage of their unique features to make practical a particularly flexible approach formerly thought infeasible. Thus, we address both traditional proof engineering challenges as well as new ones resulting from our ambition to build upon this development a library of constructive analysis in which abstraction penalties inhibiting efficient computation are reduced to a minimum. The base of our development consists of type classes representing a standard algebraic hierarchy, as well as portions of category theory and universal algebra. On this foundation we build a set of mathematically sound abstract interfaces for different kinds of numbers, succinctly expressed using categorical language and universal algebra constructions. Strategic use of type classes lets us support these high-level theory-friendly definitions while still enabling efficient implementations unhindered by gratuitous indirection, conversion or projection. Algebra thrives on the interplay between syntax and semantics. The Prolog-like abilities of type class instance resolution allow us to conveniently define a quote function, thus facilitating the use of reflective techniques.
A Discrete Choquet Integral for Ordered Systems
Venue: arXiv cs.DM 2011
Year: 2011

A model for a Choquet integral for arbitrary finite set systems is presented. The model includes in particular the classical model on the system of all subsets of a finite set. The general model associates canonical non-negative and positively homogeneous superadditive functionals with generalized belief functions relative to an ordered system, which are then extended to arbitrary valuations on the set system. It is shown that the general Choquet integral can be computed by a simple Monge-type algorithm for so-called intersection systems, which include as a special case weakly union-closed families. Generalizing Lovász' classical characterization, we give a characterization of the superadditivity of the Choquet integral relative to a capacity on a union-closed system in terms of an appropriate model of supermodularity of such capacities.
Trends in Social Media : Persistence and Decay
Venue: arXiv cs.CY 2011
Year: 2011

Social media generates a prodigious wealth of real-time content at an incessant rate. From all the content that people create and share, only a few topics manage to attract enough attention to rise to the top and become temporal trends which are displayed to users. The question of what factors cause the formation and persistence of trends is an important one that has not been answered yet. In this paper, we conduct an intensive study of trending topics on Twitter and provide a theoretical basis for the formation, persistence and decay of trends. We also demonstrate empirically how factors such as user activity and number of followers do not contribute strongly to trend creation and its propagation. In fact, we find that the resonance of the content with the users of the social network plays a major role in causing trends.
Distributed Throughput-optimal Scheduling in Ad Hoc Wireless Networks
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose a distributed throughput-optimal ad hoc wireless network scheduling algorithm, which is motivated by the celebrated simplex algorithm for solving linear programming (LP) problems. The scheduler stores a sparse set of basic schedules, and chooses the max-weight basic schedule for transmission in each time slot. At the same time, the scheduler tries to update the set of basic schedules by searching for a new basic schedule in a throughput increasing direction. We show that both of the above procedures can be achieved in a distributed manner. Specifically, we propose an average consensus based link contending algorithm to implement the distributed max weight scheduling. Further, we show that the basic schedule update can be implemented using CSMA mechanisms, which is similar to the one proposed by Jiang et al. Compared to the optimal distributed scheduler in Jiang's paper, where schedules change in a random walk fashion, our algorithm has a better delay performance by achieving faster schedule transitions in the steady state. The performance of the algorithm is finally confirmed by simulation results.
Multiple Tree for Partially Observable Monte-Carlo Tree Search
Venue: arXiv cs.GT 2011
Year: 2011

We propose an algorithm for computing approximate Nash equilibria of partially observable games using Monte-Carlo tree search based on recent bandit methods. We obtain experimental results for the game of phantom tic-tac-toe, showing that strong strategies can be efficiently computed by our algorithm.
Restructuring in Combinatorial Optimization
Venue: arXiv cs.DS 2011
Year: 2011

The paper addresses a new class of combinatorial problems which consist in restructuring of solutions (as structures) in combinatorial optimization. Two main features of the restructuring process are examined: (i) a cost of the restructuring, (ii) a closeness to a goal solution. This problem corresponds to redesign (improvement, upgrade) of modular systems or solutions. The restructuring approach is described and illustrated for the following combinatorial optimization problems: knapsack problem, multiple choice problem, assignment problem, spanning tree problems. Examples illustrate the restructuring processes.
Predictors of short-term decay of cell phone contacts in a large scale communication network
Venue: arXiv cs.SI 2011
Year: 2011

Under what conditions is an edge present in a social network at time t likely to decay or persist by some future time t + Delta(t)? Previous research addressing this issue suggests that the network range of the people involved in the edge, the extent to which the edge is embedded in a surrounding structure, and the age of the edge all play a role in edge decay. This paper uses weighted data from a large-scale social network built from cell-phone calls in an 8-week period to determine the importance of edge weight for the decay/persistence process. In particular, we study the relative predictive power of directed weight, embeddedness, newness, and range (measured as outdegree) with respect to edge decay and assess the effectiveness with which a simple decision tree and logistic regression classifier can accurately predict whether an edge that was active in one time period continues to be so in a future time period. We find that directed edge weight, weighted reciprocity and time-dependent measures of edge longevity are highly predictive of whether we classify an edge as persistent or decayed, relative to the other types of factors at the dyad and neighborhood level.
Distributed Uplink Resource Allocation in Cognitive Radio Networks -- Part II: Equilibria and Algorithms for Joint Access Point Selection and Power Allocation
Venue: arXiv cs.IT 2011
Year: 2011

In the first part of this paper, we have studied solely the spectrum sharing aspect of the above problem, and proposed algorithms for the CUs in the single AP network to efficiently share the spectrum. In this second part of the paper, we build upon our previous understanding of the single AP network, and formulate the joint spectrum decision and spectrum sharing problem in a multiple AP network into a non-cooperative game, in which the feasible strategy of a player contains a discrete variable (the AP/spectrum decision) and a continuous vector (the power allocation among multiple channels). The structure of the game is hence very different from most non-cooperative spectrum management game proposed in the literature. We provide characterization of the Nash Equilibrium (NE) of this game, and present a set of novel algorithms that allow the CUs to distributively and efficiently select the suitable AP and share the channels with other CUs. Finally, we study the properties of the proposed algorithms as well as their performance via extensive simulations.
Quasi-Cross Lattice Tilings with Applications to Flash Memory
Venue: arXiv cs.IT 2011
Year: 2011

We consider lattice tilings of $\R^n$ by a shape we call a $(\kp,\km,n)$-quasi-cross. Such lattices form perfect error-correcting codes which correct a single limited-magnitude error with prescribed maximal-magnitudes of positive error and negative error (the ratio of which is called the balance ratio). These codes can be used to correct both disturb and retention errors in flash memories, which are characterized by having limited magnitudes and different signs. We construct infinite families of perfect codes for any rational balance ratio, and provide a specific construction for $(2,1,n)$-quasi-cross lattice tiling. The constructions are related to group splitting and modular $B_1$ sequences. We also study bounds on the parameters of lattice-tilings by quasi-crosses, connecting the arm lengths of the quasi-crosses and the dimension. We also prove constraints on group splitting, a specific case of which shows that the parameters of the lattice tiling of $(2,1,n)$-quasi-crosses is the only ones possible.
A new protocol implementing authentication transformations for multi-located parties
Venue: arXiv cs.CR 2011
Year: 2011

This paper discusses a new protocol implementing authentication in a multi-located environment that avoids man-in-the-middle (MIM) attack, replay attack and provides privacy, integrity of a message for multi-located parties. The protocol uses the concept that each party is associated with a subsidiary agent.
Decidable Expansions of Labelled Linear Orderings
Venue: arXiv cs.LO 2011
Year: 2011

Consider a linear ordering equipped with a finite sequence of monadic predicates. If the ordering contains an interval of order type ωor -ω, and the monadic second-order theory of the combined structure is decidable, there exists a non-trivial expansion by a further monadic predicate that is still decidable.
A Study of Language Usage Evolution in Open Source Software
Venue: arXiv cs.PL 2011
Year: 2011

The use of programming languages such as Java and C in Open Source Software (OSS) has been well studied. However, many other popular languages such as XSL or XML have received minor attention. In this paper, we discuss some trends in OSS development that we observed when considering multiple programming language evolution of OSS. Based on the revision data of 22 OSS projects, we tracked the evolution of language usage and other artefacts such as documentation files, binaries and graphics files. In these systems several different languages and artefact types including C/C++, Java, XML, XSL, Makefile, Groovy, HTML, Shell scripts, CSS, Graphics files, JavaScript, JSP, Ruby, Phyton, XQuery, OpenDocument files, PHP, etc. have been used. We found that the amount of code written in different languages differs substantially. Some of our findings can be summarized as follows: (1) JavaScript and CSS files most often co-evolve with XSL; (2) Most Java developers but only every second C/C++ developer work with XML; (3) and more generally, we observed a significant increase of usage of XML and XSL during recent years and found that Java or C are hardly ever the only language used by a developer. In fact, a developer works with more than 5 different artefact types (or 4 different languages) in a project on average.
Towards a Cognitive Handoff for the Future Internet: Model-driven Methodology and Taxonomy of Scenarios
Venue: arXiv cs.NI 2011
Year: 2011

A cognitive handoff is a multipurpose handoff that achieves many desirable features simultaneously; e.g., seamlessness, autonomy, security, correctness, adaptability, etc. But, the development of cognitive handoffs is a challenging task that has not been properly addressed in the literature. In this paper, we discuss the difficulties of developing cognitive handoffs and propose a new model-driven methodology for their systematic development. The theoretical framework of this methodology is the holistic approach, the functional decomposition method, the model-based design paradigm, and the theory of design as scientific problem-solving. We applied the proposed methodology and obtained the following results: (i) a correspondence between handoff purposes and quantitative environment information, (ii) a novel taxonomy of handoff mobility scenarios, and (iii) an original state-based model representing the functional behavior of the handoff process.
Cellular Automata and Discrete Geometry
Venue: arXiv cs.CG 2011
Year: 2011

In this paper, we look at the possibility to implement the algorithm to construct a discrete line devised by the first author in cellular automata. It turns out that such an implementation is feasible.
A decompilation of the pi-calculus and its application to termination
Venue: arXiv cs.PL 2011
Year: 2011

We study the correspondence between a concurrent lambda-calculus in administrative, continuation passing style and a pi-calculus and we derive a termination result for the latter.
Stuttering Equivalence for Parity Games
Venue: arXiv cs.LO 2011
Year: 2011

We study the process theoretic notion of stuttering equivalence in the setting of parity games. We demonstrate that stuttering equivalent vertices have the same winner in the parity game. This means that solving a parity game can be accelerated by minimising the game graph with respect to stuttering equivalence. While, at the outset, it might not be clear that this strategy should pay off, our experiments using typical verification problems illustrate that stuttering equivalence speeds up solving parity games in many cases.
Matching, Merging and Structural Properties of Data Base Category
Venue: arXiv cs.DB 2011
Year: 2011

Main contribution of this paper is an investigation of expressive power of the database category DB. An object in this category is a database-instance (set of n-ary relations). Morphisms are not functions but have complex tree structures based on a set of complex query computations. They express the semantics of view-based mappings between databases. The higher (logical) level scheme mappings between databases, usually written in some high expressive logical language, may be functorially translated into this base "computation" DB category . The behavioral point of view for databases is assumed, with behavioural equivalence of databases corresponding to isomorphism of objects in DB category. The introduced observations, which are view-based computations without side-effects, are based (from Universal algebra) on monad endofunctor T, which is the closure operator for objects and for morphisms also. It was shown that DB is symmetric (with a bijection between arrows and objects) 2-category, equal to its dual, complete and cocomplete. In this paper we demonstrate that DB is concrete, locally small and finitely presentable. Moreover, it is enriched over itself monoidal symmetric category with a tensor products for matching, and has a parameterized merging database operation. We show that it is an algebraic lattice and we define a database metric space and a subobject classifier: thus, DB category is a monoidal elementary topos.
High-order integral-chain differentiator and application to acceleration feedback
Venue: arXiv cs.SY 2011
Year: 2011

The equivalence between integral-chain differentiator and usual high-gain differentiator is given under suitable coordinate transformation. Integral-chain differentiator can restrain noises more thoroughly than usual high-gain linear differentiator. In integral-chain differentiator, disturbances only exist in the last differential equation and can be restrained through each layer of integrator. Moreover, a nonlinear integral-chain differentiator is designed which is the expansion of linear integral-chain differentiator. Finally, a 3-order differentiator is applied to the estimation of acceleration for a second-order uncertain system.
Improved Redundancy Bounds for Exponential Objectives
Venue: arXiv cs.IT 2011
Year: 2011

We present new lower and upper bounds for the compression rate of binary prefix codes optimized over memoryless sources according to two related exponential codeword length objectives. The objectives explored here are exponential-average length and exponential-average redundancy. The first of these relates to various problems involving queueing, uncertainty, and lossless communications, and it can be reduced to the second, which has properties more amenable to analysis. These bounds, some of which are tight, are in terms of a form of entropy and/or the probability of an input symbol, improving on recently discovered bounds of similar form. We also observe properties of optimal codes over the exponential-average redundancy utility.
PORGY: Strategy-Driven Interactive Transformation of Graphs
Venue: arXiv cs.CE 2011
Year: 2011

This paper investigates the use of graph rewriting systems as a modelling tool, and advocates the embedding of such systems in an interactive environment. One important application domain is the modelling of biochemical systems, where states are represented by port graphs and the dynamics is driven by rules and strategies. A graph rewriting tool's capability to interactively explore the features of the rewriting system provides useful insights into possible behaviours of the model and its properties. We describe PORGY, a visual and interactive tool we have developed to model complex systems using port graphs and port graph rewrite rules guided by strategies, and to navigate in the derivation history. We demonstrate via examples some functionalities provided by PORGY.
Minimum Redundancy Coding for Uncertain Sources
Venue: arXiv cs.IT 2011
Year: 2011

Consider the set of source distributions within a fixed maximum relative entropy with respect to a given nominal distribution. Lossless source coding over this relative entropy ball can be approached in more than one way. A problem previously considered is finding a minimax average length source code. The minimizing players are the codeword lengths --- real numbers for arithmetic codes, integers for prefix codes --- while the maximizing players are the uncertain source distributions. Another traditional minimizing objective is the first one considered here, maximum (average) redundancy. This problem reduces to an extension of an exponential Huffman objective treated in the literature but heretofore without direct practical application. In addition to these, this paper examines the related problem of maximal minimax pointwise redundancy and the problem considered by Gawrychowski and Gagie, which, for a sufficiently small relative entropy ball, is equivalent to minimax redundancy. One can consider both Shannon-like coding based on optimal real number ("ideal") codeword lengths and a Huffman-like optimal prefix coding.
A General Framework for Development of the Cortex-like Visual Object Recognition System: Waves of Spikes, Predictive Coding and Universal Dictionary of Features
Venue: arXiv cs.CV 2011
Year: 2011

This study is focused on the development of the cortex-like visual object recognition system. We propose a general framework, which consists of three hierarchical levels (modules). These modules functionally correspond to the V1, V4 and IT areas. Both bottom-up and top-down connections between the hierarchical levels V4 and IT are employed. The higher the degree of matching between the input and the preferred stimulus, the shorter the response time of the neuron. Therefore information about a single stimulus is distributed in time and is transmitted by the waves of spikes. The reciprocal connections and waves of spikes implement predictive coding: an initial hypothesis is generated on the basis of information delivered by the first wave of spikes and is tested with the information carried by the consecutive waves. The development is considered as extraction and accumulation of features in V4 and objects in IT. Once stored a feature can be disposed, if rarely activated. This cause update of feature repository. Consequently, objects in IT are also updated. This illustrates the growing process and dynamical change of topological structures of V4, IT and connections between these areas.
Multi-task GLOH feature selection for human age estimation
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, we propose a novel age estimation method based on GLOH feature descriptor and multi-task learning (MTL). The GLOH feature descriptor, one of the state-of-the-art feature descriptor, is used to capture the age-related local and spatial information of face image. As the exacted GLOH features are often redundant, MTL is designed to select the most informative feature bins for age estimation problem, while the corresponding weights are determined by ridge regression. This approach largely reduces the dimensions of feature, which can not only improve performance but also decrease the computational burden. Experiments on the public available FG-NET database show that the proposed method can achieve comparable performance over previous approaches while using much fewer features.