OpenRaiser/Intern-Atlas huggingface dataset:
Equilibrium and Potential in Coalitional Congestion Games
Venue: arXiv cs.GT 2011
Year: 2011

The model of congestion games is widely used to analyze games related to traffic and communication. A central property of these games is that they are potential games and hence posses a pure Nash equilibrium. In reality it is often the case that some players cooperatively decide on their joint action in order to maximize the coalition's total utility. This is by modeled by Coalitional Congestion Games. Typical settings include truck drivers who work for the same shipping company, or routers that belong to the same ISP. The formation of coalitions will typically imply that the resulting coalitional congestion game will no longer posses a pure Nash equilibrium. In this paper we provide conditions under which such games are potential games and posses a pure Nash equilibrium.
Partial Decode-Forward Binning Schemes for the Causal Cognitive Relay Channels
Venue: arXiv cs.IT 2011
Year: 2011

The causal cognitive relay channel (CRC) has two sender-receiver pairs, in which the second sender obtains information from the first sender causally and assists the transmission of both senders. In this paper, we study both the full- and half-duplex modes. In each mode, we propose two new coding schemes built successively upon one another to illustrate the impact of different coding techniques. The first scheme called partial decode-forward binning (PDF-binning) combines the ideas of partial decode-forward relaying and Gelfand-Pinsker binning. The second scheme called Han-Kobayashi partial decode-forward binning (HK-PDF-binning) combines PDF-binning with Han-Kobayashi coding by further splitting rates and applying superposition coding, conditional binning and relaxed joint decoding. In both schemes, the second sender decodes a part of the message from the first sender, then uses Gelfand-Pinsker binning technique to bin against the decoded codeword, but in such a way that allows both state nullifying and forwarding. For the Gaussian channels, this PDF-binning essentializes to a correlation between the transmit signal and the binning state, which encompasses the traditional dirty-paper-coding binning as a special case when this correlation factor is zero. We also provide the closed-form optimal binning parameter for each scheme. The 2-phase half-duplex schemes are adapted from the full-duplex ones by removing block Markov encoding, sending different message parts in different phases and applying joint decoding across both phases. Analysis shows that the HK-PDF-binning scheme in both modes encompasses the Han-Kobayashi rate region and achieves both the partial decode-forward relaying rate for the first sender and interference-free rate for the second sender. Furthermore, this scheme outperforms all existing schemes.
A Model of Spatial Thinking for Computational Intelligence
Venue: arXiv cs.AI 2011
Year: 2011

Trying to be effective (no matter who exactly and in what field) a person face the problem which inevitably destroys all our attempts to easily get to a desired goal. The problem is the existence of some insuperable barriers for our mind, anotherwords barriers for principles of thinking. They are our clue and main reason for research. Here we investigate these barriers and their features exposing the nature of mental process. We start from special structures which reflect the ways to define relations between objects. Then we came to realizing about what is the material our mind uses to build thoughts, to make conclusions, to understand, to form reasoning, etc. This can be called a mental dynamics. After this the nature of mental barriers on the required level of abstraction as well as the ways to pass through them became clear. We begin to understand why thinking flows in such a way, with such specifics and with such limitations we can observe in reality. This can help us to be more optimal. At the final step we start to understand, what ma-thematical models can be applied to such a picture. We start to express our thoughts in a language of mathematics, developing an apparatus for our Spatial Theory of Mind, suitable to represent processes and infrastructure of thinking. We use abstract algebra and stay invariant in relation to the nature of objects.
Parametric Estimation of the Ultimate Size of Hypercomputers
Venue: arXiv cs.PF 2011
Year: 2011

The performance of the emerging petaflops-scale supercomputers of the nearest future (hypercomputers) will be governed not only by the clock frequency of the processing nodes or by the width of the system bus, but also by such factors as the overall power consumption and the geometric size. In this paper, we study the influence of such parameters on one of the most important characteristics of a general purpose computer - on the degree of multithreading that must be present in an application to make the use of the hypercomputer justifiable. Our major finding is that for the class of applications with purely random memory access patterns "super-fast computing" and "high-performance computing" are essentially synonyms for "massively-parallel computing."
Star-Free Languages are Church-Rosser Congruential
Venue: arXiv cs.FL 2011
Year: 2011

The class of Church-Rosser congruential languages has been introduced by McNaughton, Narendran, and Otto in 1988. A language L is Church-Rosser congruential (belongs to CRCL), if there is a finite, confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S. To date, it is still open whether every regular language is in CRCL. In this paper, we show that every star-free language is in CRCL. In fact, we prove a stronger statement: For every star-free language L there exists a finite, confluent, and subword-reducing semi-Thue system S such that the total number of congruence classes modulo S is finite and such that L is a union of congruence classes modulo S. The construction turns out to be effective.
Incentive Mechanisms for Hierarchical Spectrum Markets
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we study spectrum allocation mechanisms in hierarchical multi-layer markets which are expected to proliferate in the near future based on the current spectrum policy reform proposals. We consider a setting where a state agency sells spectrum channels to Primary Operators (POs) who subsequently resell them to Secondary Operators (SOs) through auctions. We show that these hierarchical markets do not result in a socially efficient spectrum allocation which is aimed by the agency, due to lack of coordination among the entities in different layers and the inherently selfish revenue-maximizing strategy of POs. In order to reconcile these opposing objectives, we propose an incentive mechanism which aligns the strategy and the actions of the POs with the objective of the agency, and thus leads to system performance improvement in terms of social welfare. This pricing-based scheme constitutes a method for hierarchical market regulation. A basic component of the proposed incentive mechanism is a novel auction scheme which enables POs to allocate their spectrum by balancing their derived revenue and the welfare of the SOs.
A Low-Energy Fast Cyber Foraging Mechanism for Mobile Devices
Venue: arXiv cs.DC 2011
Year: 2011

The ever increasing demands for using resource-constrained mobile devices for running more resource intensive applications nowadays has initiated the development of cyber foraging solutions that offload parts or whole computational intensive tasks to more powerful surrogate stationary computers and run them on behalf of mobile devices as required. The choice of proper mix of mobile devices and surrogates has remained an unresolved challenge though. In this paper, we propose a new decision-making mechanism for cyber foraging systems to select the best locations to run an application, based on context metrics such as the specifications of surrogates, the specifications of mobile devices, application specification, and communication network specification. Experimental results show faster response time and lower energy consumption of benched applications compared to when applications run wholly on mobile devices and when applications are offloaded to surrogates blindly for execution.
Non-monotony and Boolean automata networks
Venue: arXiv cs.DM 2011
Year: 2011

This paper aims at setting the keystone of a prospective theoretical study on the role of non-monotone interactions in biological regulation networks. Focusing on discrete models of these networks, namely, Boolean automata networks, we propose to analyse the contribution of non-monotony to the diversity and complexity in their dynamical behaviours. More precisely, in this paper, we start by detailing some motivations, both mathematical and biological, for our interest in non-monotony, and we discuss how it may account for phenomena that cannot be produced by monotony only. Then, to build some understanding in this direction, we propose some preliminary results on the dynamical behaviour of some specific non-monotone Boolean automata networks called XOR circulant networks.
Information Theoretic Exemplification of the Impact of Transmitter-Receiver Cognition on the Channel Capacity
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study, information theoretically, the impact of transmitter and or receiver cognition on the channel capacity. The cognition can be described by state information, dependent on the channel noise and or input. Specifically, as a new idea, we consider the receiver cognition as a state information dependent on the noise and we derive a capacity theorem based on the Gaussian version of the Cover-Chiang capacity theorem for two-sided state information channel. As intuitively expected, the receiver cognition increases the channel capacity and our theorem shows this increase quantitatively. Also, our capacity theorem includes the famous Costa theorem as its special cases.
Program Understanding: A Reengineering Case for the Transformation Tool Contest
Venue: arXiv cs.SE 2011
Year: 2011

In Software Reengineering, one of the central artifacts is the source code of the legacy system in question. In fact, in most cases it is the only definitive artifact, because over the time the code has diverged from the original architecture and design documents. The first task of any reengineering project is to gather an understanding of the system's architecture. Therefore, a common approach is to use parsers to translate the source code into a model conforming to the abstract syntax of the programming language the system is implemented in which can then be subject to querying. Despite querying, transformations can be used to generate more abstract views on the system's architecture. This transformation case deals with the creation of a state machine model out of a Java syntax graph. It is derived from a task that originates from a real reengineering project.
HelloWorld! An Instructive Case for the Transformation Tool Contest
Venue: arXiv cs.SE 2011
Year: 2011

This case comprises several primitive tasks that can be solved straight away with most transformation tools. The aim is to cover the most important kinds of primitive operations on models, i.e. create, read, update and delete (CRUD). To this end, tasks such as a constant transformation, a model-to-text transformation, a very basic migration transformation or diverse simple queries or in-place operations on graphs have to be solved. The motivation for this case is that the results expectedly will be very instructive for beginners. Also, it is really hard to compare transformation languages along complex cases, because the complexity of the respective case might hide the basic language concepts and constructs.
Solving the TTC 2011 Model Migration Case with Edapt
Venue: arXiv cs.SE 2011
Year: 2011

This paper gives an overview of the Edapt solution to the GMF model migration case of the Transformation Tool Contest 2011.
Solving the TTC 2011 Model Migration Case with UML-RSDS
Venue: arXiv cs.SE 2011
Year: 2011

In this paper we apply the UML-RSDS notation and tools to the GMF model migration case study and explain how to use the UML-RSDS tools.
Solving the TTC 2011 Compiler Optimization Case with GReTL
Venue: arXiv cs.SE 2011
Year: 2011

This paper discusses the GReTL solution of the TTC 2011 Compiler Optimization case. The submitted solution covers both the constant folding task and the instruction selection task. The verifier for checking the validity of the graph is also implemented, and some additional test graphs are provided as requested by the extension.
Solving the TTC 2011 Reengineering Case with MOLA and Higher-Order Transformations
Venue: arXiv cs.PL 2011
Year: 2011

The Reengineering Case of the Transformation Tool Contest 2011 deals with automatic extraction of state machine from Java source code. The transformation task involves complex, non-local matching of model elements. This paper contains the solution of the task using model transformation language MOLA. The MOLA solution uses higher-order transformations (HOT-s) to generate a part of the required MOLA program. The described HOT approach allows creating reusable, complex model transformation libraries for generic tasks without modifying an implementation of a model transformation language. Thus model transformation users who are not the developers of the language can achieve the desired functionality more easily.
Saying Hello World with MOLA - A Solution to the TTC 2011 Instructive Case
Venue: arXiv cs.PL 2011
Year: 2011

This paper describes the solution of Hello World transformations in MOLA transformation language. Transformations implementing the task are relatively straightforward and easily inferable from the task specification. The required additional steps related to model import and export are also described.
Capacity of Multiple Unicast in Wireless Networks: A Polymatroidal Approach
Venue: arXiv cs.IT 2011
Year: 2011

A classical result in undirected wireline networks is the near optimality of routing (flow) for multiple-unicast traffic (multiple sources communicating independent messages to multiple destinations): the min cut upper bound is within a logarithmic factor of the number of sources of the max flow. In this paper we "extend" the wireline result to the wireless context. Our main result is the approximate optimality of a simple layering principle: {\em local physical-layer schemes combined with global routing}. We use the {\em reciprocity} of the wireless channel critically in this result. Our formal result is in the context of channel models for which "good" local schemes, that achieve the cut-set bound, exist (such as Gaussian MAC and broadcast channels, broadcast erasure networks, fast fading Gaussian networks). Layered architectures, common in the engineering-design of wireless networks, can have near-optimal performance if the {\em locality} over which physical-layer schemes should operate is carefully designed. Feedback is shown to play a critical role in enabling the separation between the physical and the network layers. The key technical idea is the modeling of a wireless network by an undirected "polymatroidal" network, for which we establish a max-flow min-cut approximation theorem.
Enhanced Antenna Position Implementation Over Vehicular Ad Hoc Network (VNET) In 3D Space
Venue: arXiv cs.NI 2011
Year: 2011

The technology related to networking moves wired connection to wireless connection.The basic problem concern in the wireless domain, random packet loss for the end to end connection. In this paper we show the performance and the impact of the packet loss and delay, by the bit error rate throughput etc with respect to the real world scenario vehicular ad hoc network in 3-dimension space (VANET in 3D). Over the years software development has responded to the increasing growth of wireless connectivity in developing network enabled software. In this paper we consider the real world physical problem in three dimensional wireless domain and map the problem to analytical problem . In this paper we simulate that analytic problem with respect to real world scenario by using enhanced antenna position system (EAPS) mounted over the mobile node in 3D space. In this paper we convert the real world problem into lab oriented problem by using the EAPS -system and shown the performance in wireless domain in 3 dimensional space.
A weighted message-passing algorithm to estimate volume-related properties of random polytopes
Venue: arXiv cs.DS 2011
Year: 2011

In this letter, we introduce a novel message-passing algorithm for a class of problems which can be mathematically understood as estimating volume-related properties of random polytopes. Unlike the usual approach consisting in approximating the real-valued cavity marginal distributions by a few parameters, we propose a weighted message-passing algorithm to deal with the entire function. Various alternatives of how to implement our approach are discussed and numerical results for random polytopes are compared with results using the Hit-and-Run algorithm.
Prediction Of Arrival Of Nodes In A Scale Free Network
Venue: arXiv cs.SI 2011
Year: 2011

Most of the networks observed in real life obey power-law degree distribution. It is hypothesized that the emergence of such a degree distribution is due to preferential attachment of the nodes. Barabasi-Albert model is a generative procedure that uses preferential attachment based on degree and one can use this model to generate networks with power-law degree distribution. In this model, the network is assumed to grow one node every time step. After the evolution of such a network, it is impossible for one to predict the exact order of node arrivals. We present in this article, a novel strategy to partially predict the order of node arrivals in such an evolved network. We show that our proposed method outperforms other centrality measure based approaches. We bin the nodes and predict the order of node arrivals between the bins with an accuracy of above 80%.
Reaction Automata
Venue: arXiv cs.FL 2011
Year: 2011

Reaction systems are a formal model that has been introduced to investigate the interactive behaviors of biochemical reactions. Based on the formal framework of reaction systems, we propose new computing models called reaction automata that feature (string) language acceptors with multiset manipulation as a computing mechanism, and show that reaction automata are computationally Turing universal. Further, some subclasses of reaction automata with space complexity are investigated and their language classes are compared to the ones in the Chomsky hierarchy.
Communicating Concurrent Functions
Venue: arXiv cs.SE 2011
Year: 2011

In this article we extend the framework of execution of concurrent functions on different abstract levels from previous work with communication between the concurrent functions. We classify the communications and identify problems that can occur with these communications. We present solutions for the problems based on encapsulation and abstraction to obtain correct behaviours. The result is that communication on a low level of abstraction in the form of shared memory and message passing is dealt with on an higher level of abstraction.
Coverage Related Issues in Networks
Venue: arXiv cs.NI 2011
Year: 2011

Wireless sensor networks consisting of great number of cheap and tiny sensor nodes which are used for military environment controlling, natural events recording, traffic monitoring, robot navigation, and etc. Such a networks encounter with various types of challenges like energy consumption, routing, coverage, reliability. The most significant types of these problems are coverage that originated from the nodes energy consumption constrained. In order to dominate this problem different kinds of methods has been presented where the majority of them based on theoretical methods and used unbalanced and calculated distributions. In all of the proposed methods a large numbers of nodes are used. In this paper our attempt is based on using a few numbers of sensors in order to cover the vast area of environment. We proposed an algorithm that divides the desired environment to several areas and in each of these areas by using the genetic algorithm improve the coverage. The proposed method is simulated in MATLAB software and the obtained results are compared with the existing algorithms. Results show that the presented algorithm has a substantial coverage in compare with its previous counterparts.
Analytical and Learning-Based Spectrum Sensing Time Optimization in Cognitive Radio Systems
Venue: arXiv cs.NI 2011
Year: 2011

Powerful spectrum sensing schemes enable cognitive radios (CRs) to find transmission opportunities in spectral resources allocated exclusively to the primary users. In this paper, maximizing the average throughput of a secondary user by optimizing its spectrum sensing time is formulated assuming that a prior knowledge of the presence and absence probabilities of the primary users is available. The energy consumed for finding a transmission opportunity is evaluated and a discussion on the impact of the number of the primary users on the secondary user throughput and consumed energy is presented. In order to avoid the challenges associated with the analytical method, as a second solution, a systematic neural network-based sensing time optimization approach is also proposed in this paper. The proposed adaptive scheme is able to find the optimum value of the channel sensing time without any prior knowledge or assumption about the wireless environment. The structure, performance, and cooperation of the artificial neural networks used in the proposed method are disclosed in detail and a set of illustrative simulation results is presented to validate the analytical results as well as the performance of the proposed learning-based optimization scheme.
A New Round Robin Based Scheduling Algorithm for Operating Systems: Dynamic Quantum Using the Mean Average
Venue: arXiv cs.OS 2011
Year: 2011

Round Robin, considered as the most widely adopted CPU scheduling algorithm, undergoes severe problems directly related to quantum size. If time quantum chosen is too large, the response time of the processes is considered too high. On the other hand, if this quantum is too small, it increases the overhead of the CPU. In this paper, we propose a new algorithm, called AN, based on a new approach called dynamic-time-quantum; the idea of this approach is to make the operating systems adjusts the time quantum according to the burst time of the set of waiting processes in the ready queue. Based on the simulations and experiments, we show that the new proposed algorithm solves the fixed time quantum problem and increases the performance of Round Robin.