OpenRaiser/Intern-Atlas huggingface dataset:
Analytic Properties and Covariance Functions of a New Class of Generalized Gibbs Random Fields
Venue: arXiv cs.IT 2006
Year: 2006

Spartan Spatial Random Fields (SSRFs) are generalized Gibbs random fields, equipped with a coarse-graining kernel that acts as a low-pass filter for the fluctuations. SSRFs are defined by means of physically motivated spatial interactions and a small set of free parameters (interaction couplings). This paper focuses on the FGC-SSRF model, which is defined on the Euclidean space $\mathbb{R}^{d}$ by means of interactions proportional to the squares of the field realizations, as well as their gradient and curvature. The permissibility criteria of FGC-SSRFs are extended by considering the impact of a finite-bandwidth kernel. It is proved that the FGC-SSRFs are almost surely differentiable in the case of finite bandwidth. Asymptotic explicit expressions for the Spartan covariance function are derived for $d=1$ and $d=3$; both known and new covariance functions are obtained depending on the value of the FGC-SSRF shape parameter. Nonlinear dependence of the covariance integral scale on the FGC-SSRF characteristic length is established, and it is shown that the relation becomes linear asymptotically. The results presented in this paper are useful in random field parameter inference, as well as in spatial interpolation of irregularly-spaced samples.
A Locating-First Approach for Scalable Overlay Multicast
Venue: arXiv cs.NI 2006
Year: 2006

Recent proposals in multicast overlay construction have demonstrated the importance of exploiting underlying network topology. However, these topology-aware proposals often rely on incremental and periodic refinements to improve the system performance. These approaches are therefore neither scalable, as they induce high communication cost due to refinement overhead, nor efficient because long convergence time is necessary to obtain a stabilized structure. In this paper, we propose a highly scalable locating algorithm that gradually directs newcomers to their a set of their closest nodes without inducing high overhead. On the basis of this locating process, we build a robust and scalable topology-aware clustered hierarchical overlay scheme, called LCC. We conducted both simulations and PlanetLab experiments to evaluate the performance of LCC. Results show that the locating process entails modest resources in terms of time and bandwidth. Moreover, LCC demonstrates promising performance to support large scale multicast applications.
Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities
Venue: arXiv cs.SC 2006
Year: 2006

We present an algorithm which takes as input a closed semi-algebraic set, $S \subset \R^k$, defined by \[ P_1 \leq 0, ..., P_\ell \leq 0, P_i \in \R[X_1,...,X_k], °(P_i) \leq 2, \] and computes the Euler-Poincaré characteristic of $S$. The complexity of the algorithm is $k^{O(\ell)}$.
Upper Bounding the Performance of Arbitrary Finite LDPC Codes on Binary Erasure Channels
Venue: arXiv cs.IT 2006
Year: 2006

Assuming iterative decoding for binary erasure channels (BECs), a novel tree-based technique for upper bounding the bit error rates (BERs) of arbitrary, finite low-density parity-check (LDPC) codes is provided and the resulting bound can be evaluated for all operating erasure probabilities, including both the waterfall and the error floor regions. This upper bound can also be viewed as a narrowing search of stopping sets, which is an approach different from the stopping set enumeration used for lower bounding the error floor. When combined with optimal leaf-finding modules, this upper bound is guaranteed to be tight in terms of the asymptotic order. The Boolean framework proposed herein further admits a composite search for even tighter results. For comparison, a refinement of the algorithm is capable of exhausting all stopping sets of size <14 for irregular LDPC codes of length n=500, which requires approximately 1.67*10^25 trials if a brute force approach is taken. These experiments indicate that this upper bound can be used both as an analytical tool and as a deterministic worst-performance (error floor) guarantee, the latter of which is crucial to optimizing LDPC codes for extremely low BER applications, e.g., optical/satellite communications.
TARMAC: Traffic-Analysis Reslient MAC Protocol for Multi-Hop Wireless Networks
Venue: arXiv cs.NI 2006
Year: 2006

Traffic analysis in Multi-hop Wireless Networks can expose the structure of the network allowing attackers to focus their efforts on critical nodes. For example, jamming the only data sink in a sensor network can cripple the network. We propose a new communication protocol that is part of the MAC layer, but resides conceptually between the routing layer and MAC, that is resilient to traffic analysis. Each node broadcasts the data that it has to transmit according to a fixed transmission schedule that is independent of the traffic being generated, making the network immune to time correlation analysis. The transmission pattern is identical, with the exception of a possible time shift, at all nodes, removing spatial correlation of transmissions to network strucutre. Data for all neighbors resides in the same encrypted packet. Each neighbor then decides which subset of the data in a packet to forward onwards using a routing protocol whose details are orthogonal to the proposed scheme. We analyze the basic scheme, exploring the tradeoffs in terms of frequency of transmission and packet size. We also explore adaptive and time changing patterns and analyze their performance under a number of representative scenarios.
Supervisory Control of Fuzzy Discrete Event Systems: A Formal Approach
Venue: arXiv cs.LO 2006
Year: 2006

Fuzzy {\it discrete event systems} (DESs) were proposed recently by Lin and Ying [19], which may better cope with the real-world problems with fuzziness, impreciseness, and subjectivity such as those in biomedicine. As a continuation of [19], in this paper we further develop fuzzy DESs by dealing with supervisory control of fuzzy DESs. More specifically, (i) we reformulate the parallel composition of crisp DESs, and then define the parallel composition of fuzzy DESs that is equivalent to that in [19]; {\it max-product} and {\it max-min} automata for modeling fuzzy DESs are considered; (ii) we deal with a number of fundamental problems regarding supervisory control of fuzzy DESs, particularly demonstrate controllability theorem and nonblocking controllability theorem of fuzzy DESs, and thus present the conditions for the existence of supervisors in fuzzy DESs; (iii) we analyze the complexity for presenting a uniform criterion to test the fuzzy controllability condition of fuzzy DESs modeled by max-product automata; in particular, we present in detail a general computing method for checking whether or not the fuzzy controllability condition holds, if max-min automata are used to model fuzzy DESs, and by means of this method we can search for all possible fuzzy states reachable from initial fuzzy state in max-min automata; also, we introduce the fuzzy $n$-controllability condition for some practical problems; (iv) a number of examples serving to illustrate the applications of the derived results and methods are described; some basic properties related to supervisory control of fuzzy DESs are investigated. To conclude, some related issues are raised for further consideration.
Diagnosability of Fuzzy Discrete Event Systems
Venue: arXiv cs.AI 2006
Year: 2006

In order to more effectively cope with the real-world problems of vagueness, {\it fuzzy discrete event systems} (FDESs) were proposed recently, and the supervisory control theory of FDESs was developed. In view of the importance of failure diagnosis, in this paper, we present an approach of the failure diagnosis in the framework of FDESs. More specifically: (1) We formalize the definition of diagnosability for FDESs, in which the observable set and failure set of events are {\it fuzzy}, that is, each event has certain degree to be observable and unobservable, and, also, each event may possess different possibility of failure occurring. (2) Through the construction of observability-based diagnosers of FDESs, we investigate its some basic properties. In particular, we present a necessary and sufficient condition for diagnosability of FDESs. (3) Some examples serving to illuminate the applications of the diagnosability of FDESs are described. To conclude, some related issues are raised for further consideration.
Communication of Social Agents and the Digital City - A Semiotic Perspective
Venue: arXiv cs.AI 2006
Year: 2006

This paper investigates the concept of digital city. First, a functional analysis of a digital city is made in the light of the modern study of urbanism; similarities between the virtual and urban constructions are pointed out. Next, a semiotic perspective on the subject matter is elaborated, and a terminological basis is introduced to treat a digital city as a self-organizing meaning-producing system intended to support social or spatial navigation. An explicit definition of a digital city is formulated. Finally, the proposed approach is discussed, conclusions are given, and future work is outlined.
Notes on Geometric Measure Theory Applications to Image Processing; De-noising, Segmentation, Pattern, Texture, Lines, Gestalt and Occlusion
Venue: arXiv cs.CV 2006
Year: 2006

Regularization functionals that lower level set boundary length when used with L^1 fidelity functionals on signal de-noising on images create artifacts. These are (i) rounding of corners, (ii) shrinking of radii, (iii) shrinking of cusps, and (iv) non-smoothing of staircasing. Regularity functionals based upon total curvature of level set boundaries do not create artifacts (i) and (ii). An adjusted fidelity term based on the flat norm on the current (a distributional graph) representing the density of curvature of level sets boundaries can minimize (iii) by weighting the position of a cusp. A regularity term to eliminate staircasing can be based upon the mass of the current representing the graph of an image function or its second derivatives. Densities on the Grassmann bundle of the Grassmann bundle of the ambient space of the graph can be used to identify patterns, textures, occlusion and lines.
On the Role of Estimate-and-Forward with Time-Sharing in Cooperative Communications
Venue: arXiv cs.IT 2006
Year: 2006

In this work we focus on the general relay channel. We investigate the application of estimate-and-forward (EAF) to different scenarios. Specifically, we consider assignments of the auxiliary random variables that always satisfy the feasibility constraints. We first consider the multiple relay channel and obtain an achievable rate without decoding at the relays. We demonstrate the benefits of this result via an explicit discrete memoryless multiple relay scenario where multi-relay EAF is superior to multi-relay decode-and-forward (DAF). We then consider the Gaussian relay channel with coded modulation, where we show that a three-level quantization outperforms the Gaussian quantization commonly used to evaluate the achievable rates in this scenario. Finally we consider the cooperative general broadcast scenario with a multi-step conference. We apply estimate-and-forward to obtain a general multi-step achievable rate region. We then give an explicit assignment of the auxiliary random variables, and use this result to obtain an explicit expression for the single common message broadcast scenario with a two-step conference.
Construction and Count of Boolean Functions of an Odd Number of Variables with Maximum Algebraic Immunity
Venue: arXiv cs.CR 2006
Year: 2006

Algebraic immunity has been proposed as an important property of Boolean functions. To resist algebraic attack, a Boolean function should possess high algebraic immunity. It is well known now that the algebraic immunity of an $n$-variable Boolean function is upper bounded by $\left\lceil {\frac{n}{2}} \right\rceil $. In this paper, for an odd integer $n$, we present a construction method which can efficiently generate a Boolean function of $n$ variables with maximum algebraic immunity, and we also show that any such function can be generated by this method. Moreover, the number of such Boolean functions is greater than $2^{2^{n-1}}$.
The KAA project: a trust policy point of view
Venue: arXiv cs.NI 2006
Year: 2006

In the context of ambient networks where each small device must trust its neighborhood rather than a fixed network, we propose in this paper a \textit{trust management framework} inspired by known social patterns and based on the following statements: each mobile constructs itself a local level of trust what means that it does not accept recommendation by other peers, and the only relevant parameter, beyond some special cases discussed later, to evaluate the level of trust is the number of common trusted mobiles. These trusted mobiles are considered as entries in a local database called history for each device and we use identity-based cryptography to ensure strong security: history must be a non-tansferable object.
Foundations of Modern Language Resource Archives
Venue: arXiv cs.CL 2006
Year: 2006

A number of serious reasons will convince an increasing amount of researchers to store their relevant material in centers which we will call "language resource archives". They combine the duty of taking care of long-term preservation as well as the task to give access to their material to different user groups. Access here is meant in the sense that an active interaction with the data will be made possible to support the integration of new data, new versions or commentaries of all sort. Modern Language Resource Archives will have to adhere to a number of basic principles to fulfill all requirements and they will have to be involved in federations to create joint language resource domains making it even more simple for the researchers to access the data. This paper makes an attempt to formulate the essential pillars language resource archives have to adhere to.
Vectorial Resilient $PC(l)$ of Order $k$ Boolean Functions from AG-Codes
Venue: arXiv cs.CR 2006
Year: 2006

Propagation criterion of degree $l$ and order $k$ ($PC(l)$ of order $k$) and resiliency of vectorial Boolean functions are important for cryptographic purpose (see [1, 2, 3,6, 7,8,10,11,16]. Kurosawa, Stoh [8] and Carlet [1] gave a construction of Boolean functions satisfying $PC(l)$ of order $k$ from binary linear or nonlinear codes in. In this paper, algebraic-geometric codes over $GF(2^m)$ are used to modify Carlet and Kurosawa-Satoh's construction for giving vectorial resilient Boolean functions satisfying $PC(l)$ of order $k$. The new construction is compared with previously known results.
Good Illumination of Minimum Range
Venue: arXiv cs.CG 2006
Year: 2006

A point p is 1-well illuminated by a set F of n point lights if p lies in the interior of the convex hull of F. This concept corresponds to triangle-guarding or well-covering. In this paper we consider the illumination range of the light sources as a parameter to be optimized. First, we solve the problem of minimizing the light sources' illumination range to 1-well illuminate a given point p. We also compute a minimal set of light sources that 1-well illuminates p with minimum illumination range. Second, we solve the problem of minimizing the light sources' illumination range to 1-well illuminate all the points of a line segment with an O(n^2) algorithm. Finally, we give an O(n^2 log n) algorithm for preprocessing the data so that one can obtain the illumination range needed to 1-well illuminate a point of a line segment in O(log n) time. These results can be applied to solve problems of 1-well illuminating a trajectory by approaching it to a polygonal path.
Performance Analysis of Iterative Channel Estimation and Multiuser Detection in Multipath DS-CDMA Channels
Venue: arXiv cs.IT 2006
Year: 2006

This paper examines the performance of decision feedback based iterative channel estimation and multiuser detection in channel coded aperiodic DS-CDMA systems operating over multipath fading channels. First, explicit expressions describing the performance of channel estimation and parallel interference cancellation based multiuser detection are developed. These results are then combined to characterize the evolution of the performance of a system that iterates among channel estimation, multiuser detection and channel decoding. Sufficient conditions for convergence of this system to a unique fixed point are developed.
Emerging Markets for RFID Traces
Venue: arXiv cs.CY 2006
Year: 2006

RFID tags are held to become ubiquitous in logistics in the near future, and item-level tagging will pave the way for Ubiquitous Computing, for example in application fields like smart homes. Our paper addresses the value and the production cost of information that can be gathered by observing these tags over time and different locations. We argue that RFID technology will induce a thriving market for such information, resulting in easy data access for analysts to infer business intelligence and individual profiles of unusually high detail. Understanding these information markets is important for many reasons: They represent new business opportunities, and market players need to be aware of their roles in these markets. Policy makers need to confirm that the market structure will not negatively affect overall welfare. Finally, though we are not addressing the complex issue of privacy, we are convinced that market forces will have a significant impact on the effectiveness of deployed security enhancements to RFID technology. In this paper we take a few first steps into a relatively new field of economic research and conclude with a list of research problems that promise deeper insights into the matter.
Generating parity check equations for bounded-distance iterative erasure decoding
Venue: arXiv cs.IT 2006
Year: 2006

A generic $(r,m)$-erasure correcting set is a collection of vectors in $\bF_2^r$ which can be used to generate, for each binary linear code of codimension $r$, a collection of parity check equations that enables iterative decoding of all correctable erasure patterns of size at most $m$. That is to say, the only stopping sets of size at most $m$ for the generated parity check equations are the erasure patterns for which there is more than one manner to fill in theerasures to obtain a codeword. We give an explicit construction of generic $(r,m)$-erasure correcting sets of cardinality $\sum_{i=0}^{m-1} {r-1\choose i}$. Using a random-coding-like argument, we show that for fixed $m$, the minimum size of a generic $(r,m)$-erasure correcting set is linear in $r$. Keywords: iterative decoding, binary erasure channel, stopping set
Finding roots of polynomials over finite fields
Venue: arXiv cs.IT 2006
Year: 2006

We propose an improved algorithm for finding roots of polynomials over finite fields. This makes possible significant speedup of the decoding process of Bose-Chaudhuri-Hocquenghem, Reed-Solomon, and some other error-correcting codes.
Schedule generation schemes for the job-shop problem with sequence-dependent setup times: dominance properties and computational analysis
Venue: arXiv cs.CC 2006
Year: 2006

We consider the job-shop problem with sequence-dependent setup times. We focus on the formal definition of schedule generation schemes (SGSs) based on the semi-active, active, and non-delay schedule categories. We study dominance properties of the sets of schedules obtainable with each SGS. We show how the proposed SGSs can be used within single-pass and multi-pass priority rule based heuristics. We study several priority rules for the problem and provide a comparative computational analysis of the different SGSs on sets of instances taken from the literature. The proposed SGSs significantly improve previously best-known results on a set of hard benchmark instances.
The Cumulative Rule for Belief Fusion
Venue: arXiv cs.AI 2006
Year: 2006

The problem of combining beliefs in the Dempster-Shafer belief theory has attracted considerable attention over the last two decades. The classical Dempster's Rule has often been criticised, and many alternative rules for belief combination have been proposed in the literature. The consensus operator for combining beliefs has nice properties and produces more intuitive results than Dempster's rule, but has the limitation that it can only be applied to belief distribution functions on binary state spaces. In this paper we present a generalisation of the consensus operator that can be applied to Dirichlet belief functions on state spaces of arbitrary size. This rule, called the cumulative rule of belief combination, can be derived from classical statistical theory, and corresponds well with human intuition.
Is there an Elegant Universal Theory of Prediction?
Venue: arXiv cs.AI 2006
Year: 2006

Solomonoff's inductive learning model is a powerful, universal and highly elegant theory of sequence prediction. Its critical flaw is that it is incomputable and thus cannot be used in practice. It is sometimes suggested that it may still be useful to help guide the development of very general and powerful theories of prediction which are computable. In this paper it is shown that although powerful algorithms exist, they are necessarily highly complex. This alone makes their theoretical analysis problematic, however it is further shown that beyond a moderate level of complexity the analysis runs into the deeper problem of Goedel incompleteness. This limits the power of mathematics to analyse and study prediction algorithms, and indeed intelligent systems in general.
A Flexible Bandwidth Reservation Framework for Bulk Data Transfers in Grid Networks
Venue: arXiv cs.NI 2006
Year: 2006

In grid networks, distributed resources are interconnected by wide area network to support compute and data-intensive applications, which require reliable and efficient transfer of gigabits (even terabits) of data. Different from best-effort traffic in Internet, bulk data transfer in grid requires bandwidth reservation as a fundamental service. Existing reservation schemes such as RSVP are designed for real-time traffic specified by reservation rate, transfer start time but with unknown lifetime. In comparison, bulk data transfer requests are defined in terms of volume and deadline, which provide more information, and allow more flexibility in reservation schemes, i.e., transfer start time can be flexibly chosen, and reservation for a single request can be divided into multiple intervals with different reservation rates. We define a flexible reservation framework using time-rate function algebra, and identify a series of practical reservation scheme families with increasing generality and potential performance, namely, FixTime-FixRate, FixTime-FlexRate, FlexTime-FlexRate, and Multi-Interval. Simple heuristics are used to select representative scheme from each family for performance comparison. Simulation results show that the increasing flexibility can potentially improve system performance, minimizing both blocking probability and mean flow time. We also discuss the distributed implementation of proposed framework.