OpenRaiser/Intern-Atlas huggingface dataset:
ATNoSFERES revisited
Venue: arXiv cs.AI 2005
Year: 2005

ATNoSFERES is a Pittsburgh style Learning Classifier System (LCS) in which the rules are represented as edges of an Augmented Transition Network. Genotypes are strings of tokens of a stack-based language, whose execution builds the labeled graph. The original ATNoSFERES, using a bitstring to represent the language tokens, has been favorably compared in previous work to several Michigan style LCSs architectures in the context of Non Markov problems. Several modifications of ATNoSFERES are proposed here: the most important one conceptually being a representational change: each token is now represented by an integer, hence the genotype is a string of integers; several other modifications of the underlying grammar language are also proposed. The resulting ATNoSFERES-II is validated on several standard animat Non Markov problems, on which it outperforms all previously published results in the LCS literature. The reasons for these improvement are carefully analyzed, and some assumptions are proposed on the underlying mechanisms in order to explain these good results.
The error-floor of LDPC codes in the Laplacian channel
Venue: arXiv cs.IT 2005
Year: 2005

We analyze the performance of Low-Density-Parity-Check codes in the error-floor domain where the Signal-to-Noise-Ratio, s, is large, s >> 1. We describe how the instanton method of theoretical physics, recently adapted to coding theory, solves the problem of characterizing the error-floor domain in the Laplacian channel. An example of the (155,64,20) LDPC code with four iterations (each iteration consisting of two semi-steps: from bits-to-checks and from checks-to-bits) of the min-sum decoding is discussed. A generalized computational tree analysis is devised to explain the rational structure of the leading instantons. The asymptotic for the symbol Bit-Error-Rate in the error-floor domain is comprised of individual instanton contributions, each estimated as ~ \exp(-l_{inst;L} s), where the effective distances, l_{inst;L}, of the the leading instantons are 7.6, 8.0 and 8.0 respectively. (The Hamming distance of the code is 20.) The analysis shows that the instantons are distinctly different from the ones found for the same coding/decoding scheme performing over the Gaussian channel. We validate instanton results against direct simulations and offer an explanation for remarkable performance of the instanton approximation not only in the extremal, s -> \infty, limit but also at the moderate s values of practical interest.
ReacProc: A Tool to Process Reactions Describing Particle Interactions
Venue: arXiv cs.CE 2005
Year: 2005

ReacProc is a program written in C/C++ programming language which can be used (1) to check out of reactions describing particles interactions against conservation laws and (2) to reduce input reaction into some canonical form. A table with particles properties is available within ReacProc package.
Data complexity of answering conjunctive queries over SHIQ knowledge bases
Venue: arXiv cs.LO 2005
Year: 2005

An algorithm for answering conjunctive queries over SHIQ knowledge bases that is coNP in data complexity is given. The algorithm is based on the tableau algorithm for reasoning with individuals in SHIQ. The blocking conditions of the tableau are weakened in such a way that the set of models the modified algorithm yields suffices to check query entailment. The modified blocking conditions are based on the ones proposed by Levy and Rousset for reasoning with Horn Rules in the description logic ALCNR.
Authentication Schemes Using Braid Groups
Venue: arXiv cs.CR 2005
Year: 2005

In this paper we proposed two identification schemes based on the root problem. The proposed schemes are secure against passive attacks assuming that the root problem (RP) is hard in braid groups.
Conjunctive Query Containment and Answering under Description Logics Constraints
Venue: arXiv cs.DB 2005
Year: 2005

Query containment and query answering are two important computational tasks in databases. While query answering amounts to compute the result of a query over a database, query containment is the problem of checking whether for every database, the result of one query is a subset of the result of another query. In this paper, we deal with unions of conjunctive queries, and we address query containment and query answering under Description Logic constraints. Every such constraint is essentially an inclusion dependencies between concepts and relations, and their expressive power is due to the possibility of using complex expressions, e.g., intersection and difference of relations, special forms of quantification, regular expressions over binary relations, in the specification of the dependencies. These types of constraints capture a great variety of data models, including the relational, the entity-relationship, and the object-oriented model, all extended with various forms of constraints, and also the basic features of the ontology languages used in the context of the Semantic Web. We present the following results on both query containment and query answering. We provide a method for query containment under Description Logic constraints, thus showing that the problem is decidable, and analyze its computational complexity. We prove that query containment is undecidable in the case where we allow inequalities in the right-hand side query, even for very simple constraints and queries. We show that query answering under Description Logic constraints can be reduced to query containment, and illustrate how such a reduction provides upper bound results with respect to both combined and data complexity.
Users and Assessors in the Context of INEX: Are Relevance Dimensions Relevant?
Venue: arXiv cs.IR 2005
Year: 2005

The main aspects of XML retrieval are identified by analysing and comparing the following two behaviours: the behaviour of the assessor when judging the relevance of returned document components; and the behaviour of users when interacting with components of XML documents. We argue that the two INEX relevance dimensions, Exhaustivity and Specificity, are not orthogonal dimensions; indeed, an empirical analysis of each dimension reveals that the grades of the two dimensions are correlated to each other. By analysing the level of agreement between the assessor and the users, we aim at identifying the best units of retrieval. The results of our analysis show that the highest level of agreement is on highly relevant and on non-relevant document components, suggesting that only the end points of the INEX 10-point relevance scale are perceived in the same way by both the assessor and the users. We propose a new definition of relevance for XML retrieval and argue that its corresponding relevance scale would be a better choice for INEX.
Reliable Data Storage in Distributed Hash Tables
Venue: arXiv cs.DC 2005
Year: 2005

Distributed Hash Tables offer a resilient lookup service for unstable distributed environments. Resilient data storage, however, requires additional data replication and maintenance algorithms. These algorithms can have an impact on both the performance and the scalability of the system. In this paper, we describe the goals and design space of these replication algorithms. We examine an existing replication algorithm, and present a new analysis of its reliability. We then present a new dynamic replication algorithm which can operate in unstable environments. We give several possible replica placement strategies for this algorithm, and show how they impact reliability and performance. Finally we compare all replication algorithms through simulation, showing quantitatively the difference between their bandwidth use, fault tolerance and performance.
Dimensions of Copeland-Erdos Sequences
Venue: arXiv cs.CC 2005
Year: 2005

The base-$k$ {\em Copeland-Erdös sequence} given by an infinite set $A$ of positive integers is the infinite sequence $\CE_k(A)$ formed by concatenating the base-$k$ representations of the elements of $A$ in numerical order. This paper concerns the following four quantities. The {\em finite-state dimension} $\dimfs (\CE_k(A))$, a finite-state version of classical Hausdorff dimension introduced in 2001. The {\em finite-state strong dimension} $\Dimfs(\CE_k(A))$, a finite-state version of classical packing dimension introduced in 2004. This is a dual of $\dimfs(\CE_k(A))$ satisfying $\Dimfs(\CE_k(A))$ $\geq \dimfs(\CE_k(A))$. The {\em zeta-dimension} $\Dimzeta(A)$, a kind of discrete fractal dimension discovered many times over the past few decades. The {\em lower zeta-dimension} $\dimzeta(A)$, a dual of $\Dimzeta(A)$ satisfying $\dimzeta(A)\leq \Dimzeta(A)$. We prove the following. $\dimfs(\CE_k(A))\geq \dimzeta(A)$. This extends the 1946 proof by Copeland and Erdös that the sequence $\CE_k(\mathrm{PRIMES})$ is Borel normal. $\Dimfs(\CE_k(A))\geq \Dimzeta(A)$. These bounds are tight in the strong sense that these four quantities can have (simultaneously) any four values in $[0,1]$ satisfying the four above-mentioned inequalities.
A three-valued semantics for logic programmers
Venue: arXiv cs.LO 2005
Year: 2005

This paper describes a simpler way for programmers to reason about the correctness of their code. The study of semantics of logic programs has shown strong links between the model theoretic semantics (truth and falsity of atoms in the programmer's interpretation of a program), procedural semantics (for example, SLD resolution) and fixpoint semantics (which is useful for program analysis and alternative execution mechanisms). Most of this work assumes that intended interpretations are two-valued: a ground atom is true (and should succeed according to the procedural semantics) or false (and should not succeed). In reality, intended interpretations are less precise. Programmers consider that some atoms "should not occur" or are "ill-typed" or "inadmissible". Programmers don't know and don't care whether such atoms succeed. In this paper we propose a three-valued semantics for (essentially) pure Prolog programs with (ground) negation as failure which reflects this. The semantics of Fitting is similar but only associates the third truth value with non-termination. We provide tools to reason about correctness of programs without the need for unnatural precision or undue restrictions on programming style. As well as theoretical results, we provide a programmer-oriented synopsis. This work has come out of work on declarative debugging, where it has been recognised that inadmissible calls are important. This paper has been accepted to appear in Theory and Practice of Logic Programming.
A New Approach for Boundary Recognition in Geometric Sensor Networks
Venue: arXiv cs.DS 2005
Year: 2005

We describe a new approach for dealing with the following central problem in the self-organization of a geometric sensor network: Given a polygonal region R, and a large, dense set of sensor nodes that are scattered uniformly at random in R. There is no central control unit, and nodes can only communicate locally by wireless radio to all other nodes that are within communication radius r, without knowing their coordinates or distances to other nodes. The objective is to develop a simple distributed protocol that allows nodes to identify themselves as being located near the boundary of R and form connected pieces of the boundary. We give a comparison of several centrality measures commonly used in the analysis of social networks and show that restricted stress centrality is particularly suited for geometric networks; we provide mathematical as well as experimental evidence for the quality of this measure.
IMPACT: Investigation of Mobile-user Patterns Across University Campuses using WLAN Trace Analysis
Venue: arXiv cs.NI 2005
Year: 2005

We conduct the most comprehensive study of WLAN traces to date. Measurements collected from four major university campuses are analyzed with the aim of developing fundamental understanding of realistic user behavior in wireless networks. Both individual user and inter-node (group) behaviors are investigated and two classes of metrics are devised to capture the underlying structure of such behaviors. For individual user behavior we observe distinct patterns in which most users are 'on' for a small fraction of the time, the number of access points visited is very small and the overall on-line user mobility is quite low. We clearly identify categories of heavy and light users. In general, users exhibit high degree of similarity over days and weeks. For group behavior, we define metrics for encounter patterns and friendship. Surprisingly, we find that a user, on average, encounters less than 6% of the network user population within a month, and that encounter and friendship relations are highly asymmetric. We establish that number of encounters follows a biPareto distribution, while friendship indexes follow an exponential distribution. We capture the encounter graph using a small world model, the characteristics of which reach steady state after only one day. We hope for our study to have a great impact on realistic modeling of network usage and mobility patterns in wireless networks.
Distributed Algorithms for Optimal Rate-Reliability Tradeoff in Networks
Venue: arXiv cs.NI 2005
Year: 2005

The current framework of network utility maximization for distributed rate allocation assumes fixed channel code rates. However, by adapting the physical layer channel coding, different rate-reliability tradeoffs can be achieved on each link and for each end user. Consider a network where each user has a utility function that depends on both signal quality and data rate, and each link may provide a `fatter' (`thinner') information `pipe' by allowing a higher (lower) decoding error probability. We propose two distributed, pricing-based algorithms to attain optimal rate-reliability tradeoff, with an interpretation that each user provides its willingness to pay for reliability to the network and the network feeds back congestion prices to users. The proposed algorithms converge to a tradeoff point between rate and reliability, which is proved to be globally optimal for codes with sufficiently large codeword lengths and user utilities with sufficiently negative curvatures.
Signature coding for OR channel with asynchronous access
Venue: arXiv cs.IT 2005
Year: 2005

Signature coding for multiple access OR channel is considered. We prove that in block asynchronous case the upper bound on the minimum code length asymptotically is the same as in the case of synchronous access.
Expectation maximization as message passing
Venue: arXiv cs.IT 2005
Year: 2005

Based on prior work by Eckford, it is shown how expectation maximization (EM) may be viewed, and used, as a message passing algorithm in factor graphs.
Selfish vs. Unselfish Optimization of Network Creation
Venue: arXiv cs.NI 2005
Year: 2005

We investigate several variants of a network creation model: a group of agents builds up a network between them while trying to keep the costs of this network small. The cost function consists of two addends, namely (i) a constant amount for each edge an agent buys and (ii) the minimum number of hops it takes sending messages to other agents. Despite the simplicity of this model, various complex network structures emerge depending on the weight between the two addends of the cost function and on the selfish or unselfish behaviour of the agents.
Polymorphic Self-* Agents for Stigmergic Fault Mitigation in Large-Scale Real-Time Embedded Systems
Venue: arXiv cs.AI 2005
Year: 2005

Organization and coordination of agents within large-scale, complex, distributed environments is one of the primary challenges in the field of multi-agent systems. A lot of interest has surfaced recently around self-* (self-organizing, self-managing, self-optimizing, self-protecting) agents. This paper presents polymorphic self-* agents that evolve a core set of roles and behavior based on environmental cues. The agents adapt these roles based on the changing demands of the environment, and are directly implementable in computer systems applications. The design combines strategies from game theory, stigmergy, and other biologically inspired models to address fault mitigation in large-scale, real-time, distributed systems. The agents are embedded within the individual digital signal processors of BTeV, a High Energy Physics experiment consisting of 2500 such processors. Results obtained using a SWARM simulation of the BTeV environment demonstrate the polymorphic character of the agents, and show how this design exceeds performance and reliability metrics obtained from comparable centralized, and even traditional decentralized approaches.
Lessons from Three Views of the Internet Topology
Venue: arXiv cs.NI 2005
Year: 2005

Network topology plays a vital role in understanding the performance of network applications and protocols. Thus, recently there has been tremendous interest in generating realistic network topologies. Such work must begin with an understanding of existing network topologies, which today typically consists of a relatively small number of data sources. In this paper, we calculate an extensive set of important characteristics of Internet AS-level topologies extracted from the three data sources most frequently used by the research community: traceroutes, BGP, and WHOIS. We find that traceroute and BGP topologies are similar to one another but differ substantially from the WHOIS topology. We discuss the interplay between the properties of the data sources that result from specific data collection mechanisms and the resulting topology views. We find that, among metrics widely considered, the joint degree distribution appears to fundamentally characterize Internet AS-topologies: it narrowly defines values for other important metrics. We also introduce an evaluation criteria for the accuracy of topology generators and verify previous observations that generators solely reproducing degree distributions cannot capture the full spectrum of critical topological characteristics of any of the three topologies. Finally, we release to the community the input topology datasets, along with the scripts and output of our calculations. This supplement should enable researchers to validate their models against real data and to make more informed selection of topology data sources for their specific needs.
Very Simple Chaitin Machines for Concrete AIT
Venue: arXiv cs.IT 2005
Year: 2005

In 1975, Chaitin introduced his celebrated Omega number, the halting probability of a universal Chaitin machine, a universal Turing machine with a prefix-free domain. The Omega number's bits are {\em algorithmically random}--there is no reason the bits should be the way they are, if we define ``reason'' to be a computable explanation smaller than the data itself. Since that time, only {\em two} explicit universal Chaitin machines have been proposed, both by Chaitin himself. Concrete algorithmic information theory involves the study of particular universal Turing machines, about which one can state theorems with specific numerical bounds, rather than include terms like O(1). We present several new tiny Chaitin machines (those with a prefix-free domain) suitable for the study of concrete algorithmic information theory. One of the machines, which we call Keraia, is a binary encoding of lambda calculus based on a curried lambda operator. Source code is included in the appendices. We also give an algorithm for restricting the domain of blank-endmarker machines to a prefix-free domain over an alphabet that does not include the endmarker; this allows one to take many universal Turing machines and construct universal Chaitin machines from them.
Layered Orthogonal Lattice Detector for Two Transmit Antenna Communications
Venue: arXiv cs.IT 2005
Year: 2005

A novel detector for multiple-input multiple-output (MIMO) communications is presented. The algorithm belongs to the class of the lattice detectors, i.e. it finds a reduced complexity solution to the problem of finding the closest vector to the received observations. The algorithm achieves optimal maximum-likelihood (ML) performance in case of two transmit antennas, at the same time keeping a complexity much lower than the exhaustive search-based ML detection technique. Also, differently from the state-of-art lattice detector (namely sphere decoder), the proposed algorithm is suitable for a highly parallel hardware architecture and for a reliable bit soft-output information generation, thus making it a promising option for real-time high-data rate transmission.
Copyright and Promotion: Oxymoron or Opportunity?
Venue: arXiv cs.CY 2005
Year: 2005

Copyright in the cultural sphere can act as a barrier to the dissemination of high-quality information. On the other hand it protects works of art that might not be made available otherwise. This dichotomy makes the area of copyright difficult, especially when it applies to the digital arena of the web where copying is so easy and natural. Here we present a snapshot of the issues for online copyright, with particular emphasis on the relevance to cultural institutions. We concentrate on Europe and the US; as an example we include a special section dedicated to the situation in Italy.
Every decision tree has an influential variable
Venue: arXiv cs.CC 2005
Year: 2005

We prove that for any decision tree calculating a boolean function $f:\{-1,1\}^n\to\{-1,1\}$, \[ \Var[f] \le \sum_{i=1}^n δ_i \Inf_i(f), \] where $δ_i$ is the probability that the $i$th input variable is read and $\Inf_i(f)$ is the influence of the $i$th variable on $f$. The variance, influence and probability are taken with respect to an arbitrary product measure on $\{-1,1\}^n$. It follows that the minimum depth of a decision tree calculating a given balanced function is at least the reciprocal of the largest influence of any input variable. Likewise, any balanced boolean function with a decision tree of depth $d$ has a variable with influence at least $\frac{1}{d}$. The only previous nontrivial lower bound known was $Ω(d 2^{-d})$. Our inequality has many generalizations, allowing us to prove influence lower bounds for randomized decision trees, decision trees on arbitrary product probability spaces, and decision trees with non-boolean outputs. As an application of our results we give a very easy proof that the randomized query complexity of nontrivial monotone graph properties is at least $Ω(v^{4/3}/p^{1/3})$, where $v$ is the number of vertices and $p \leq \half$ is the critical threshold probability. This supersedes the milestone $Ω(v^{4/3})$ bound of Hajnal and is sometimes superior to the best known lower bounds of Chakrabarti-Khot and Friedgut-Kahn-Wigderson.