OpenRaiser/Intern-Atlas huggingface dataset:
Effective Characterizations of Simple Fragments of Temporal Logic Using Carton--Michel Automata
Venue: arXiv cs.FL 2013
Year: 2013

We present a framework for obtaining effective characterizations of simple fragments of future temporal logic (LTL) with the natural numbers as time domain. The framework is based on a form of strongly unambiguous automata, also known as prophetic automata or complete unambiguous Büchi automata and referred to as Carton-Michel automata in this paper. These automata enjoy strong structural properties, in particular, they separate the "finitary fraction" of a regular language of infinite words from its "infinitary fraction" in a natural fashion. Within our framework, we provide characterizations of several natural fragments of temporal logic, where, in some cases, no effective characterization had been known previously, and give lower and upper bounds for their computational complexity.
Real-Time Vector Automata
Venue: arXiv cs.FL 2013
Year: 2013

We study the computational power of real-time finite automata that have been augmented with a vector of dimension k, and programmed to multiply this vector at each step by an appropriately selected $k \times k$ matrix. Only one entry of the vector can be tested for equality to 1 at any time. Classes of languages recognized by deterministic, nondeterministic, and "blind" versions of these machines are studied and compared with each other, and the associated classes for multicounter automata, automata with multiplication, and generalized finite automata.
Machine learning of hierarchical clustering to segment 2D and 3D images
Venue: arXiv cs.CV 2013
Year: 2013

We aim to improve segmentation through the use of machine learning tools during region agglomeration. We propose an active learning approach for performing hierarchical agglomerative segmentation from superpixels. Our method combines multiple features at all scales of the agglomerative process, works for data with an arbitrary number of dimensions, and scales to very large datasets. We advocate the use of variation of information to measure segmentation accuracy, particularly in 3D electron microscopy (EM) images of neural tissue, and using this metric demonstrate an improvement over competing algorithms in EM and natural images.
A hybrid bat algorithm
Venue: arXiv cs.NE 2013
Year: 2013

Swarm intelligence is a very powerful technique to be used for optimization purposes. In this paper we present a new swarm intelligence algorithm, based on the bat algorithm. The Bat algorithm is hybridized with differential evolution strategies. Besides showing very promising results of the standard benchmark functions, this hybridization also significantly improves the original bat algorithm.
Extracting the information backbone in online system
Venue: arXiv cs.IR 2013
Year: 2013

Information overload is a serious problem in modern society and many solutions such as recommender system have been proposed to filter out irrelevant information. In the literature, researchers mainly dedicated to improve the recommendation performance (accuracy and diversity) of the algorithms while overlooked the influence of topology of the online user-object bipartite networks. In this paper, we find that some information provided by the bipartite networks is not only redundant but also misleading. With such "less can be more" feature, we design some algorithms to improve the recommendation performance by eliminating some links from the original networks. Moreover, we propose a hybrid method combining the time-aware and topology-aware link removal algorithms to extract the backbone which contains the essential information for the recommender systems. From the practical point of view, our method can improve the performance and reduce the computational time of the recommendation system, thus improve both of their effectiveness and efficiency.
Information Measures for Deterministic Input-Output Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this work the information loss in deterministic, memoryless systems is investigated by evaluating the conditional entropy of the input random variable given the output random variable. It is shown that for a large class of systems the information loss is finite, even if the input is continuously distributed. Based on this finiteness, the problem of perfectly reconstructing the input is addressed and Fano-type bounds between the information loss and the reconstruction error probability are derived. For systems with infinite information loss a relative measure is defined and shown to be tightly related to Rényi information dimension. Employing another Fano-type argument, the reconstruction error probability is bounded by the relative information loss from below. In view of developing a system theory from an information-theoretic point-of-view, the theoretical results are illustrated by a few example systems, among them a multi-channel autocorrelation receiver.
Feasible combinatorial matrix theory
Venue: arXiv cs.LO 2013
Year: 2013

We show that the well-known Konig's Min-Max Theorem (KMM), a fundamental result in combinatorial matrix theory, can be proven in the first order theory $\LA$ with induction restricted to $Σ_1^B$ formulas. This is an improvement over the standard textbook proof of KMM which requires $Π_2^B$ induction, and hence does not yield feasible proofs --- while our new approach does. $\LA$ is a weak theory that essentially captures the ring properties of matrices; however, equipped with $Σ_1^B$ induction $\LA$ is capable of proving KMM, and a host of other combinatorial properties such as Menger's, Hall's and Dilworth's Theorems. Therefore, our result formalizes Min-Max type of reasoning within a feasible framework.
An N-dimensional approach towards object based classification of remotely sensed imagery
Venue: arXiv cs.CV 2013
Year: 2013

Remote sensing techniques are widely used for land cover classification and urban analysis. The availability of high resolution remote sensing imagery limits the level of classification accuracy attainable from pixel-based approach. In this paper object-based classification scheme based on a hierarchical support vector machine is introduced. By combining spatial and spectral information, the amount of overlap between classes can be decreased; thereby yielding higher classification accuracy and more accurate land cover maps. We have adopted certain automatic approaches based on the advanced techniques as Cellular automata and Genetic Algorithm for kernel and tuning parameter selection. Performance evaluation of the proposed methodology in comparison with the existing approaches is performed with reference to the Bhopal city study area.
Revisiting the Equivalence Problem for Finite Multitape Automata
Venue: arXiv cs.FL 2013
Year: 2013

The decidability of determining equivalence of deterministic multitape automata (or transducers) was a longstanding open problem until it was resolved by Harju and Karhumäki in the early 1990s. Their proof of decidability yields a co_NP upper bound, but apparently not much more is known about the complexity of the problem. In this paper we give an alternative proof of decidability, which follows the basic strategy of Harju and Karhumaki but replaces their use of group theory with results on matrix algebras. From our proof we obtain a simple randomised algorithm for deciding language equivalence of deterministic multitape automata and, more generally, multiplicity equivalence of nondeterministic multitape automata. The algorithm involves only matrix exponentiation and runs in polynomial time for each fixed number of tapes. If the two input automata are inequivalent then the algorithm outputs a word on which they differ.
Matchgates Revisited
Venue: arXiv cs.CC 2013
Year: 2013

We study a collection of concepts and theorems that laid the foundation of matchgate computation. This includes the signature theory of planar matchgates, and the parallel theory of characters of not necessarily planar matchgates. Our aim is to present a unified and, whenever possible, simplified account of this challenging theory. Our results include: (1) A direct proof that Matchgate Identities (MGI) are necessary and sufficient conditions for matchgate signatures. This proof is self-contained and does not go through the character theory. More importantly it rectifies a gap in the existing proof. (2) A proof that Matchgate Identities already imply the Parity Condition. (3) A simplified construction of a crossover gadget. This is used in the proof of sufficiency of MGI for matchgate signatures. This is also used to give a proof of equivalence between the signature theory and the character theory which permits omittable nodes. (4) A direct construction of matchgates realizing all matchgate-realizable symmetric signatures.
A Federated CloudNet Architecture: The PIP and the VNP Role
Venue: arXiv cs.NI 2013
Year: 2013

We present a generic and flexible architecture to realize CloudNets: virtual networks connecting cloud resources with resource guarantees. Our architecture is federated and supports different (and maybe even competing) economical roles, by providing explicit negotiation and provisioning interfaces. Contract-based interactions and a resource description language that allows for aggregation and abstraction, preserve the different roles' autonomy without sacrificing flexibility. Moreover, since our CloudNet architecture is plugin based, essentially all cloud operating systems (e.g., OpenStack) or link technologies (e.g., VLANs, OpenFlow, VPLS) can be used within the framework. This paper describes two roles in more detail: The Physical Infrastructure Providers (PIP) which own the substrate network and resources, and the Virtual Network Providers (VNP) which can act as resource and CloudNet brokers and resellers. Both roles are fully implemented in our wide-area prototype that spans remote sites and resources.
Modeling the interdependency of low-priority congestion control and active queue management
Venue: arXiv cs.NI 2013
Year: 2013

Recently, a negative interplay has been shown to arise when scheduling/AQM techniques and low-priority congestion control protocols are used together: namely, AQM resets the relative level of priority among congestion control protocols. This work explores this issue by (i) studying a fluid model that describes system dynamics of heterogeneous congestion control protocols competing on a bottleneck link governed by AQM and (ii) proposing a system level solution able to reinstate priorities among protocols.
Multi-sample Receivers Increase Information Rates for Wiener Phase Noise Channels
Venue: arXiv cs.IT 2013
Year: 2013

A waveform channel is considered where the transmitted signal is corrupted by Wiener phase noise and additive white Gaussian noise (AWGN). A discrete-time channel model is introduced that is based on a multi-sample receiver. Tight lower bounds on the information rates achieved by the multi-sample receiver are computed by means of numerical simulations. The results show that oversampling at the receiver is beneficial for both strong and weak phase noise at high signal-to-noise ratios. The results are compared with results obtained when using other discrete-time models.
Scalable peer-to-peer streaming for live entertainment content
Venue: arXiv cs.NI 2013
Year: 2013

We present a system for streaming live entertainment content over the Internet originating from a single source to a scalable number of consumers without resorting to centralised or provider- provisioned resources. The system creates a peer-to-peer overlay network, which attempts to optimise use of existing capacity to ensure quality of service, delivering low start-up delay and lag in playout of the live content. There are three main aspects of our solution. Firstly, a swarming mechanism that constructs an overlay topology for minimising propagation delays from the source to end consumers. Secondly, a distributed overlay anycast system that uses a location-based search algorithm for peers to quickly find the closest peers in a given stream. Finally, a novel incentives mechanism that encourages peers to donate capacity even when the user is not actively consuming content.
The development of the architecture of Distributed Network Intrusion Detection System (D-NIDS)
Venue: arXiv cs.CR 2013
Year: 2013

This paper presents the development of the architecture of Distributed Network Intrusion Detection System.
A Partial Decode-Forward Scheme For A Network with N relays
Venue: arXiv cs.IT 2013
Year: 2013

We study a discrete-memoryless relay network consisting of one source, one destination and N relays, and design a scheme based on partial decode-forward relaying. The source splits its message into one common and N+1 private parts, one intended for each relay. It encodes these message parts using Nth-order block Markov coding, in which each private message part is independently superimposed on the common parts of the current and N previous blocks. Using simultaneous sliding window decoding, each relay fully recovers the common message and its intended private message with the same block index, then forwards them to the following nodes in the next block. This scheme can be applied to any network topology. We derive its achievable rate in a compact form. The result reduces to a known decode-forward lower bound for an N-relay network and partial decode-forward lower bound for a two-level relay network. We then apply the scheme to a Gaussian two-level relay network and obtain its capacity lower bound considering power constraints at the transmitting nodes.
Bipolar Fuzzy Soft sets and its applications in decision making problem
Venue: arXiv cs.AI 2013
Year: 2013

In this article, we combine the concept of a bipolar fuzzy set and a soft set. We introduce the notion of bipolar fuzzy soft set and study fundamental properties. We study basic operations on bipolar fuzzy soft set. We define exdended union, intersection of two bipolar fuzzy soft set. We also give an application of bipolar fuzzy soft set into decision making problem. We give a general algorithm to solve decision making problems by using bipolar fuzzy soft set.
A Massively Parallel Associative Memory Based on Sparse Neural Networks
Venue: arXiv cs.AI 2013
Year: 2013

Associative memories store content in such a way that the content can be later retrieved by presenting the memory with a small portion of the content, rather than presenting the memory with an address as in more traditional memories. Associative memories are used as building blocks for algorithms within database engines, anomaly detection systems, compression algorithms, and face recognition systems. A classical example of an associative memory is the Hopfield neural network. Recently, Gripon and Berrou have introduced an alternative construction which builds on ideas from the theory of error correcting codes and which greatly outperforms the Hopfield network in capacity, diversity, and efficiency. In this paper we implement a variation of the Gripon-Berrou associative memory on a general purpose graphical processing unit (GPU). The work of Gripon and Berrou proposes two retrieval rules, sum-of-sum and sum-of-max. The sum-of-sum rule uses only matrix-vector multiplication and is easily implemented on the GPU. The sum-of-max rule is much less straightforward to implement because it involves non-linear operations. However, the sum-of-max rule gives significantly better retrieval error rates. We propose a hybrid rule tailored for implementation on a GPU which achieves a 880-fold speedup without sacrificing any accuracy.
Energy Efficient Cooperative Strategies for Relay-Assisted Downlink Cellular Systems Part II: Practical Design
Venue: arXiv cs.IT 2013
Year: 2013

In a companion paper [1], we present a general approach to evaluate the impact of cognition in a downlink cellular system in which multiple relays assist the transmission of the base station. This approach is based on a novel theoretical tool which produces transmission schemes involving rate-splitting, superposition coding and interference decoding for a network with any number of relays and receivers. This second part focuses on a practical design example for a network in which a base station transmits to three receivers with the aid of two relay nodes. For this simple network, we explicitly evaluate the impact of relay cognition and precisely characterize the trade offs between the total energy consumption and the rate improvements provided by relay cooperation. These closedform expressions provide important insights on the role of cognition in larger networks and highlights interesting interference management strategies. We also present a numerical simulation setup in which we fully automate the derivation of achievable rate region for a general relay-assisted downlink cellular network. Our simulations clearly show the great advantages provided by cooperative strategies at the relays as compared to the uncoordinated scenario under varying channel conditions and target rates. These results are obtained by considering a large number of transmission strategies for different levels of relay cognition and numerically determining one that is the most energy efficient. The limited computational complexity of the numerical evaluations makes this approach suitable for the optimization of transmission strategies for larger networks.
Joint Resource Partitioning and Offloading in Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2013
Year: 2013

In heterogeneous cellular networks (HCNs), it is desirable to offload mobile users to small cells, which are typically significantly less congested than the macrocells. To achieve sufficient load balancing, the offloaded users often have much lower SINR than they would on the macrocell. This SINR degradation can be partially alleviated through interference avoidance, for example time or frequency resource partitioning, whereby the macrocell turns off in some fraction of such resources. Naturally, the optimal offloading strategy is tightly coupled with resource partitioning; the optimal amount of which in turn depends on how many users have been offloaded. In this paper, we propose a general and tractable framework for modeling and analyzing joint resource partitioning and offloading in a two-tier cellular network. With it, we are able to derive the downlink rate distribution over the entire network, and an optimal strategy for joint resource partitioning and offloading. We show that load balancing, by itself, is insufficient, and resource partitioning is required in conjunction with offloading to improve the rate of cell edge users in co-channel heterogeneous networks.
Smart Cities Software from the developer's point of view
Venue: arXiv cs.CY 2013
Year: 2013

The paper discusses the current state and development proposals for Smart Cities and Future Internet projects. Definitions of a Smart City can vary but usually tend to suggest the use of innovative Info-Communication technologies such as the Internet of Things and Web 2.0 to deliver more effective and efficient public services that improve living and working conditions and create more sustainable urban environments. Our goal is to analyze the current proposals from the developer's point of view, highlight the really new elements, the positions borrowed from the existing tools as well as propose some new extensions. We would like to discuss the possible extensions for the existing proposals and describe add-ons that, by our opinion, let keep the future research inline with the modern approaches in the web development domain.
Efficient Construction of Spanners in $d$-Dimensions
Venue: arXiv cs.CG 2013
Year: 2013

In this paper we consider the problem of efficiently constructing $k$-vertex fault-tolerant geometric $t$-spanners in $\dspace$ (for $k \ge 0$ and $t >1$). Vertex fault-tolerant spanners were introduced by Levcopoulus et. al in 1998. For $k=0$, we present an $O(n \log n)$ method using the algebraic computation tree model to find a $t$-spanner with degree bound O(1) and weight $O(\weight(MST))$. This resolves an open problem. For $k \ge 1$, we present an efficient method that, given $n$ points in $\dspace$, constructs $k$-vertex fault-tolerant $t$-spanners with the maximum degree bound O(k) and weight bound $O(k^2 \weight(MST))$ in time $O(n \log n)$. Our method achieves the best possible bounds on degree, total edge length, and the time complexity, and solves the open problem of efficient construction of (fault-tolerant) $t$-spanners in $\dspace$ in time $O(n \log n)$.
On Mobile DNA in Artificial Regulatory Networks: Evolving Functional and Structural Dynamism
Venue: arXiv cs.ET 2013
Year: 2013

There is a growing body of work considering the use of representations based upon genetic regulatory networks. This paper uses a recently presented abstract, tunable Boolean regulatory network model to explore aspects of mobile DNA, such as transposons, within these dynamical systems. The significant role of mobile DNA in the evolution of natural systems is becoming increasingly clear. Whilst operators loosely based upon transposons have previously been used within evolutionary computation, their use within regulatory network representations enables the potential exploitation of numerous new mechanisms. This paper shows how dynamically controlling network node connectivity and function via transposon-inspired mechanisms can be selected for under non-stationary and coevolutionary scenarios, including when such changes are heritable.
On Constellations for Physical Layer Network Coded Two-Way Relaying
Venue: arXiv cs.IT 2013
Year: 2013

Modulation schemes for two-way bidirectional relay network employing two phases: Multiple access (MA) phase and Broadcast (BC) phase and using physical layer network coding are currently studied intensively. Recently, adaptive modulation schemes using Latin Squares to obtain network coding maps with the denoise and forward protocol have been reported with good end-to-end performance. These schemes work based on avoiding the detrimental effects of distance shortening in the effective receive constellation at the end of the MA phase at the relay. The channel fade states that create such distance shortening called singular fade states, are effectively removed using appropriate Latin squares. This scheme as well as all other known schemes studied so far use conventional regular PSK or QAM signal sets for the end users which lead to the relay using different sized constellations for the BC phase depending upon the fade state. In this work, we propose a 4-point signal set that would always require a 4-ary constellation for the BC phase for all the channel fade conditions. We also propose an 8-point constellation that gives better SER performance (gain of 1 dB) than 8-PSK while still using 8-ary constellation for BC phase like the case with 8-PSK. This is in spite of the fact that the proposed 8-point signal set has more number of singular fade states than for 8-PSK.
Evaluating Reputation Systems for Agent Mediated e-Commerce
Venue: arXiv cs.MA 2013
Year: 2013

Agent mediated e-commerce involves buying and selling on Internet through software agents. The success of an agent mediated e-commerce system lies in the underlying reputation management system which is used to improve the quality of services in e-market environment. A reputation system encourages the honest behaviour of seller agents and discourages the malicious behaviour of dishonest seller agents in the e-market where actual traders never meet each other. This paper evaluates various reputation systems for assigning reputation rating to software agents acting on behalf of buyers and sellers in e-market. These models are analysed on the basis of a number of features viz. reputation computation and their defence mechanisms against different attacks. To address the problems of traditional reputation systems which are relatively static in nature, this paper identifies characteristics of a dynamic reputation framework which ensures judicious use of information sharing for inter-agent cooperation and also associates the reputation of an agent with the value of a transaction so that the market approaches an equilibrium state and dishonest agents are weeded out of the market.