OpenRaiser/Intern-Atlas huggingface dataset:
Weighted Max-Min Resource Allocation for Frequency Selective Channels
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we discuss the computation of weighted max-min rate allocation using joint TDM/FDM strategies under a PSD mask constraint. We show that the weighted max-min solution allocates the rates according to a predetermined rate ratio defined by the weights, a fact that is very valuable for telecommunication service providers. Furthermore, we show that the problem can be efficiently solved using linear programming. We also discuss the resource allocation problem in the mixed services scenario where certain users have a required rate, while the others have flexible rate requirements. The solution is relevant to many communication systems that are limited by a power spectral density mask constraint such as WiMax, Wi-Fi and UWB.
Semi-Supervised Kernel PCA
Venue: arXiv cs.LG 2010
Year: 2010

We present three generalisations of Kernel Principal Components Analysis (KPCA) which incorporate knowledge of the class labels of a subset of the data points. The first, MV-KPCA, penalises within class variances similar to Fisher discriminant analysis. The second, LSKPCA is a hybrid of least squares regression and kernel PCA. The final LR-KPCA is an iteratively reweighted version of the previous which achieves a sigmoid loss function on the labeled points. We provide a theoretical risk bound as well as illustrative experiments on real and toy data sets.
On a game theoretic approach to capacity maximization in wireless networks
Venue: arXiv cs.DS 2010
Year: 2010

We consider the capacity problem (or, the single slot scheduling problem) in wireless networks. Our goal is to maximize the number of successful connections in arbitrary wireless networks where a transmission is successful only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. We study a game theoretic approach towards capacity maximization introduced by Andrews and Dinitz (INFOCOM 2009) and Dinitz (INFOCOM 2010). We prove vastly improved bounds for the game theoretic algorithm. In doing so, we achieve the first distributed constant factor approximation algorithm for capacity maximization for the uniform power assignment. When compared to the optimum where links may use an arbitrary power assignment, we prove a $O(\log Δ)$ approximation, where $Δ$ is the ratio between the largest and the smallest link in the network. This is an exponential improvement of the approximation factor compared to existing results for distributed algorithms. All our results work for links located in any metric space. In addition, we provide simulation studies clarifying the picture on distributed algorithms for capacity maximization.
Linear Size Optimal q-ary Constant-Weight Codes and Constant-Composition Codes
Venue: arXiv cs.IT 2010
Year: 2010

An optimal constant-composition or constant-weight code of weight $w$ has linear size if and only if its distance $d$ is at least $2w-1$. When $d\geq 2w$, the determination of the exact size of such a constant-composition or constant-weight code is trivial, but the case of $d=2w-1$ has been solved previously only for binary and ternary constant-composition and constant-weight codes, and for some sporadic instances. This paper provides a construction for quasicyclic optimal constant-composition and constant-weight codes of weight $w$ and distance $2w-1$ based on a new generalization of difference triangle sets. As a result, the sizes of optimal constant-composition codes and optimal constant-weight codes of weight $w$ and distance $2w-1$ are determined for all such codes of sufficiently large lengths. This solves an open problem of Etzion. The sizes of optimal constant-composition codes of weight $w$ and distance $2w-1$ are also determined for all $w\leq 6$, except in two cases.
Optimal Partitioned Cyclic Difference Packings for Frequency Hopping and Code Synchronization
Venue: arXiv cs.IT 2010
Year: 2010

Optimal partitioned cyclic difference packings (PCDPs) are shown to give rise to optimal frequency-hopping sequences and optimal comma-free codes. New constructions for PCDPs, based on almost difference sets and cyclic difference matrices, are given. These produce new infinite families of optimal PCDPs (and hence optimal frequency-hopping sequences and optimal comma-free codes). The existence problem for optimal PCDPs in ${\mathbb Z}_{3m}$, with $m$ base blocks of size three, is also solved for all $m\not\equiv 8,16\pmod{24}$.
Survey of Search and Replication Schemes in Unstructured P2P Networks
Venue: arXiv cs.NI 2010
Year: 2010

P2P computing lifts taxing issues in various areas of computer science. The largely used decentralized unstructured P2P systems are ad hoc in nature and present a number of research challenges. In this paper, we provide a comprehensive theoretical survey of various state-of-the-art search and replication schemes in unstructured P2P networks for file-sharing applications. The classifications of search and replication techniques and their advantages and disadvantages are briefly explained. Finally, the various issues on searching and replication for unstructured P2P networks are discussed.
Accepting Hybrid Networks of Evolutionary Processors with Special Topologies and Small Communication
Venue: arXiv cs.CC 2010
Year: 2010

Starting from the fact that complete Accepting Hybrid Networks of Evolutionary Processors allow much communication between the nodes and are far from network structures used in practice, we propose in this paper three network topologies that restrict the communication: star networks, ring networks, and grid networks. We show that ring-AHNEPs can simulate 2-tag systems, thus we deduce the existence of a universal ring-AHNEP. For star networks or grid networks, we show a more general result; that is, each recursively enumerable language can be accepted efficiently by a star- or grid-AHNEP. We also present bounds for the size of these star and grid networks. As a consequence we get that each recursively enumerable can be accepted by networks with at most 13 communication channels and by networks where each node communicates with at most three other nodes.
Representing Small Ordinals by Finite Automata
Venue: arXiv cs.FL 2010
Year: 2010

It is known that an ordinal is the order type of the lexicographic ordering of a regular language if and only if it is less than omega^omega. We design a polynomial time algorithm that constructs, for each well-ordered regular language L with respect to the lexicographic ordering, given by a deterministic finite automaton, the Cantor Normal Form of its order type. It follows that there is a polynomial time algorithm to decide whether two deterministic finite automata accepting well-ordered regular languages accept isomorphic languages. We also give estimates on the size of the smallest automaton representing an ordinal less than omega^omega, together with an algorithm that translates each such ordinal to an automaton.
Transition Complexity of Incomplete DFAs
Venue: arXiv cs.FL 2010
Year: 2010

In this paper, we consider the transition complexity of regular languages based on the incomplete deterministic finite automata. A number of results on Boolean operations have been obtained. It is shown that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity result is similar to that of state complexity.
The Magic Number Problem for Subregular Language Families
Venue: arXiv cs.FL 2010
Year: 2010

We investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has alpha states, for all n and alpha satisfying n less or equal to alpha less or equal to exp(2,n). A number alpha not satisfying this condition is called a magic number (for n). It was shown in [11] that no magic numbers exist for general regular languages, while in [5] trivial and non-trivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, combinational languages, star-free, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages, showing that there are only trivial magic numbers, when they exist. For finite languages we obtain some partial results showing that certain numbers are non-magic.
Ciliate Gene Unscrambling with Fewer Templates
Venue: arXiv cs.FL 2010
Year: 2010

One of the theoretical models proposed for the mechanism of gene unscrambling in some species of ciliates is the template-guided recombination (TGR) system by Prescott, Ehrenfeucht and Rozenberg which has been generalized by Daley and McQuillan from a formal language theory perspective. In this paper, we propose a refinement of this model that generates regular languages using the iterated TGR system with a finite initial language and a finite set of templates, using fewer templates and a smaller alphabet compared to that of the Daley-McQuillan model. To achieve Turing completeness using only finite components, i.e., a finite initial language and a finite set of templates, we also propose an extension of the contextual template-guided recombination system (CTGR system) by Daley and McQuillan, by adding an extra control called permitting contexts on the usage of templates.
On the Descriptional Complexity of Limited Propagating Lindenmayer Systems
Venue: arXiv cs.FL 2010
Year: 2010

We investigate the descriptional complexity of limited propagating Lindenmayer systems and their deterministic and tabled variants with respect to the number of rules and the number of symbols. We determine the decrease of complexity when the generative capacity is increased. For incomparable families, we give languages that can be described more efficiently in either of these families than in the other.
On Maxwell fluid with relaxation time and viscosity depending on the pressure
Venue: arXiv cs.NA 2010
Year: 2010

We study a variant of the well known Maxwell model for viscoelastic fluids, namely we consider the Maxwell fluid with viscosity and relaxation time depending on the pressure. Such a model is relevant for example in modelling behaviour of some polymers and geomaterials. Although it is experimentally known that the material moduli of some viscoelastic fluids can depend on the pressure, most of the studies concerning the motion of viscoelastic fluids do not take such effects into account despite their possible practical significance in technological applications. Using a generalized Maxwell model with pressure dependent material moduli we solve a simple boundary value problem and we demonstrate interesting non-classical features exhibited by the model.
The Shannon Cipher System with a Guessing Wiretapper: General Sources
Venue: arXiv cs.IT 2010
Year: 2010

The Shannon cipher system is studied in the context of general sources using a notion of computational secrecy introduced by Merhav & Arikan. Bounds are derived on limiting exponents of guessing moments for general sources. The bounds are shown to be tight for iid, Markov, and unifilar sources, thus recovering some known results. A close relationship between error exponents and correct decoding exponents for fixed rate source compression on the one hand and exponents for guessing moments on the other hand is established.
Congruence from the Operator's Point of View: Compositionality Requirements on Process Semantics
Venue: arXiv cs.LO 2010
Year: 2010

One of the basic sanity properties of a behavioural semantics is that it constitutes a congruence with respect to standard process operators. This issue has been traditionally addressed by the development of rule formats for transition system specifications that define process algebras. In this paper we suggest a novel, orthogonal approach. Namely, we focus on a number of process operators, and for each of them attempt to find the widest possible class of congruences. To this end, we impose restrictions on sublanguages of Hennessy-Milner logic, so that a semantics whose modal characterization satisfies a given criterion is guaranteed to be a congruence with respect to the operator in question. We investigate action prefix, alternative composition, two restriction operators, and parallel composition.
Resumptions, Weak Bisimilarity and Big-Step Semantics for While with Interactive I/O: An Exercise in Mixed Induction-Coinduction
Venue: arXiv cs.LO 2010
Year: 2010

We look at the operational semantics of languages with interactive I/O through the glasses of constructive type theory. Following on from our earlier work on coinductive trace-based semantics for While, we define several big-step semantics for While with interactive I/O, based on resumptions and termination-sensitive weak bisimilarity. These require nesting inductive definitions in coinductive definitions, which is interesting both mathematically and from the point-of-view of implementation in a proof assistant. After first defining a basic semantics of statements in terms of resumptions with explicit internal actions (delays), we introduce a semantics in terms of delay-free resumptions that essentially removes finite sequences of delays on the fly from those resumptions that are responsive. Finally, we also look at a semantics in terms of delay-free resumptions supplemented with a silent divergence option. This semantics hinges on decisions between convergence and divergence and is only equivalent to the basic one classically. We have fully formalized our development in Coq.
Secret Key and Private Key Constructions for Simple Multiterminal Source Models
Venue: arXiv cs.IT 2010
Year: 2010

We propose an approach for constructing secret and private keys based on the long-known Slepian-Wolf code, due to Wyner, for correlated sources connected by a virtual additive noise channel. Our work is motivated by results of Csiszár and Narayan which highlight innate connections between secrecy generation by multiple terminals that observe correlated source signals and Slepian-Wolf near-lossless data compression. Explicit procedures for such constructions and their substantiation are provided. The performance of low density parity check channel codes in devising a new class of secret keys is examined.
Benchmarking the True Random Number Generator of TPM Chips
Venue: arXiv cs.CR 2010
Year: 2010

A TPM (trusted platform module) is a chip present mostly on newer motherboards, and its primary function is to create, store and work with cryptographic keys. This dedicated chip can serve to authenticate other devices or to protect encryption keys used by various software applications. Among other features, it comes with a True Random Number Generator (TRNG) that can be used for cryptographic purposes. This random number generator consists of a state machine that mixes unpredictable data with the output of a one way hash function. According the specification it can be a good source of unpredictable random numbers even without having to require a genuine source of hardware entropy. However the specification recommends collecting entropy from any internal sources available such as clock jitter or thermal noise in the chip itself, a feature that was implemented by most manufacturers. This paper will benchmark the random number generator of several TPM chips from two perspectives: the quality of the random bit sequences generated, as well as the output bit rate.
Symmetry and Uncountability of Computation
Venue: arXiv cs.CC 2010
Year: 2010

This paper talk about the complexity of computation by Turing Machine. I take attention to the relation of symmetry and order structure of the data, and I think about the limitation of computation time. First, I make general problem named "testing problem". And I get some condition of the P complete and NP complete by using testing problem. Second, I make two problem "orderly problem" and "chaotic problem". Orderly problem have some order structure. And DTM can limit some possible symbol effectly by using symmetry of each symbol. But chaotic problem must treat some symbol as a set of symbol, so DTM cannot limit some possible symbol. Orderly problem is P complete, and chaotic problem is NP complete. Finally, I clear the computation time of orderly problem and chaotic problem. And P != NP.
Application Neutrality and a Paradox of Side Payments
Venue: arXiv cs.NI 2010
Year: 2010

The ongoing debate over net neutrality covers a broad set of issues related to the regulation of public networks. In two ways, we extend an idealized usage-priced game-theoretic framework based on a common linear demand-response model. First, we study the impact of "side payments" among a plurality of Internet service (access) providers and content providers. In the non-monopolistic case, our analysis reveals an interesting "paradox" of side payments in that overall revenues are reduced for those that receive them. Second, assuming different application types (e.g., HTTP web traffic, peer-to-peer file sharing, media streaming, interactive VoIP), we extend this model to accommodate differential pricing among them in order to study the issue of application neutrality. Revenues for neutral and non-neutral pricing are compared for the case of two application types.
Trident, a new pseudo random number generator based on coupled chaotic maps
Venue: arXiv cs.CR 2010
Year: 2010

This article describes a new family of cryptographically secure pseudorandom number generators, based on coupled chaotic maps, that will serve as keystream in a stream cipher. The maps are a modification of a piecewise linear map, by dynamic changing of the coefficient values and perturbing its lesser significant bits.
Discover & eXplore Neural Network (DXNN) Platform, a Modular TWEANN
Venue: arXiv cs.NE 2010
Year: 2010

In this paper I present a novel type of Topology and Weight Evolving Artificial Neural Network (TWEANN) system called Modular Discover & eXplore Neural Network (DXNN). Modular DXNN utilizes a hierarchical/modular topology which allows for highly scalable and dynamically granular systems to evolve. Among the novel features discussed in this paper is a simple and database friendly encoding for hierarchical/modular NNs, a new selection method aimed at producing highly compact and fit individuals within the population, a "Targeted Tunning" system aimed at alleviating the curse of dimensionality, and a two phase based neuroevolutionary approach which yields high population diversity and removes the need for speciation algorithms. I will discuss DXNN's mutation operators which are aimed at improving its efficiency, expandability, and capabilities through a built in feature selection method that allows for the evolved system to expand, discover, and explore new sensors and actuators. Finally I will compare DXNN platform to other state of the art TWEANNs on a control task to demonstrate its superior ability to produce highly compact solutions faster than its competitors.
Inverse Star, Borders, and Palstars
Venue: arXiv cs.FL 2010
Year: 2010

A language L is closed if L = L*. We consider an operation on closed languages, L-*, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L-* is also regular. We show that the analogous result fails to hold for the context-free languages. Along the way we find a new relationship between the unbordered words and the prime palstars of Knuth, Morris, and Pratt. We use this relationship to enumerate the prime palstars, and we prove that neither the language of all unbordered words nor the language of all prime palstars is context-free.
Integration of Design Patterns and Mobile Applications in a Management System for Monitoring Maintenance Cathode Plates of Mining Company Quebrada Blanca SA
Venue: arXiv cs.SE 2010
Year: 2010

This document presents the integration of design patterns and mobile applications, in the development of software management of plates (SIGEP) that allows to support in the solutions to problematics that they appear in the process of maintaining of plates copper cathodes of a Mining Company, in our case for Quebrada Blanca S.A. (CMQB S.A.). These problematics mainly are related to the little control over the tasks carried out in the maintaining to the cathodic plates, and the lack of information that leads to this practice, originates a deficient management and it does not allow to make opportune decisions referring to these elements, and therefore it does to project and to administer the life utility of the plates of cathodes, generating lifted costs associated to this process. As the process of maintaining a cathode plates constantly changing process, with respect to maintenance strategies in the system design SIGEP recognizing the flexibility and reuse in the design of system components, this achieved through design patterns used. The SIGEP implementation of the system and the incorporation of a mobile application, meant for CMQB S.A. increase control of the tasks carried out plates cathodes, allowing the company to detailed information on the maintenance of these elements, allowing among other things, identify cathode plates which are more expensive, and therefore knowing what must be replaced.
Searching publications on software testing
Venue: arXiv cs.SE 2010
Year: 2010

This note concerns a search for publications in which the pragmatic concept of a test as conducted in the practice of software testing is formalized, a theory about software testing based on such a formalization is presented or it is demonstrated on the basis of such a theory that there are solid grounds to test software in cases where in principle other forms of analysis could be used. This note reports on the way in which the search has been carried out and the main outcomes of the search. The message of the note is that the fundamentals of software testing are not yet complete in some respects.
Immune System Inspired Strategies for Distributed Systems
Venue: arXiv cs.DC 2010
Year: 2010

Many components of the IS are constructed as modular units which do not need to communicate with each other such that the number of components increases but the size remains constant. However, a sub-modular IS architecture in which lymph node number and size both increase sublinearly with body size is shown to efficiently balance the requirements of communication and migration, consistent with experimental data. We hypothesize that the IS architecture optimizes the tradeoff between local search for pathogens and global response using antibodies. Similar to natural immune systems, physical space and resource are also important constraints on Artificial Immune Systems (AIS), especially distributed systems applications used to connect low-powered sensors using short-range wireless communication. AIS problems like distributed robot control will also require a sub-modular architecture to efficiently balance the tradeoff between local search for a solution and global response or proliferation of the solution between different components.
Very Well-Covered Graphs of Girth at least Four and Local Maximum Stable Set Greedoids
Venue: arXiv cs.DM 2010
Year: 2010

A \textit{maximum stable set} in a graph $G$ is a stable set of maximum cardinality. $S$ is a \textit{local maximum stable set} of $G$, and we write $S\inΨ(G)$, if $S$ is a maximum stable set of the subgraph induced by $S\cup N(S)$, where $N(S)$ is the neighborhood of $S$. Nemhauser and Trotter Jr. (1975), proved that any $S\inΨ(G)$ is a subset of a maximum stable set of $G$. In (Levit & Mandrescu, 2002) we have shown that the family $Ψ(T)$ of a forest $T$ forms a greedoid on its vertex set. The cases where $G$ is bipartite, triangle-free, well-covered, while $Ψ(G)$ is a greedoid, were analyzed in (Levit & Mandrescu, 2002),(Levit & Mandrescu, 2004),(Levit & Mandrescu, 2007), respectively. In this paper we demonstrate that if $G$ is a very well-covered graph of girth $\geq4$, then the family $Ψ(G)$ is a greedoid if and only if $G$ has a unique perfect matching.