OpenRaiser/Intern-Atlas huggingface dataset:
An Outer Bound for the Multi-Terminal Rate-Distortion Region
Venue: arXiv cs.IT 2006
Year: 2006

The multi-terminal rate-distortion problem has been studied extensively. Notably, among these, Tung and Housewright have provided the best known inner and outer bounds for the rate region under certain distortion constraints. In this paper, we first propose an outer bound for the rate region, and show that it is tighter than the outer bound of Tung and Housewright. Our outer bound involves some $n$-letter Markov chain constraints, which cause computational difficulties. We utilize a necessary condition for the Markov chain constraints to obtain another outer bound, which is represented in terms of some single-letter mutual information expressions evaluated over probability distributions that satisfy some single-letter conditions.
Error Exponents of Low-Density Parity-Check Codes on the Binary Erasure Channel
Venue: arXiv cs.IT 2006
Year: 2006

We introduce a thermodynamic (large deviation) formalism for computing error exponents in error-correcting codes. Within this framework, we apply the heuristic cavity method from statistical mechanics to derive the average and typical error exponents of low-density parity-check (LDPC) codes on the binary erasure channel (BEC) under maximum-likelihood decoding.
DSR with Non-Optimal Route Suppression for MANETs
Venue: arXiv cs.NI 2006
Year: 2006

This paper revisits the issue of route discovery in dynamic source routing (DSR) for mobile ad hoc networks (MANETs), and puts forward a proposal of a lightweight non-optimal route suppression technique based on the observation of a rarely noted but commonly occurring phenomenon in route discovery. The technique exploits the observed phenomenon to extract query state information that permits intermediate nodes to identify and suppress the initiation of route replies with non-optimal routes, even if the route query is received for the first time. A detailed evaluation of DSR with non-optimal route suppression is found to yield significant improvements in both protocol efficiency and performance.
The meaning of manufacturing know-how
Venue: arXiv cs.AI 2006
Year: 2006

This paper investigates the phenomenon of manufacturing know-how. First, the abstract notion of knowledge is discussed, and a terminological basis is introduced to treat know-how as a kind of knowledge. Next, a brief survey of the recently reported works dealt with manufacturing know-how is presented, and an explicit definition of know-how is formulated. Finally, the problem of utilizing know-how with knowledge-based systems is analyzed, and some ideas useful for its solving are given.
General Compact Labeling Schemes for Dynamic Trees
Venue: arXiv cs.DC 2006
Year: 2006

Let $F$ be a function on pairs of vertices. An {\em $F$- labeling scheme} is composed of a {\em marker} algorithm for labeling the vertices of a graph with short labels, coupled with a {\em decoder} algorithm allowing one to compute $F(u,v)$ of any two vertices $u$ and $v$ directly from their labels. As applications for labeling schemes concern mainly large and dynamically changing networks, it is of interest to study {\em distributed dynamic} labeling schemes. This paper investigates labeling schemes for dynamic trees. This paper presents a general method for constructing labeling schemes for dynamic trees. Our method is based on extending an existing {\em static} tree labeling scheme to the dynamic setting. This approach fits many natural functions on trees, such as ancestry relation, routing (in both the adversary and the designer port models), nearest common ancestor etc.. Our resulting dynamic schemes incur overheads (over the static scheme) on the label size and on the communication complexity. Informally, for any function $k(n)$ and any static $F$-labeling scheme on trees, we present an $F$-labeling scheme on dynamic trees incurring multiplicative overhead factors (over the static scheme) of $O(\log_{k(n)} n)$ on the label size and $O(k(n)\log_{k(n)} n)$ on the amortized message complexity. In particular, by setting $k(n)=n^ε$ for any $0<ε<1$, we obtain dynamic labeling schemes with asymptotically optimal label sizes and sublinear amortized message complexity for all the above mentioned functions.
On the communication between cells of a cellular automaton on the penta- and heptagrids of the hyperbolic plane
Venue: arXiv cs.CG 2006
Year: 2006

This contribution belongs to a combinatorial approach to hyperbolic geometry and it is aimed at possible applications to computer simulations. It is based on the splitting method which was introduced by the author and which is reminded in the second section of the paper. Then we sketchily remind the application to the classical case of the pentagrid, i.e. the tiling of the hyperbolic plane which is generated by reflections of the regular rectangular pentagon in its sides and, recursively, of its images in their sides. From this application, we derived a system of coordinates to locate the tiles, allowing an implementation of cellular automata. At the software level, cells exchange messages thanks to a new representation which improves the speed of contacts between cells. In the new setting, communications are exchanged along actual geodesics and the contribution of the cellular automaton is also linear in the coordinates of the cells.
On the Capacity of Multiple Access Channels with State Information and Feedback
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, the multiple access channel (MAC) with channel state is analyzed in a scenario where a) the channel state is known non-causally to the transmitters and b) there is perfect causal feedback from the receiver to the transmitters. An achievable region and an outer bound are found for a discrete memoryless MAC that extend existing results, bringing together ideas from the two separate domains of MAC with state and MAC with feedback. Although this achievable region does not match the outer bound in general, special cases where they meet are identified. In the case of a Gaussian MAC, a specialized achievable region is found by using a combination of dirty paper coding and a generalization of the Schalkwijk-Kailath, Ozarow and Merhav-Weissman schemes, and this region is found to be capacity achieving. Specifically, it is shown that additive Gaussian interference that is known non-causally to the transmitter causes no loss in capacity for the Gaussian MAC with feedback.
Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements
Venue: arXiv cs.CC 2006
Year: 2006

Let S = <s_1, s_2, s_3, ..., s_n> be a given vector of n real numbers. The rank of a real z with respect to S is defined as the number of elements s_i in S such that s_i is less than or equal to z. We consider the following decision problem: determine whether the odd-numbered elements s_1, s_3, s_5, ... are precisely the elements of S whose rank with respect to S is odd. We prove a bound of Theta(n log n) on the number of operations required to solve this problem in the algebraic computation tree model.
Evolutionary Design: Philosophy, Theory, and Application Tactics
Venue: arXiv cs.CE 2006
Year: 2006

Although it has contributed to remarkable improvements in some specific areas, attempts to develop a universal design theory are generally characterized by failure. This paper sketches arguments for a new approach to engineering design based on Semiotics - the science about signs. The approach is to combine different design theories over all the product life cycle stages into one coherent and traceable framework. Besides, it is to bring together the designer's and user's understandings of the notion of 'good product'. Building on the insight from natural sciences that complex systems always exhibit a self-organizing meaning-influential hierarchical dynamics, objective laws controlling product development are found through an examination of design as a semiosis process. These laws are then applied to support evolutionary design of products. An experiment validating some of the theoretical findings is outlined, and concluding remarks are given.
Authorised Translations of Electronic Documents
Venue: arXiv cs.OH 2006
Year: 2006

A concept is proposed to extend authorised translations of documents to electronically signed, digital documents. Central element of the solution is an electronic seal, embodied as an XML data structure, which attests to the correctness of the translation and the authorisation of the translator. The seal contains a digital signature binding together original and translated document, thus enabling forensic inspection and therefore legal security in the appropriation of the translation. Organisational aspects of possible implementation variants of electronic authorised translations are discussed and a realisation as a stand-alone web-service is presented.
Asynchronous iterative computations with Web information retrieval structures: The PageRank case
Venue: arXiv cs.DC 2006
Year: 2006

There are several ideas being used today for Web information retrieval, and specifically in Web search engines. The PageRank algorithm is one of those that introduce a content-neutral ranking function over Web pages. This ranking is applied to the set of pages returned by the Google search engine in response to posting a search query. PageRank is based in part on two simple common sense concepts: (i)A page is important if many important pages include links to it. (ii)A page containing many links has reduced impact on the importance of the pages it links to. In this paper we focus on asynchronous iterative schemes to compute PageRank over large sets of Web pages. The elimination of the synchronizing phases is expected to be advantageous on heterogeneous platforms. The motivation for a possible move to such large scale distributed platforms lies in the size of matrices representing Web structure. In orders of magnitude: $10^{10}$ pages with $10^{11}$ nonzero elements and $10^{12}$ bytes just to store a small percentage of the Web (the already crawled); distributed memory machines are necessary for such computations. The present research is part of our general objective, to explore the potential of asynchronous computational models as an underlying framework for very large scale computations over the Grid. The area of ``internet algorithmics'' appears to offer many occasions for computations of unprecedent dimensionality that would be good candidates for this framework.
Decentralized Erasure Codes for Distributed Networked Storage
Venue: arXiv cs.IT 2006
Year: 2006

We consider the problem of constructing an erasure code for storage over a network when the data sources are distributed. Specifically, we assume that there are n storage nodes with limited memory and k<n sources generating the data. We want a data collector, who can appear anywhere in the network, to query any k storage nodes and be able to retrieve the data. We introduce Decentralized Erasure Codes, which are linear codes with a specific randomized structure inspired by network coding on random bipartite graphs. We show that decentralized erasure codes are optimally sparse, and lead to reduced communication, storage and computation cost over random linear coding.
Syntactic Characterisations of Polynomial-Time Optimisation Classes (Syntactic Characterizations of Polynomial-Time Optimization Classes)
Venue: arXiv cs.CC 2006
Year: 2006

In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as \textbf{P, NP, L and NL}. ~ However, research on the descriptive complexity of optimisation problems has been limited. Optimisation problems corresponding to the \textbf{NP} class have been characterised in terms of logic expressions by Papadimitriou and Yannakakis, Panconesi and Ranjan, Kolaitis and Thakur, Khanna et al, and by Zimand. Grädel characterised the polynomial class \textbf{P} of decision problems. In this paper, we attempt to characterise the optimisation versions of \textbf{P} via expressions in second order logic, many of them using universal Horn formulae with successor relations. The polynomially bound versions of maximisation (maximization) and minimisation (minimization) problems are treated first, and then the maximisation problems in the "not necessarily polynomially bound" class.
Context-Sensitive Languages, Rational Graphs and Determinism
Venue: arXiv cs.LO 2006
Year: 2006

We investigate families of infinite automata for context-sensitive languages. An infinite automaton is an infinite labeled graph with two sets of initial and final vertices. Its language is the set of all words labelling a path from an initial vertex to a final vertex. In 2001, Morvan and Stirling proved that rational graphs accept the context-sensitive languages between rational sets of initial and final vertices. This result was later extended to sub-families of rational graphs defined by more restricted classes of transducers. languages.<br><br> Our contribution is to provide syntactical and self-contained proofs of the above results, when earlier constructions relied on a non-trivial normal form of context-sensitive grammars defined by Penttonen in the 1970's. These new proof techniques enable us to summarize and refine these results by considering several sub-families defined by restrictions on the type of transducers, the degree of the graph or the size of the set of initial vertices.
Logics for Unranked Trees: An Overview
Venue: arXiv cs.LO 2006
Year: 2006

Labeled unranked trees are used as a model of XML documents, and logical languages for them have been studied actively over the past several years. Such logics have different purposes: some are better suited for extracting data, some for expressing navigational properties, and some make it easy to relate complex properties of trees to the existence of tree automata for those properties. Furthermore, logics differ significantly in their model-checking properties, their automata models, and their behavior on ordered and unordered trees. In this paper we present a survey of logics for unranked trees.
FLAIM: A Multi-level Anonymization Framework for Computer and Network Logs
Venue: arXiv cs.CR 2006
Year: 2006

FLAIM (Framework for Log Anonymization and Information Management) addresses two important needs not well addressed by current log anonymizers. First, it is extremely modular and not tied to the specific log being anonymized. Second, it supports multi-level anonymization, allowing system administrators to make fine-grained trade-offs between information loss and privacy/security concerns. In this paper, we examine anonymization solutions to date and note the above limitations in each. We further describe how FLAIM addresses these problems, and we describe FLAIM's architecture and features in detail.
Rate Regions for Relay Broadcast Channels
Venue: arXiv cs.IT 2006
Year: 2006

A partially cooperative relay broadcast channel (RBC) is a three-node network with one source node and two destination nodes (destinations 1 and 2) where destination 1 can act as a relay to assist destination 2. Inner and outer bounds on the capacity region of the discrete memoryless partially cooperative RBC are obtained. When the relay function is disabled, the inner and outer bounds reduce to new bounds on the capacity region of broadcast channels. Four classes of RBCs are studied in detail. For the partially cooperative RBC with degraded message sets, inner and outer bounds are obtained. For the semideterministic partially cooperative RBC and the orthogonal partially cooperative RBC, the capacity regions are established. For the parallel partially cooperative RBC with unmatched degraded subchannels, the capacity region is established for the case of degraded message sets. The capacity is also established when the source node has only a private message for destination 2, i.e., the channel reduces to a parallel relay channel with unmatched degraded subchannels.
On Sequence Prediction for Arbitrary Measures
Venue: arXiv cs.LG 2006
Year: 2006

Suppose we are given two probability measures on the set of one-way infinite finite-alphabet sequences and consider the question when one of the measures predicts the other, that is, when conditional probabilities converge (in a certain sense) when one of the measures is chosen to generate the sequence. This question may be considered a refinement of the problem of sequence prediction in its most general formulation: for a given class of probability measures, does there exist a measure which predicts all of the measures in the class? To address this problem, we find some conditions on local absolute continuity which are sufficient for prediction and which generalize several different notions which are known to be sufficient for prediction. We also formulate some open questions to outline a direction for finding the conditions on classes of measures for which prediction is possible.
The Diversity Order of the Semidefinite Relaxation Detector
Venue: arXiv cs.IT 2006
Year: 2006

We consider the detection of binary (antipodal) signals transmitted in a spatially multiplexed fashion over a fading multiple-input multiple-output (MIMO) channel and where the detection is done by means of semidefinite relaxation (SDR). The SDR detector is an attractive alternative to maximum likelihood (ML) detection since the complexity is polynomial rather than exponential. Assuming that the channel matrix is drawn with i.i.d. real valued Gaussian entries, we study the receiver diversity and prove that the SDR detector achieves the maximum possible diversity. Thus, the error probability of the receiver tends to zero at the same rate as the optimal maximum likelihood (ML) receiver in the high signal to noise ratio (SNR) limit. This significantly strengthens previous performance guarantees available for the semidefinite relaxation detector. Additionally, it proves that full diversity detection is in certain scenarios also possible when using a non-combinatorial receiver structure.
Provably Secure Universal Steganographic Systems
Venue: arXiv cs.CR 2006
Year: 2006

We propose a simple universal (that is, distribution--free) steganographic system in which covertexts with and without hidden texts are statistically indistinguishable. The stegosystem can be applied to any source generating i.i.d. covertexts with unknown distribution, and the hidden text is transmitted exactly, with zero probability of error. Moreover, the proposed steganographic system has two important properties. First, the rate of transmission of hidden information approaches the Shannon entropy of the covertext source as the size of blocks used for hidden text encoding tends to infinity. Second, if the size of the alphabet of the covertext source and its minentropy tend to infinity then the number of bits of hidden text per letter of covertext tends to $\log(n!)/n$ where $n$ is the (fixed) size of blocks used for hidden text encoding. The proposed stegosystem uses randomization.
Uniform Random Sampling of Traces in Very Large Models
Venue: arXiv cs.LO 2006
Year: 2006

This paper presents some first results on how to perform uniform random walks (where every trace has the same probability to occur) in very large models. The models considered here are described in a succinct way as a set of communicating reactive modules. The method relies upon techniques for counting and drawing uniformly at random words in regular languages. Each module is considered as an automaton defining such a language. It is shown how it is possible to combine local uniform drawings of traces, and to obtain some global uniform random sampling, without construction of the global model.
On Typechecking Top-Down XML Tranformations: Fixed Input or Output Schemas
Venue: arXiv cs.DB 2006
Year: 2006

Typechecking consists of statically verifying whether the output of an XML transformation always conforms to an output type for documents satisfying a given input type. In this general setting, both the input and output schema as well as the transformation are part of the input for the problem. However, scenarios where the input or output schema can be considered to be fixed, are quite common in practice. In the present work, we investigate the computational complexity of the typechecking problem in the latter setting.
Synonym search in Wikipedia: Synarcher
Venue: arXiv cs.IR 2006
Year: 2006

The program Synarcher for synonym (and related terms) search in the text corpus of special structure (Wikipedia) was developed. The results of the search are presented in the form of graph. It is possible to explore the graph and search for graph elements interactively. Adapted HITS algorithm for synonym search, program architecture, and program work evaluation with test examples are presented in the paper. The proposed algorithm can be applied to a query expansion by synonyms (in a search engine) and a synonym dictionary forming.
Models simulation and interoperability using MDA and HLA
Venue: arXiv cs.OH 2006
Year: 2006

In the manufacturing context, there have been numerous efforts to use modeling and simulation tools and techniques to improve manufacturing efficiency over the last four decades. While an increasing number of manufacturing system decisions are being made based on the use of models, their use is still sporadic in many manufacturing environments. Our paper advocates for an approach combining MDA (model driven architecture) and HLA (High Level Architecture), the IEEE standard for modeling and simulation, in order to overcome the deficiencies of current simulation methods at the level of interoperability and reuse.
Adapting a general parser to a sublanguage
Venue: arXiv cs.CL 2006
Year: 2006

In this paper, we propose a method to adapt a general parser (Link Parser) to sublanguages, focusing on the parsing of texts in biology. Our main proposal is the use of terminology (identication and analysis of terms) in order to reduce the complexity of the text to be parsed. Several other strategies are explored and finally combined among which text normalization, lexicon and morpho-guessing module extensions and grammar rules adaptation. We compare the parsing results before and after these adaptations.
May We Have Your Attention: Analysis of a Selective Attention Task
Venue: arXiv cs.NE 2006
Year: 2006

In this paper we present a deeper analysis than has previously been carried out of a selective attention problem, and the evolution of continuous-time recurrent neural networks to solve it. We show that the task has a rich structure, and agents must solve a variety of subproblems to perform well. We consider the relationship between the complexity of an agent and the ease with which it can evolve behavior that generalizes well across subproblems, and demonstrate a shaping protocol that improves generalization.
Automatic forming lists of semantically related terms based on texts rating in the corpus with hyperlinks and categories (In Russian)
Venue: arXiv cs.IR 2006
Year: 2006

HITS adapted algorithm for synonym search, the program architecture, and the program work evaluation with test examples are presented in the paper. Synarcher program for synonym (and related terms) search in the text corpus of special structure (Wikipedia) was developed. The results of search are presented in the form of a graph. It is possible to explore the graph and search graph elements interactively. The proposed algorithm could be applied to the search request extending and for synonym dictionary forming.