OpenRaiser/Intern-Atlas huggingface dataset:
Graph Homomorphisms, Circular Colouring, and Fractional Covering by H-cuts
Venue: arXiv cs.DM 2009
Year: 2009

A graph homomorphism is a vertex map which carries edges from a source graph to edges in a target graph. The instances of the Weighted Maximum H-Colourable Subgraph problem (MAX H-COL) are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H; note that for H=K_k this problem is equivalent to MAX k-CUT. Farnqvist et al. have introduced a parameter on the space of graphs that allows close study of the approximability properties of MAX H-COL. Specifically, it can be used to extend previously known (in)approximability results to larger classes of graphs. Here, we investigate the properties of this parameter on circular complete graphs K_{p/q}, where 2 <= p/q <= 3. The results are extended to K_4-minor-free graphs and graphs with bounded maximum average degree. We also consider connections with Samal's work on fractional covering by cuts: we address, and decide, two conjectures concerning cubical chromatic numbers.
Characterizations of Stable Model Semantics for Logic Programs with Arbitrary Constraint Atoms
Venue: arXiv cs.AI 2009
Year: 2009

This paper studies the stable model semantics of logic programs with (abstract) constraint atoms and their properties. We introduce a succinct abstract representation of these constraint atoms in which a constraint atom is represented compactly. We show two applications. First, under this representation of constraint atoms, we generalize the Gelfond-Lifschitz transformation and apply it to define stable models (also called answer sets) for logic programs with arbitrary constraint atoms. The resulting semantics turns out to coincide with the one defined by Son et al., which is based on a fixpoint approach. One advantage of our approach is that it can be applied, in a natural way, to define stable models for disjunctive logic programs with constraint atoms, which may appear in the disjunctive head as well as in the body of a rule. As a result, our approach to the stable model semantics for logic programs with constraint atoms generalizes a number of previous approaches. Second, we show that our abstract representation of constraint atoms provides a means to characterize dependencies of atoms in a program with constraint atoms, so that some standard characterizations and properties relying on these dependencies in the past for logic programs with ordinary atoms can be extended to logic programs with constraint atoms.
Multiple-Bases Belief-Propagation Decoding of High-Density Cyclic Codes
Venue: arXiv cs.IT 2009
Year: 2009

We introduce a new method for decoding short and moderate length linear block codes with dense parity-check matrix representations of cyclic form, termed multiple-bases belief-propagation (MBBP). The proposed iterative scheme makes use of the fact that a code has many structurally diverse parity-check matrices, capable of detecting different error patterns. We show that this inherent code property leads to decoding algorithms with significantly better performance when compared to standard BP decoding. Furthermore, we describe how to choose sets of parity-check matrices of cyclic form amenable for multiple-bases decoding, based on analytical studies performed for the binary erasure channel. For several cyclic and extended cyclic codes, the MBBP decoding performance can be shown to closely follow that of maximum-likelihood decoders.
A low Complexity Wireless Gigabit Ethernet IFoF 60 GHz H/W Platform and Issues
Venue: arXiv cs.NI 2009
Year: 2009

This paper proposes a complete IFoF system architecture derived from simplified IEEE802.15.3c PHY layer proposal to successfully ensure near 1 Gbps on the air interface. The system architecture utilizes low complexity baseband processing modules. The byte/frame synchronization technique is designed to provide a high value of preamble detection probability and a very small value of the false detection probability. Conventional Reed-Solomon RS (255, 239) coding is used for Channel Forward Error Correction (FEC). Good communication link quality and Bit Error Rate (BER) results at 875 Mbps are achieved with directional antennas.
60 GHz High Data Rate Wireless Communication System
Venue: arXiv cs.NI 2009
Year: 2009

This paper presents the design and the realization of a 60 GHz wireless Gigabit Ethernet communication system. A differential encoded binary phase shift keying modulation (DBPSK) and differential demodulation schemes are adopted for the IF blocks. The Gigabit Ethernet interface allows a high speed transfer of multimedia files via a 60 GHz wireless link. First measurement results are shown for 875 Mbps data rate.
Maximum Flow in Directed Planar Graphs with Vertex Capacities
Venue: arXiv cs.DM 2009
Year: 2009

In this paper we present an O(n log n) algorithm for finding a maximum flow in a directed planar graph, where the vertices are subject to capacity constraints, in addition to the arcs. If the source and the sink are on the same face, then our algorithm can be implemented in O(n) time. For general (not planar) graphs, vertex capacities do not make the problem more difficult, as there is a simple reduction that eliminates vertex capacities. However, this reduction does not preserve the planarity of the graph. The essence of our algorithm is a different reduction that does preserve the planarity, and can be implemented in linear time. For the special case of undirected planar graph, an algorithm with the same time complexity was recently claimed, but we show that it has a flaw.
Design and Analysis of Successive Decoding with Finite Levels for the Markov Channel
Venue: arXiv cs.IT 2009
Year: 2009

This paper proposes a practical successive decoding scheme with finite levels for the finite-state Markov channels where there is no a priori state information at the transmitter or the receiver. The design employs either a random interleaver or a deterministic interleaver with an irregular pattern and an optional iterative estimation and decoding procedure within each level. The interleaver design criteria may be the achievable rate or the extrinsic information transfer (EXIT) chart, depending on the receiver type. For random interleavers, the optimization problem is solved efficiently using a pilot-utility function, while for deterministic interleavers, a good construction is given using empirical rules. Simulation results demonstrate that the new successive decoding scheme combined with irregular low-density parity-check codes can approach the identically and uniformly distributed (i.u.d.) input capacity on the Markov-fading channel using only a few levels.
Feasibility of random basis function approximators for modeling and control
Venue: arXiv cs.NE 2009
Year: 2009

We discuss the role of random basis function approximators in modeling and control. We analyze the published work on random basis function approximators and demonstrate that their favorable error rate of convergence O(1/n) is guaranteed only with very substantial computational resources. We also discuss implications of our analysis for applications of neural networks in modeling and control.
Soft Motion Trajectory Planner for Service Manipulator Robot
Venue: arXiv cs.RO 2009
Year: 2009

Human interaction introduces two main constraints: Safety and Comfort. Therefore service robot manipulator can't be controlled like industrial robotic manipulator where personnel is isolated from the robot's work envelope. In this paper, we present a soft motion trajectory planner to try to ensure that these constraints are satisfied. This planner can be used on-line to establish visual and force control loop suitable in presence of human. The cubic trajectories build by this planner are good candidates as output of a manipulation task planner. The obtained system is then homogeneous from task planning to robot control. The soft motion trajectory planner limits jerk, acceleration and velocity in cartesian space using quaternion. Experimental results carried out on a Mitsubishi PA10-6CE arm are presented.
Constructions of Almost Optimal Resilient Boolean Functions on Large Even Number of Variables
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, a technique on constructing nonlinear resilient Boolean functions is described. By using several sets of disjoint spectra functions on a small number of variables, an almost optimal resilient function on a large even number of variables can be constructed. It is shown that given any $m$, one can construct infinitely many $n$-variable ($n$ even), $m$-resilient functions with nonlinearity $>2^{n-1}-2^{n/2}$. A large class of highly nonlinear resilient functions which were not known are obtained. Then one method to optimize the degree of the constructed functions is proposed. Last, an improved version of the main construction is given.
Statistical Automatic Summarization in Organic Chemistry
Venue: arXiv cs.IR 2009
Year: 2009

We present an oriented numerical summarizer algorithm, applied to producing automatic summaries of scientific documents in Organic Chemistry. We present its implementation named Yachs (Yet Another Chemistry Summarizer) that combines a specific document pre-processing with a sentence scoring method relying on the statistical properties of documents. We show that Yachs achieves the best results among several other summarizers on a corpus of Organic Chemistry articles.
The Modular Audio Recognition Framework (MARF) and its Applications: Scientific and Software Engineering Notes
Venue: arXiv cs.SD 2009
Year: 2009

MARF is an open-source research platform and a collection of voice/sound/speech/text and natural language processing (NLP) algorithms written in Java and arranged into a modular and extensible framework facilitating addition of new algorithms. MARF can run distributively over the network and may act as a library in applications or be used as a source for learning and extension. A few example applications are provided to show how to use the framework. There is an API reference in the Javadoc format as well as this set of accompanying notes with the detailed description of the architectural design, algorithms, and applications. MARF and its applications are released under a BSD-style license and is hosted at SourceForge.net. This document provides the details and the insight on the internals of MARF and some of the mentioned applications.
Two-message quantum interactive proofs are in PSPACE
Venue: arXiv cs.CC 2009
Year: 2009

We prove that QIP(2), the class of problems having two-message quantum interactive proof systems, is a subset of PSPACE. This relationship is obtained by means of an efficient parallel algorithm, based on the multiplicative weights update method, for approximately solving a certain class of semidefinite programs.
On the Distribution of the Sum of Gamma-Gamma Variates and Applications in RF and Optical Wireless Communications
Venue: arXiv cs.IT 2009
Year: 2009

The Gamma-Gamma (GG) distribution has recently attracted the interest within the research community due to its involvement in various communication systems. In the context of RF wireless communications, GG distribution accurately models the power statistics in composite shadowing/fading channels as well as in cascade multipath fading channels, while in optical wireless (OW) systems, it describes the fluctuations of the irradiance of optical signals distorted by atmospheric turbulence. Although GG channel model offers analytical tractability in the analysis of single input single output (SISO) wireless systems, difficulties arise when studying multiple input multiple output (MIMO) systems, where the distribution of the sum of independent GG variates is required. In this paper, we present a novel simple closed-form approximation for the distribution of the sum of independent, but not necessarily identically distributed GG variates. It is shown that the probability density function (PDF) of the GG sum can be efficiently approximated either by the PDF of a single GG distribution, or by a finite weighted sum of PDFs of GG distributions. To reveal the importance of the proposed approximation, the performance of RF wireless systems in the presence of composite fading, as well as MIMO OW systems impaired by atmospheric turbulence, are investigated. Numerical results and simulations illustrate the accuracy of the proposed approach.
Saddle-point Solution of the Fingerprinting Capacity Game Under the Marking Assumption
Venue: arXiv cs.IT 2009
Year: 2009

We study a fingerprinting game in which the collusion channel is unknown. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. Fingerprinting capacity has recently been derived as the limit value of a sequence of maxmin games with mutual information as the payoff function. However, these games generally do not admit saddle-point solutions and are very hard to solve numerically. Here under the so-called Boneh-Shaw marking assumption, we reformulate the capacity as the value of a single two-person zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is $k$ and the fingerprint alphabet is binary, we derive equations that can numerically solve the capacity game for arbitrary $k$. We also provide tight upper and lower bounds on the capacity. Finally, we discuss the asymptotic behavior of the fingerprinting game for large $k$ and practical implementation issues.
A Recommender System to Support the Scholarly Communication Process
Venue: arXiv cs.DL 2009
Year: 2009

The number of researchers, articles, journals, conferences, funding opportunities, and other such scholarly resources continues to grow every year and at an increasing rate. Many services have emerged to support scholars in navigating particular aspects of this resource-rich environment. Some commercial publishers provide recommender and alert services for the articles and journals in their digital libraries. Similarly, numerous noncommercial social bookmarking services have emerged for citation sharing. While these services do provide some support, they lack an understanding of the various problem-solving scenarios that researchers face daily. Example scenarios, to name a few, include when a scholar is in search of an article related to another article of interest, when a scholar is in search of a potential collaborator for a funding opportunity, when a scholar is in search of an optimal venue to which to submit their article, and when a scholar, in the role of an editor, is in search of referees to review an article. All of these example scenarios can be represented as a problem in information filtering by means of context-sensitive recommendation. This article presents an overview of a context-sensitive recommender system to support the scholarly communication process that is based on the standards and technology set forth by the Semantic Web initiative.
More efficient periodic traversal in anonymous undirected graphs
Venue: arXiv cs.DM 2009
Year: 2009

We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an arbitrary undirected graph G in a periodic manner. Graphs are supposed to be anonymous, that is, nodes are unlabeled. However, while visiting a node, the robot has to distinguish between edges incident to it. For each node v the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in minimisation of the length of the exploration period. This problem is unsolvable if the local port numbers are set arbitrarily. However, surprisingly small periods can be achieved when assigning carefully the local port numbers. Dobrev et al. described an algorithm for assigning port numbers, and an oblivious agent (i.e. agent with no memory) using it, such that the agent explores all graphs of size n within period 10n. Providing the agent with a constant number of memory bits, the optimal length of the period was previously proved to be no more than 3.75n (using a different assignment of the port numbers). In this paper, we improve both these bounds. More precisely, we show a period of length at most 4 1/3 n for oblivious agents, and a period of length at most 3.5n for agents with constant memory. Moreover, we give the first non-trivial lower bound, 2.8n, on the period length for the oblivious case.
Classification of Cellular Automata Rules Based on Their Properties
Venue: arXiv cs.DM 2009
Year: 2009

This paper presents a classification of Cellular Automata rules based on its properties at the nth iteration. Elaborate computer program has been designed to get the nth iteration for arbitrary 1-D or 2-D CA rules. Studies indicate that the figures at some particular iteration might be helpful for some specific application. The hardware circuit implementation can be done using opto-electronic components [1-7].
The L(2, 1)-Labeling Problem on Oriented Regular Grids
Venue: arXiv cs.DM 2009
Year: 2009

The L(2, 1)-labeling of a digraph G is a function f from the node set of $G$ to the set of all nonnegative integers such that $|f(x)-f(y)| \geq 2$ if $x$ and $y$ are at distance 1, and $f(x)=f(y)$ if $x$ and $y$ are at distance 2, where the distance from vertex $x$ to vertex $y$ is the length of a shortest dipath from $x$ to $y$. The minimum of the maximum used label over all $L(2, 1)$-labelings of $G$ is called $λ(G)$. In this paper we study the L(2, 1)-labeling problem on squared, triangular and hexagonal grids and for them we compute the exact values of $λ$.
Cascade multiterminal source coding
Venue: arXiv cs.IT 2009
Year: 2009

We investigate distributed source coding of two correlated sources X and Y where messages are passed to a decoder in a cascade fashion. The encoder of X sends a message at rate R_1 to the encoder of Y. The encoder of Y then sends a message to the decoder at rate R_2 based both on Y and on the message it received about X. The decoder's task is to estimate a function of X and Y. For example, we consider the minimum mean squared-error distortion when encoding the sum of jointly Gaussian random variables under these constraints. We also characterize the rates needed to reconstruct a function of X and Y losslessly. Our general contribution toward understanding the limits of the cascade multiterminal source coding network is in the form of inner and outer bounds on the achievable rate region for satisfying a distortion constraint for an arbitrary distortion function d(x,y,z). The inner bound makes use of a balance between two encoding tactics--relaying the information about X and recompressing the information about X jointly with Y. In the Gaussian case, a threshold is discovered for identifying which of the two extreme strategies optimizes the inner bound. Relaying outperforms recompressing the sum at the relay for some rate pairs if the variance of X is greater than the variance of Y.
Termination Prediction for General Logic Programs
Venue: arXiv cs.PL 2009
Year: 2009

We present a heuristic framework for attacking the undecidable termination problem of logic programs, as an alternative to current termination/non-termination proof approaches. We introduce an idea of termination prediction, which predicts termination of a logic program in case that neither a termination nor a non-termination proof is applicable. We establish a necessary and sufficient characterization of infinite (generalized) SLDNF-derivations with arbitrary (concrete or moded) queries, and develop an algorithm that predicts termination of general logic programs with arbitrary non-floundering queries. We have implemented a termination prediction tool and obtained quite satisfactory experimental results. Except for five programs which break the experiment time limit, our prediction is 100% correct for all 296 benchmark programs of the Termination Competition 2007, of which eighteen programs cannot be proved by any of the existing state-of-the-art analyzers like AProVE07, NTI, Polytool and TALP.
End-to-End Joint Antenna Selection Strategy and Distributed Compress and Forward Strategy for Relay Channels
Venue: arXiv cs.IT 2009
Year: 2009

Multi-hop relay channels use multiple relay stages, each with multiple relay nodes, to facilitate communication between a source and destination. Previously, distributed space-time codes were proposed to maximize the achievable diversity-multiplexing tradeoff, however, they fail to achieve all the points of the optimal diversity-multiplexing tradeoff. In the presence of a low-rate feedback link from the destination to each relay stage and the source, this paper proposes an end-to-end antenna selection (EEAS) strategy as an alternative to distributed space-time codes. The EEAS strategy uses a subset of antennas of each relay stage for transmission of the source signal to the destination with amplify and forwarding at each relay stage. The subsets are chosen such that they maximize the end-to-end mutual information at the destination. The EEAS strategy achieves the corner points of the optimal diversity-multiplexing tradeoff (corresponding to maximum diversity gain and maximum multiplexing gain) and achieves better diversity gain at intermediate values of multiplexing gain, versus the best known distributed space-time coding strategies. A distributed compress and forward (CF) strategy is also proposed to achieve all points of the optimal diversity-multiplexing tradeoff for a two-hop relay channel with multiple relay nodes.
Privacy-Preserving Querying in Sensor Networks
Venue: arXiv cs.CR 2009
Year: 2009

Wireless Sensor Networks (WSNs) provide sensing and monitoring services by means of many tiny autonomous devices equipped with wireless radio transceivers. As WSNs are deployed on a large-scale and/or on long-term basis, not only traditional security but also privacy issues must be taken into account. Furthermore, when network operators offer on-demand access to sensor measurements to their clients, query mechanisms should ideally leak neither client interests nor query patterns. In this paper, we present a privacy-preserving WSN query mechanism that uses standard cryptographic techniques. Besides preventing unauthorized entities from accessing sensor readings, it minimizes leakage of (potentially sensitive) information about users' query targets and patterns.
Expressiveness and Closure Properties for Quantitative Languages
Venue: arXiv cs.LO 2009
Year: 2009

Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages $L$ that assign to each word $w$ a real number $L(w)$. In the case of infinite words, the value of a run is naturally computed as the maximum, limsup, liminf, limit average, or discounted sum of the transition weights. We study expressiveness and closure questions about these quantitative languages. We first show that the set of words with value greater than a threshold can be non-$ω$-regular for deterministic limit-average and discounted-sum automata, while this set is always $ω$-regular when the threshold is isolated (i.e., some neighborhood around the threshold contains no word). In the latter case, we prove that the $ω$-regular language is robust against small perturbations of the transition weights. We next consider automata with transition weights 0 or 1 and show that they are as expressive as general weighted automata in the limit-average case, but not in the discounted-sum case. Third, for quantitative languages $L_1$ and $L_2$, we consider the operations $\max(L_1,L_2)$, $\min(L_1,L_2)$, and $1-L_1$, which generalize the boolean operations on languages, as well as the sum $L_1 + L_2$. We establish the closure properties of all classes of quantitative languages with respect to these four operations.