OpenRaiser/Intern-Atlas huggingface dataset:
Digital Ecosystems: Ecosystem-Oriented Architectures
Venue: arXiv cs.NI 2011
Year: 2011

We view Digital Ecosystems to be the digital counterparts of biological ecosystems. Here, we are concerned with the creation of these Digital Ecosystems, exploiting the self-organising properties of biological ecosystems to evolve high-level software applications. Therefore, we created the Digital Ecosystem, a novel optimisation technique inspired by biological ecosystems, where the optimisation works at two levels: a first optimisation, migration of agents which are distributed in a decentralised peer-to-peer network, operating continuously in time; this process feeds a second optimisation based on evolutionary computing that operates locally on single peers and is aimed at finding solutions to satisfy locally relevant constraints. The Digital Ecosystem was then measured experimentally through simulations, with measures originating from theoretical ecology, evaluating its likeness to biological ecosystems. This included its responsiveness to requests for applications from the user base, as a measure of the ecological succession (ecosystem maturity). Overall, we have advanced the understanding of Digital Ecosystems, creating Ecosystem-Oriented Architectures where the word ecosystem is more than just a metaphor.
Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we define and study the new problem Simultaneous PQ-Ordering. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. Simultaneous PQ-Ordering asks whether orders of the leaves of each of the trees can be chosen simultaneously, that is, for every child-parent relation the order chosen for the parent is an extension of the order chosen for the child. We show that Simultaneous PQ-Ordering is NP-complete in general and that it is efficiently solvable for a special subset of instances, the 2-fixed instances. We then show that several constrained embedding problems can be formulated as such 2-fixed instances. In particular, we obtain a linear-time algorithm for Partially PQ-Constrained Planarity for biconnected graphs, a common generalization of two recently considered embedding problems, and a quadratic-time algorithm for Simultaneous Embedding with Fixed Edges for biconnected graphs with a connected intersection; formerly only the much more restricted case that the intersection is biconnected was known to be efficiently solvable. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two non-trivial blocks. This includes for example the case where both graphs have maximum degree 5. Moreover, we give an optimal linear-time algorithm for recognition of simultaneous interval graphs, improving upon a recent O(n^2 log n)-time algorithm due to Jampani and Lubiw and show that this can be used to also solve the problem of extending partial interval representations of graphs with n vertices and m edges in time O(n + m), improving a recent result of Klavík et al.
Grammatical Relations of Myanmar Sentences Augmented by Transformation-Based Learning of Function Tagging
Venue: arXiv cs.CL 2011
Year: 2011

In this paper we describe function tagging using Transformation Based Learning (TBL) for Myanmar that is a method of extensions to the previous statistics-based function tagger. Contextual and lexical rules (developed using TBL) were critical in achieving good results. First, we describe a method for expressing lexical relations in function tagging that statistical function tagging are currently unable to express. Function tagging is the preprocessing step to show grammatical relations of the sentences. Then we use the context free grammar technique to clarify the grammatical relations in Myanmar sentences or to output the parse trees. The grammatical relations are the functional structure of a language. They rely very much on the function tag of the tokens. We augment the grammatical relations of Myanmar sentences with transformation-based learning of function tagging.
A Generalized Kahn Principle for Abstract Asynchronous Networks
Venue: arXiv cs.LO 2011
Year: 2011

Our general motivation is to answer the question: "What is a model of concurrent computation?". As a preliminary exercise, we study dataflow networks. We develop a very general notion of model for asynchronous networks. The "Kahn Principle", which states that a network built from functional nodes is the least fixpoint of a system of equations associated with the network, has become a benchmark for the formal study of dataflow networks. We formulate a generalized version of the Kahn Principle, which applies to a large class of non-deterministic systems, in the setting of abstract asynchronous networks; and prove that the Kahn Principle holds under certain natural assumptions on the model. We also show that a class of models, which represent networks that compute over arbitrary event structures, generalizing dataflow networks which compute over streams, satisfy these assumptions.
Approximate ML Decision Feedback Block Equalizer for Doubly Selective Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

In order to effetively suppress intersymbol interference (ISI) at low complexity, we propose in this paper an approximate maximum likelihood (ML) decision feedback block equalizer (A-ML-DFBE) for doubly selective (frequency-selective, time-selective) fading channels. The proposed equalizer design makes efficient use of the special time-domain representation of the multipath channels through a matched filter, a sliding window, a Gaussian approximation, and a decision feedback. The A-ML-DFBE has the following features: 1) It achieves performance close to maximum likelihood sequence estimation (MLSE), and significantly outperforms the minimum mean square error (MMSE) based detectors; 2) It has substantially lower complexity than the conventional equalizers; 3) It easily realizes the complexity and performance tradeoff by adjusting the length of the sliding window; 4) It has a simple and fixed-length feedback filter. The symbol error rate (SER) is derived to characterize the behaviour of the A-ML-DFBE, and it can also be used to find the key parameters of the proposed equalizer. In addition, we further prove that the A-ML-DFBE obtains full multipath diversity.
A New Approach to Incremental Cycle Detection and Related Problems
Venue: arXiv cs.DS 2011
Year: 2011

We consider the problem of detecting a cycle in a directed graph that grows by arc insertions, and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two algorithms, one suited to sparse graphs, and the other to dense graphs. The former takes the minimum of O(m^{3/2}) and O(mn^{2/3}) time to insert m arcs into an n-vertex graph; the latter takes O(n^2 log(n)) time. Our sparse algorithm is considerably simpler than a previous O(m^{3/2})-time algorithm; it is also faster on graphs of sufficient density. The time bound of our dense algorithm beats the previously best time bound of O(n^{5/2}) for dense graphs. Our algorithms rely for their efficiency on topologically ordered vertex numberings; bounds on the size of the numbers give bound on running times.
The Web economy: goods, users, models and policies
Venue: arXiv cs.CY 2011
Year: 2011

Web emerged as an antidote to the rapidly increasing quantity of accumulated knowledge and become successful because it facilitates massive participation and communication with minimum costs. Today, its enormous impact, scale and dynamism in time and space make very difficult (and sometimes impossible) to measure and anticipate the effects in human society. In addition to that, we demand from the Web to be fast, secure, reliable, all-inclusive and trustworthy in any transaction. The scope of the present article is to review a part of the Web economy literature that will help us to identify its major participants and their functions. The goal is to understand how the Web economy differs from the traditional setting and what implications have these differences. Secondarily, we attempt to establish a minimal common understanding about the incentives and properties of the Web economy. In this direction the concept of Web Goods and a new classification of Web Users are introduced and analyzed This article, is not, by any means, a thorough review of the economic literature related to the Web. We focus only on its relevant part that models the Web as a standalone economic artifact with native functionality and processes.
Worst-Case Optimal Priority Queues via Extended Regular Counters
Venue: arXiv cs.DS 2011
Year: 2011

We consider the classical problem of representing a collection of priority queues under the operations \Findmin{}, \Insert{}, \Decrease{}, \Meld{}, \Delete{}, and \Deletemin{}. In the comparison-based model, if the first four operations are to be supported in constant time, the last two operations must take at least logarithmic time. Brodal showed that his worst-case efficient priority queues achieve these worst-case bounds. Unfortunately, this data structure is involved and the time bounds hide large constants. We describe a new variant of the worst-case efficient priority queues that relies on extended regular counters and provides the same asymptotic time and space bounds as the original. Due to the conceptual separation of the operations on regular counters and all other operations, our data structure is simpler and easier to describe and understand. Also, the constants in the time and space bounds are smaller. In addition, we give an implementation of our structure on a pointer machine. For our pointer-machine implementation, \Decrease{} and \Meld{} are asymptotically slower and require $O(\lg\lg{n})$ worst-case time, where $n$ denotes the number of elements stored in the resulting priority queue.
Stabilization of Branching Queueing Networks
Venue: arXiv cs.PF 2011
Year: 2011

Queueing networks are gaining attraction for the performance analysis of parallel computer systems. A Jackson network is a set of interconnected servers, where the completion of a job at server i may result in the creation of a new job for server j. We propose to extend Jackson networks by "branching" and by "control" features. Both extensions are new and substantially expand the modelling power of Jackson networks. On the other hand, the extensions raise computational questions, particularly concerning the stability of the networks, i.e, the ergodicity of the underlying Markov chain. We show for our extended model that it is decidable in polynomial time if there exists a controller that achieves stability. Moreover, if such a controller exists, one can efficiently compute a static randomized controller which stabilizes the network in a very strong sense; in particular, all moments of the queue sizes are finite.
Classification with Invariant Scattering Representations
Venue: arXiv cs.CV 2011
Year: 2011

A scattering transform defines a signal representation which is invariant to translations and Lipschitz continuous relatively to deformations. It is implemented with a non-linear convolution network that iterates over wavelet and modulus operators. Lipschitz continuity locally linearizes deformations. Complex classes of signals and textures can be modeled with low-dimensional affine spaces, computed with a PCA in the scattering domain. Classification is performed with a penalized model selection. State of the art results are obtained for handwritten digit recognition over small training sets, and for texture classification.
Learning in embodied action-perception loops through exploration
Venue: arXiv cs.LG 2011
Year: 2011

Although exploratory behaviors are ubiquitous in the animal kingdom, their computational underpinnings are still largely unknown. Behavioral Psychology has identified learning as a primary drive underlying many exploratory behaviors. Exploration is seen as a means for an animal to gather sensory data useful for reducing its ignorance about the environment. While related problems have been addressed in Data Mining and Reinforcement Learning, the computational modeling of learning-driven exploration by embodied agents is largely unrepresented. Here, we propose a computational theory for learning-driven exploration based on the concept of missing information that allows an agent to identify informative actions using Bayesian inference. We demonstrate that when embodiment constraints are high, agents must actively coordinate their actions to learn efficiently. Compared to earlier approaches, our exploration policy yields more efficient learning across a range of worlds with diverse structures. The improved learning in turn affords greater success in general tasks including navigation and reward gathering. We conclude by discussing how the proposed theory relates to previous information-theoretic objectives of behavior, such as predictive information and the free energy principle, and how it might contribute to a general theory of exploratory behavior.
Highly-Concurrent Doubly-Linked Lists
Venue: arXiv cs.DS 2011
Year: 2011

As file systems are increasingly being deployed on ever larger systems with many cores and multi-gigabytes of memory, scaling the internal data structures of file systems has taken greater importance and urgency. A doubly-linked list is a simple and very commonly used data structure in file systems but it is not very friendly to multi-threaded use. While special cases of lists, such as queues and stacks, have lock-free versions that scale reasonably well, the general form of a doubly-linked list offers no such solution. Using a mutex to serialize all operations remains the de-facto method of maintaining a doubly linked list. This severely limits the scalability of the list and developers must resort to ad-hoc workarounds that involve using multiple smaller lists (with individual locks) and deal with the resulting complexity of the system. In this paper, we present an approach to building highly concurrent data structures, with special focus on the implementation of highly concurrent doubly-linked lists. Dubbed "advanced doubly-linked list" or "adlist" for short, our list allows iteration in any direction, and insert/delete operations over non-overlapping nodes to execute in parallel. Operations with common nodes get serialized so as to always present a locally consistent view to the callers. An adlist node needs an additional 8 bytes of space for keeping synchronization information. The Data Domain File System makes extensive use of adlists which has allowed for significant scaling of the system without sacrificing simplicity.
Knightian Auctions
Venue: arXiv cs.GT 2011
Year: 2011

We study single-good auctions in a setting where each player knows his own valuation only within a constant multiplicative factor δ in (0,1), and the mechanism designer knows δ. The classical notions of implementation in dominant strategies and implementation in undominated strategies are naturally extended to this setting, but their power is vastly different. On the negative side, we prove that no dominant-strategy mechanism can guarantee social welfare that is significantly better than that achievable by assigning the good to a random player. On the positive side, we provide tight upper and lower bounds for the fraction of the maximum social welfare achievable in undominated strategies, whether deterministically or probabilistically.
Wireless Communications and Networking Technologies for Smart Grid: Paradigms and Challenges
Venue: arXiv cs.NI 2011
Year: 2011

Smart grid, regarded as the next generation power grid, uses two-way flows of electricity and information to create a widely distributed automated energy delivery network. In this work we present our vision on smart grid from the perspective of wireless communications and networking technologies. We present wireless communication and networking paradigms for four typical scenarios in the future smart grid and also point out the research challenges of the wireless communication and networking technologies used in smart grid
Evaluating Quality of Chaotic Pseudo-Random Generators: Application to Information Hiding
Venue: arXiv cs.CR 2011
Year: 2011

Guaranteeing the security of information transmitted through the Internet, against passive or active attacks, is a major concern. The discovery of new pseudo-random number generators with a strong level of security is a field of research in full expansion, due to the fact that numerous cryptosystems and data hiding schemes are directly dependent on the quality of these generators. At the conference Internet`09, we described a generator based on chaotic iterations which behaves chaotically as defined by Devaney. In this paper which is an extension of the work presented at the conference Internet`10, the proposal is to improve the speed, the security, and the evaluation of this generator, to make its use more relevant in the Internet security context. In order to do so, a comparative study between various generators is carried out and statistical results are improved. Finally, an application in the information hiding framework is presented with details, to give an illustrative example of the use of such a generator in the Internet security field.
Cyclic Orbit Codes
Venue: arXiv cs.IT 2011
Year: 2011

In network coding a constant dimension code consists of a set of k-dimensional subspaces of F_q^n. Orbit codes are constant dimension codes which are defined as orbits of a subgroup of the general linear group, acting on the set of all subspaces of F_q^n. If the acting group is cyclic, the corresponding orbit codes are called cyclic orbit codes. In this paper we give a classification of cyclic orbit codes and propose a decoding procedure for a particular subclass of cyclic orbit codes.
A Study on Hierarchical Floorplans of Order k
Venue: arXiv cs.DM 2011
Year: 2011

A floorplan is a rectangular dissection which describes the relative placement of electronic modules on the chip. It is called a mosaic floorplan if there are no empty rooms or cross junctions in the rectangular dissection. We study a subclass of mosaic floorplans called hierarchical floorplans of order $k$ (abbreviated HFO-${k}$). A floorplan is HFO-$k$ if it can be obtained by starting with a single rectangle and recursively embedding mosaic floorplans of at most $k$ rooms inside the rooms of intermediate floorplans. When $k=2$ this is exactly the class of slicing floorplans as the only distinct floorplans with two rooms are a room with a vertical slice and a room with a horizontal slice respectdeively. And embedding such a room is equivalent to slicing the parent room vertically/horizontally. In this paper we characterize permutations corresponding to the Abe-labeling of HFO-$k$ floorplans and also give an algorithm for identification of such permutations in linear time for any particular $k$. We give a recurrence relation for exact number of HFO-5 floorplans with $n$ rooms which can be easily extended to any $k$ also. Based on this recurrence we provide a polynomial time algorithm to generate the number of HFO-$k$ floorplans with $n$ rooms. Considering its application in VLSI design we also give moves on HFO-$k$ family of permutations for combinatorial optimization using simulated annealing etc. We also explore some interesting properties of Baxter permutations which have a bijective correspondence with mosaic floorplans.
Intelligent Paging Strategy for Multi-Carrier CDMA System
Venue: arXiv cs.NI 2011
Year: 2011

Subscriber satisfaction and maximum radio resource utilization are the pivotal criteria in communication system design. In multi-Carrier CDMA system, different paging algorithms are used for locating user within the shortest possible time and best possible utilization of radio resources. Different paging algorithms underscored different techniques based on the different purposes. However, low servicing time of sequential search and better utilization of radio resources of concurrent search can be utilized simultaneously by swapping of the algorithms. In this paper, intelligent mechanism has been developed for dynamic algorithm assignment basing on time-varying traffic demand, which is predicted by radial basis neural network; and its performance has been analyzed are based on prediction efficiency of different types of data. High prediction efficiency is observed with a good correlation coefficient (0.99) and subsequently better performance is achieved by dynamic paging algorithm assignment. This claim is substantiated by the result of proposed intelligent paging strategy.
POCS Based Super-Resolution Image Reconstruction Using an Adaptive Regularization Parameter
Venue: arXiv cs.CV 2011
Year: 2011

Crucial information barely visible to the human eye is often embedded in a series of low-resolution images taken of the same scene. Super-resolution enables the extraction of this information by reconstructing a single image, at a high resolution than is present in any of the individual images. This is particularly useful in forensic imaging, where the extraction of minute details in an image can help to solve a crime. Super-resolution image restoration has been one of the most important research areas in recent years which goals to obtain a high resolution (HR) image from several low resolutions (LR) blurred, noisy, under sampled and displaced images. Relation of the HR image and LR images can be modeled by a linear system using a transformation matrix and additive noise. However, a unique solution may not be available because of the singularity of transformation matrix. To overcome this problem, POCS method has been used. However, their performance is not good because the effect of noise energy has been ignored. In this paper, we propose an adaptive regularization approach based on the fact that the regularization parameter should be a linear function of noise variance. The performance of the proposed approach has been tested on several images and the obtained results demonstrate the superiority of our approach compared with existing methods.
Cooperative Game-Theoretic Approach to Spectrum Sharing in Cognitive Radios
Venue: arXiv cs.GT 2011
Year: 2011

In this paper, a novel framework for normative modeling of the spectrum sensing and sharing problem in cognitive radios (CRs) as a transferable utility (TU) cooperative game is proposed. Secondary users (SUs) jointly sense the spectrum and cooperatively detect the primary user (PU) activity for identifying and accessing unoccupied spectrum bands. The games are designed to be balanced and super-additive so that resource allocation is possible and provides SUs with an incentive to cooperate and form the grand coalition. The characteristic function of the game is derived based on the worths of SUs, calculated according to the amount of work done for the coalition in terms of reduction in uncertainty about PU activity. According to her worth in the coalition, each SU gets a pay-off that is computed using various one-point solutions such as Shapley value, τ-value and Nucleolus. Depending upon their data rate requirements for transmission, SUs use the earned pay-off to bid for idle channels through a socially optimal Vickrey-Clarke-Groves (VCG) auction mechanism. Simulation results show that, in comparison with other resource allocation models, the proposed cooperative game-theoretic model provides the best balance between fairness, cooperation and performance in terms of data rates achieved by each SU.