OpenRaiser/Intern-Atlas huggingface dataset:
Fast Cycle Frequency Domain Feature Detection for Cognitive Radio Systems
Venue: arXiv cs.IT 2009
Year: 2009

In cognitive radio systems, one of the main requirements is to detect the presence of the primary users' transmission, especially in weak signal cases. Cyclostationary detection is always used to solve weak signal detection, however, the computational complexity prevents it from wide usage. In this paper, a fast cycle frequency domain feature detection algorithm has been proposed, in which only feature frequency with significant cyclic signature is considered for a certain modulation mode. Simulation results show that the proposed algorithm has remarkable performance gain than energy detection when supporting real-time detection with low computational complexity.
The structure of finite meadows
Venue: arXiv cs.LO 2009
Year: 2009

A meadow is a commutative ring with a total inverse operator satisfying 0^{-1}=0. We show that the class of finite meadows is the closure of the class of Galois fields under finite products. As a corollary, we obtain a unique representation of minimal finite meadows in terms of finite prime fields.
Optimum Pilot Overhead in Wireless Communication: A Unified Treatment of Continuous and Block-Fading Channels
Venue: arXiv cs.IT 2009
Year: 2009

The optimization of the pilot overhead in single-user wireless fading channels is investigated, and the dependence of this overhead on various system parameters of interest (e.g., fading rate, signal-to-noise ratio) is quantified. The achievable pilot-based spectral efficiency is expanded with respect to the fading rate about the no-fading point, which leads to an accurate order expansion for the pilot overhead. This expansion identifies that the pilot overhead, as well as the spectral efficiency penalty with respect to a reference system with genie-aided CSI (channel state information) at the receiver, depend on the square root of the normalized Doppler frequency. Furthermore, it is shown that the widely-used block fading model is only a special case of more accurate continuous fading models in terms of the achievable pilot-based spectral efficiency, and that the overhead optimization for multiantenna systems is effectively the same as for single-antenna systems with the normalized Doppler frequency multiplied by the number of transmit antennas.
Definition of evidence fusion rules on the basis of Referee Functions
Venue: arXiv cs.AI 2009
Year: 2009

This chapter defines a new concept and framework for constructing fusion rules for evidences. This framework is based on a referee function, which does a decisional arbitrament conditionally to basic decisions provided by the several sources of information. A simple sampling method is derived from this framework. The purpose of this sampling approach is to avoid the combinatorics which are inherent to the definition of fusion rules of evidences. This definition of the fusion rule by the means of a sampling process makes possible the construction of several rules on the basis of an algorithmic implementation of the referee function, instead of a mathematical formulation. Incidentally, it is a versatile and intuitive way for defining rules. The framework is implemented for various well known evidence rules. On the basis of this framework, new rules for combining evidences are proposed, which takes into account a consensual evaluation of the sources of information.
Instanton-based Techniques for Analysis and Reduction of Error Floors of LDPC Codes
Venue: arXiv cs.IT 2009
Year: 2009

We describe a family of instanton-based optimization methods developed recently for the analysis of the error floors of low-density parity-check (LDPC) codes. Instantons are the most probable configurations of the channel noise which result in decoding failures. We show that the general idea and the respective optimization technique are applicable broadly to a variety of channels, discrete or continuous, and variety of sub-optimal decoders. Specifically, we consider: iterative belief propagation (BP) decoders, Gallager type decoders, and linear programming (LP) decoders performing over the additive white Gaussian noise channel (AWGNC) and the binary symmetric channel (BSC). The instanton analysis suggests that the underlying topological structures of the most probable instanton of the same code but different channels and decoders are related to each other. Armed with this understanding of the graphical structure of the instanton and its relation to the decoding failures, we suggest a method to construct codes whose Tanner graphs are free of these structures, and thus have less significant error floors.
Connectivity of Heterogeneous Wireless Networks
Venue: arXiv cs.NI 2009
Year: 2009

We address the connectivity of large-scale ad hoc heterogeneous wireless networks, where secondary users exploit channels temporarily unused by primary users and the existence of a communication link between two secondary users depends on not only the distance between them but also the transmitting and receiving activities of nearby primary users. We introduce the concept of connectivity region defined as the set of density pairs -- the density of secondary users and the density of primary transmitters -- under which the secondary network is connected. Using theories and techniques from continuum percolation, we analytically characterize the connectivity region of the secondary network and reveal the tradeoff between proximity (the number of neighbors) and the occurrence of spectrum opportunities. Specifically, we establish three basic properties of the connectivity region -- contiguity, monotonicity of the boundary, and uniqueness of the infinite connected component, where the uniqueness implies the occurrence of a phase transition phenomenon in terms of the almost sure existence of either zero or one infinite connected component; we identify and analyze two critical densities which jointly specify the profile as well as an outer bound on the connectivity region; we study the impacts of secondary users' transmission power on the connectivity region and the conditional average degree of a secondary user, and demonstrate that matching the interference ranges of the primary and the secondary networks maximizes the tolerance of the secondary network to the primary traffic load. Furthermore, we establish a necessary condition and a sufficient condition for connectivity, which lead to an outer bound and an inner bound on the connectivity region.
Improved Lower Bounds on Capacities of Symmetric 2-Dimensional Constraints using Rayleigh Quotients
Venue: arXiv cs.IT 2009
Year: 2009

A method for computing lower bounds on capacities of 2-dimensional constraints having a symmetric presentation in either the horizontal or the vertical direction is presented. The method is a generalization of the method of Calkin and Wilf (SIAM J. Discrete Math., 1998). Previous best lower bounds on capacities of certain constraints are improved using the method. It is also shown how this method, as well as their method for computing upper bounds on the capacity, can be applied to constraints which are not of finite-type. Additionally, capacities of 2 families of multi-dimensional constraints are given exactly.
Folding, Tiling, and Multidimensional Coding
Venue: arXiv cs.IT 2009
Year: 2009

Folding a sequence $S$ into a multidimensional box is a method that is used to construct multidimensional codes. The well known operation of folding is generalized in a way that the sequence $S$ can be folded into various shapes. The new definition of folding is based on lattice tiling and a direction in the $D$-dimensional grid. There are potentially $\frac{3^D-1}{2}$ different folding operations. Necessary and sufficient conditions that a lattice combined with a direction define a folding are given. The immediate and most impressive application is some new lower bounds on the number of dots in two-dimensional synchronization patterns. This can be also generalized for multidimensional synchronization patterns. We show how folding can be used to construct multidimensional error-correcting codes and to generate multidimensional pseudo-random arrays.
Review of Replication Schemes for Unstructured P2P Networks
Venue: arXiv cs.DC 2009
Year: 2009

To improve unstructured P2P system performance, one wants to minimize the number of peers that have to be probed for the shortening of the search time. A solution to the problem is to employ a replication scheme, which provides high hit rate for target files. Replication can also provide load balancing and reduce access latency if the file is accessed by a large population of users. This paper briefly describes various replication schemes that have appeared in the literature and also focuses on a novel replication technique called Q-replication to increase availability of objects in unstructured P2P networks. The Q-replication technique replicates objects autonomously to suitable sites based on object popularity and site selection logic by extensively employing Q-learning concept.
The Role of Tag Suggestions in Folksonomies
Venue: arXiv cs.HC 2009
Year: 2009

Most tagging systems support the user in the tag selection process by providing tag suggestions, or recommendations, based on a popularity measurement of tags other users provided when tagging the same resource. In this paper we investigate the influence of tag suggestions on the emergence of power law distributions as a result of collaborative tag behavior. Although previous research has already shown that power laws emerge in tagging systems, the cause of why power law distributions emerge is not understood empirically. The majority of theories and mathematical models of tagging found in the literature assume that the emergence of power laws in tagging systems is mainly driven by the imitation behavior of users when observing tag suggestions provided by the user interface of the tagging system. This imitation behavior leads to a feedback loop in which some tags are reinforced and get more popular which is also known as the `rich get richer' or a preferential attachment model. We present experimental results that show that the power law distribution forms regardless of whether or not tag suggestions are presented to the users. Furthermore, we show that the real effect of tag suggestions is rather subtle; the resulting power law distribution is `compressed' if tag suggestions are given to the user, resulting in a shorter long tail and a `compressed' top of the power law distribution. The consequences of this experiment show that tag suggestions by themselves do not account for the formation of power law distributions in tagging systems.
Contracting preference relations for database applications
Venue: arXiv cs.AI 2009
Year: 2009

The binary relation framework has been shown to be applicable to many real-life preference handling scenarios. Here we study preference contraction: the problem of discarding selected preferences. We argue that the property of minimality and the preservation of strict partial orders are crucial for contractions. Contractions can be further constrained by specifying which preferences should be protected. We consider two classes of preference relations: finite and finitely representable. We present algorithms for computing minimal and preference-protecting minimal contractions for finite as well as finitely representable preference relations. We study relationships between preference change in the binary relation framework and belief change in the belief revision theory. We also introduce some preference query optimization techniques which can be used in the presence of contraction. We evaluate the proposed algorithms experimentally and present the results.
Hessian and concavity of mutual information, differential entropy, and entropy power in linear vector Gaussian channels
Venue: arXiv cs.IT 2009
Year: 2009

Within the framework of linear vector Gaussian channels with arbitrary signaling, closed-form expressions for the Jacobian of the minimum mean square error and Fisher information matrices with respect to arbitrary parameters of the system are calculated in this paper. Capitalizing on prior research where the minimum mean square error and Fisher information matrices were linked to information-theoretic quantities through differentiation, closed-form expressions for the Hessian of the mutual information and the differential entropy are derived. These expressions are then used to assess the concavity properties of mutual information and differential entropy under different channel conditions and also to derive a multivariate version of the entropy power inequality due to Costa.
On Competing Wireless Service Providers
Venue: arXiv cs.IT 2009
Year: 2009

We consider a situation where wireless service providers compete for heterogenous wireless users. The users differ in their willingness to pay as well as in their individual channel gains. We prove existence and uniqueness of the Nash equilibrium for the competition of two service providers, for a generic channel model. Interestingly, the competition of two providers leads to a globally optimal outcome. We extend some of the results to the case where more than two providers are competing. Finally, we provide numerical examples that illustrate the effects of various parameters on the Nash equilibrium.
A new universal cellular automaton on the ternary heptagrid
Venue: arXiv cs.FL 2009
Year: 2009

In this paper, we construct a new weakly universal cellular automaton on the ternary heptagrid. The previous result, obtained by the same author and Y. Song required six states only. This time, the number of states is four. This is the best result up to date for cellular automata in the hyperbolic plane.
Game theory and the frequency selective interference channel - A tutorial
Venue: arXiv cs.IT 2009
Year: 2009

This paper provides a tutorial overview of game theoretic techniques used for communication over frequency selective interference channels. We discuss both competitive and cooperative techniques. Keywords: Game theory, competitive games, cooperative games, Nash Equilibrium, Nash bargaining solution, Generalized Nash games, Spectrum optimization, distributed coordination, interference channel, multiple access channel, iterative water-filling.
A Lightweight Combination of Semantics for Non-deterministic Functions
Venue: arXiv cs.PL 2009
Year: 2009

The use of non-deterministic functions is a distinctive feature of modern functional logic languages. The semantics commonly adopted is call-time choice, a notion that at the operational level is related to the sharing mechanism of lazy evaluation in functional languages. However, there are situations where run-time choice, closer to ordinary rewriting, is more appropriate. In this paper we propose an extension of existing call-time choice based languages, to provide support for run-time choice in localized parts of a program. The extension is remarkably simple at three relevant levels: syntax, formal operational calculi and implementation, which is based on the system Toy.
Prolog Visualization System Using Logichart Diagrams
Venue: arXiv cs.PL 2009
Year: 2009

We have developed a Prolog visualization system that is intended to support Prolog programming education. The system uses Logichart diagrams to visualize Prolog programs. The Logichart diagram is designed to visualize the Prolog execution flow intelligibly and to enable users to easily correlate the Prolog clauses with its parts. The system has the following functions. (1) It visually traces Prolog execution (goal calling, success, and failure) on the Logichart diagram. (2) Dynamic change in a Prolog program by calling extra-logical predicates, such as `assertz' and `retract', is visualized in real time. (3) Variable substitution processes are displayed in a text widget in real time.
On the achievable diversity-multiplexing tradeoff in interference channels
Venue: arXiv cs.IT 2009
Year: 2009

We analyze two-user single-antenna fading interference channels with perfect receive channel state information (CSI) and no transmit CSI. For the case of very strong interference, we prove that decoding interference while treating the intended signal as noise, subtracting the result out, and then decoding the desired signal, a process known as "stripping", achieves the diversity-multiplexing tradeoff (DMT) outer bound derived in Akuiyibo and Leveque, Int. Zurich Seminar on Commun., 2008. The proof is constructive in the sense that it provides corresponding code design criteria for DMT optimality. For general interference levels, we compute the DMT of a fixed-power-split Han and Kobayashi type superposition coding scheme, provide design criteria for the corresponding superposition codes, and find that this scheme is DMT-optimal for certain multiplexing rates.
Constraint solving for high-level WCET analysis
Venue: arXiv cs.PL 2009
Year: 2009

The safety of our day-to-day life depends crucially on the correct functioning of embedded software systems which control the functioning of more and more technical devices. Many of these software systems are time-critical. Hence, computations performed need not only to be correct, but must also be issued in a timely fashion. Worst case execution time (WCET) analysis is concerned with computing tight upper bounds for the execution time of a system in order to provide formal guarantees for the proper timing behaviour of a system. Central for this is to compute safe and tight bounds for loops and recursion depths. In this paper, we highlight the TuBound approach to this challenge at whose heart is a constraint logic based approach for loop analysis.
Infinite words without palindrome
Venue: arXiv cs.DM 2009
Year: 2009

We show that there exists an uniformly recurrent infinite word whose set of factors is closed under reversal and which has only finitely many palindromic factors.
Qualitative Logics and Equivalences for Probabilistic Systems
Venue: arXiv cs.LO 2009
Year: 2009

We investigate logics and equivalence relations that capture the qualitative behavior of Markov Decision Processes (MDPs). We present Qualitative Randomized CTL (QRCTL): formulas of this logic can express the fact that certain temporal properties hold over all paths, or with probability 0 or 1, but they do not distinguish among intermediate probability values. We present a symbolic, polynomial time model-checking algorithm for QRCTL on MDPs. The logic QRCTL induces an equivalence relation over states of an MDP that we call qualitative equivalence: informally, two states are qualitatively equivalent if the sets of formulas that hold with probability 0 or 1 at the two states are the same. We show that for finite alternating MDPs, where nondeterministic and probabilistic choices occur in different states, qualitative equivalence coincides with alternating bisimulation, and can thus be computed via efficient partition-refinement algorithms. On the other hand, in non-alternating MDPs the equivalence relations cannot be computed via partition-refinement algorithms, but rather, they require non-local computation. Finally, we consider QRCTL*, that extends QRCTL with nested temporal operators in the same manner in which CTL* extends CTL. We show that QRCTL and QRCTL* induce the same qualitative equivalence on alternating MDPs, while on non-alternating MDPs, the equivalence arising from QRCTL* can be strictly finer. We also provide a full characterization of the relation between qualitative equivalence, bisimulation, and alternating bisimulation, according to whether the MDPs are finite, and to whether their transition relations are finitely-branching.
A Note on Preconditioning by Low-Stretch Spanning Trees
Venue: arXiv cs.NA 2009
Year: 2009

Boman and Hendrickson observed that one can solve linear systems in Laplacian matrices in time $\bigO{m^{3/2 + o (1)} \ln (1/ε)}$ by preconditioning with the Laplacian of a low-stretch spanning tree. By examining the distribution of eigenvalues of the preconditioned linear system, we prove that the preconditioned conjugate gradient will actually solve the linear system in time $\softO{m^{4/3} \ln (1/ε)}$.
Cooperative Transmission in a Wireless Relay Network based on Flow Management
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, a cooperative transmission design for a general multi-node half-duplex wireless relay network is presented. It is assumed that the nodes operate in half-duplex mode and that channel information is available at the nodes. The proposed design involves solving a convex flow optimization problem on a graph that models the relay network. A much simpler generalized-link selection protocol based on the above design is also presented. Both the proposed flow-optimized protocol and the generalized-link selection protocol are shown to achieve the optimal diversity-multiplexing tradeoff (DMT) for the relay network. Moreover, simulation results are presented to quantify the gap between the performances of the proposed protocols and that of a max-flow-min-cut type bound, in terms of outage probability.
On $p$-adic Classification
Venue: arXiv cs.LG 2009
Year: 2009

A $p$-adic modification of the split-LBG classification method is presented in which first clusterings and then cluster centers are computed which locally minimise an energy function. The outcome for a fixed dataset is independent of the prime number $p$ with finitely many exceptions. The methods are applied to the construction of $p$-adic classifiers in the context of learning.
Spatial Skyline Queries: An Efficient Geometric Algorithm
Venue: arXiv cs.DB 2009
Year: 2009

As more data-intensive applications emerge, advanced retrieval semantics, such as ranking or skylines, have attracted attention. Geographic information systems are such an application with massive spatial data. Our goal is to efficiently support skyline queries over massive spatial data. To achieve this goal, we first observe that the best known algorithm VS2, despite its claim, may fail to deliver correct results. In contrast, we present a simple and efficient algorithm that computes the correct results. To validate the effectiveness and efficiency of our algorithm, we provide an extensive empirical comparison of our algorithm and VS2 in several aspects.
Automated Vehicle Location (AVL) Using Global Positioning System (GPS)
Venue: arXiv cs.NI 2009
Year: 2009

this is a review paper. this describes how DGPS is helpful for lane detection and to avoid collission.
TR02: State dependent oracle masks for improved dynamical features
Venue: arXiv cs.SD 2009
Year: 2009

Using the AURORA-2 digit recognition task, we show that recognition accuracies obtained with classical, SNR based oracle masks can be substantially improved by using a state-dependent mask estimation technique.
Fixed point theorems on partial randomness
Venue: arXiv cs.IT 2009
Year: 2009

In our former work [K. Tadaki, Local Proceedings of CiE 2008, pp.425-434, 2008], we developed a statistical mechanical interpretation of algorithmic information theory by introducing the notion of thermodynamic quantities at temperature T, such as free energy F(T), energy E(T), and statistical mechanical entropy S(T), into the theory. These quantities are real functions of real argument T>0. We then discovered that, in the interpretation, the temperature T equals to the partial randomness of the values of all these thermodynamic quantities, where the notion of partial randomness is a stronger representation of the compression rate by program-size complexity. Furthermore, we showed that this situation holds for the temperature itself as a thermodynamic quantity. Namely, the computability of the value of partition function Z(T) gives a sufficient condition for T in (0,1) to be a fixed point on partial randomness. In this paper, we show that the computability of each of all the thermodynamic quantities above gives the sufficient condition also. Moreover, we show that the computability of F(T) gives completely different fixed points from the computability of Z(T).