OpenRaiser/Intern-Atlas huggingface dataset:
Lack of Finite Characterizations for the Distance-based Revision
Venue: arXiv cs.LO 2006
Year: 2006

Lehmann, Magidor, and Schlechta developed an approach to belief revision based on distances between any two valuations. Suppose we are given such a distance D. This defines an operator |D, called a distance operator, which transforms any two sets of valuations V and W into the set V |D W of all elements of W that are closest to V. This operator |D defines naturally the revision of K by A as the set of all formulas satisfied in M(K) |D M(A) (i.e. those models of A that are closest to the models of K). This constitutes a distance-based revision operator. Lehmann et al. characterized families of them using a loop condition of arbitrarily big size. An interesting question is whether this loop condition can be replaced by a finite one. Extending the results of Schlechta, we will provide elements of negative answer. In fact, we will show that for families of distance operators, there is no "normal" characterization. Approximatively, a normal characterization contains only finite and universally quantified conditions. These results have an interest of their own for they help to understand the limits of what is possible in this area. Now, we are quite confident that this work can be continued to show similar impossibility results for distance-based revision operators, which suggests that the big loop condition cannot be simplified.
Static Analysis using Parameterised Boolean Equation Systems
Venue: arXiv cs.SE 2006
Year: 2006

The well-known problem of state space explosion in model checking is even more critical when applying this technique to programming languages, mainly due to the presence of complex data structures. One recent and promising approach to deal with this problem is the construction of an abstract and correct representation of the global program state allowing to match visited states during program model exploration. In particular, one powerful method to implement abstract matching is to fill the state vector with a minimal amount of relevant variables for each program point. In this paper, we combine the on-the-fly model-checking approach (incremental construction of the program state space) and the static analysis method called influence analysis (extraction of significant variables for each program point) in order to automatically construct an abstract matching function. Firstly, we describe the problem as an alternation-free value-based mu-calculus formula, whose validity can be checked on the program model expressed as a labeled transition system (LTS). Secondly, we translate the analysis into the local resolution of a parameterised boolean equation system (PBES), whose representation enables a more efficient construction of the resulting abstract matching function. Finally, we show how our proposal may be elegantly integrated into CADP, a generic framework for both the design and analysis of distributed systems and the development of verification tools.
Predictions as statements and decisions
Venue: arXiv cs.LG 2006
Year: 2006

Prediction is a complex notion, and different predictors (such as people, computer programs, and probabilistic theories) can pursue very different goals. In this paper I will review some popular kinds of prediction and argue that the theory of competitive on-line learning can benefit from the kinds of prediction that are now foreign to it.
Optimal Scheduling of Peer-to-Peer File Dissemination
Venue: arXiv cs.NI 2006
Year: 2006

Peer-to-peer (P2P) overlay networks such as BitTorrent and Avalanche are increasingly used for disseminating potentially large files from a server to many end users via the Internet. The key idea is to divide the file into many equally-sized parts and then let users download each part (or, for network coding based systems such as Avalanche, linear combinations of the parts) either from the server or from another user who has already downloaded it. However, their performance evaluation has typically been limited to comparing one system relative to another and typically been realized by means of simulation and measurements. In contrast, we provide an analytic performance analysis that is based on a new uplink-sharing version of the well-known broadcasting problem. Assuming equal upload capacities, we show that the minimal time to disseminate the file is the same as for the simultaneous send/receive version of the broadcasting problem. For general upload capacities, we provide a mixed integer linear program (MILP) solution and a complementary fluid limit solution. We thus provide a lower bound which can be used as a performance benchmark for any P2P file dissemination system. We also investigate the performance of a decentralized strategy, providing evidence that the performance of necessarily decentralized P2P file dissemination systems should be close to this bound and therefore that it is useful in practice.
Lexical Adaptation of Link Grammar to the Biomedical Sublanguage: a Comparative Evaluation of Three Approaches
Venue: arXiv cs.CL 2006
Year: 2006

We study the adaptation of Link Grammar Parser to the biomedical sublanguage with a focus on domain terms not found in a general parser lexicon. Using two biomedical corpora, we implement and evaluate three approaches to addressing unknown words: automatic lexicon expansion, the use of morphological clues, and disambiguation using a part-of-speech tagger. We evaluate each approach separately for its effect on parsing performance and consider combinations of these approaches. In addition to a 45% increase in parsing efficiency, we find that the best approach, incorporating information from a domain part-of-speech tagger, offers a statistically signicant 10% relative decrease in error. The adapted parser is available under an open-source license at http://www.it.utu.fi/biolg.
Comparison of Image Similarity Queries in P2P Systems
Venue: arXiv cs.DC 2006
Year: 2006

Given some of the recent advances in Distributed Hash Table (DHT) based Peer-To-Peer (P2P) systems we ask the following questions: Are there applications where unstructured queries are still necessary (i.e., the underlying queries do not efficiently map onto any structured framework), and are there unstructured P2P systems that can deliver the high bandwidth and computing performance necessary to support such applications. Toward this end, we consider an image search application which supports queries based on image similarity metrics, such as color histogram intersection, and discuss why in this setting, standard DHT approaches are not directly applicable. We then study the feasibility of implementing such an image search system on two different unstructured P2P systems: power-law topology with percolation search, and an optimized super-node topology using structured broadcasts. We examine the average and maximum values for node bandwidth, storage and processing requirements in the percolation and super-node models, and show that current high-end computers and high-speed links have sufficient resources to enable deployments of large-scale complex image search systems.
Approximately Efficient Cost-Sharing Mechanisms
Venue: arXiv cs.GT 2006
Year: 2006

We make three different types of contributions to cost-sharing: First, we identify several new classes of combinatorial cost functions that admit incentive-compatible mechanisms achieving both a constant-factor approximation of budget-balance and a polylogarithmic approximation of the social cost formulation of efficiency. Second, we prove a new, optimal lower bound on the approximate efficiency of every budget-balanced Moulin mechanism for Steiner tree or SSRoB cost functions. This lower bound exposes a latent approximation hierarchy among different cost-sharing problems. Third, we show that weakening the definition of incentive-compatibility to strategyproofness can permit exponentially more efficient approximately budget-balanced mechanisms, in particular for set cover cost-sharing problems.
3-facial colouring of plane graphs
Venue: arXiv cs.DM 2006
Year: 2006

A plane graph is l-facially k-colourable if its vertices can be coloured with k colours such that any two distinct vertices on a facial segment of length at most l are coloured differently. We prove that every plane graph is 3-facially 11-colourable. As a consequence, we derive that every 2-connected plane graph with maximum face-size at most 7 is cyclically 11-colourable. These two bounds are for one off from those that are proposed by the (3l+1)-Conjecture and the Cyclic Conjecture.
Slepian-Wolf Code Design via Source-Channel Correspondence
Venue: arXiv cs.IT 2006
Year: 2006

We consider Slepian-Wolf code design based on LDPC (low-density parity-check) coset codes for memoryless source-side information pairs. A density evolution formula, equipped with a concentration theorem, is derived for Slepian- Wolf coding based on LDPC coset codes. As a consequence, an intimate connection between Slepian-Wolf coding and channel coding is established. Specifically we show that, under density evolution, design of binary LDPC coset codes for Slepian-Wolf coding of an arbitrary memoryless source-side information pair reduces to design of binary LDPC codes for binary-input output-symmetric channels without loss of optimality. With this connection, many classic results in channel coding can be easily translated into the Slepian-Wolf setting.
Sharp threshold for hamiltonicity of random geometric graphs
Venue: arXiv cs.DM 2006
Year: 2006

We show for an arbitrary $\ell_p$ norm that the property that a random geometric graph $\mathcal G(n,r)$ contains a Hamiltonian cycle exhibits a sharp threshold at $r=r(n)=\sqrt{\frac{\log n}{α_p n}}$, where $α_p$ is the area of the unit disk in the $\ell_p$ norm. The proof is constructive and yields a linear time algorithm for finding a Hamiltonian cycle of $\RG$ a.a.s., provided $r=r(n)\ge\sqrt{\frac{\log n}{(α_p -ε)n}}$ for some fixed $ε> 0$.
Evaluation de Techniques de Traitement des Refusés pour l'Octroi de Crédit
Venue: arXiv cs.NE 2006
Year: 2006

We present the problem of "Reject Inference" for credit acceptance. Because of the current legal framework (Basel II), credit institutions need to industrialize their processes for credit acceptance, including Reject Inference. We present here a methodology to compare various techniques of Reject Inference and show that it is necessary, in the absence of real theoretical results, to be able to produce and compare models adapted to available data (selection of "best" model conditionnaly on data). We describe some simulations run on a small data set to illustrate the approach and some strategies for choosing the control group, which is the only valid approach to Reject Inference.
Raisonner avec des diagrammes : perspectives cognitives et computationnelles
Venue: arXiv cs.CL 2006
Year: 2006

Diagrammatic, analogical or iconic representations are often contrasted with linguistic or logical representations, in which the shape of the symbols is arbitrary. The aim of this paper is to make a case for the usefulness of diagrams in inferential knowledge representation systems. Although commonly used, diagrams have for a long time suffered from the reputation of being only a heuristic tool or a mere support for intuition. The first part of this paper is an historical background paying tribute to the logicians, psychologists and computer scientists who put an end to this formal prejudice against diagrams. The second part is a discussion of their characteristics as opposed to those of linguistic forms. The last part is aimed at reviving the interest for heterogeneous representation systems including both linguistic and diagrammatic representations.
Boundary cliques, clique trees and perfect sequences of maximal cliques of a chordal graph
Venue: arXiv cs.DM 2006
Year: 2006

We characterize clique trees of a chordal graph in their relation to simplicial vertices and perfect sequences of maximal cliques. We investigate boundary cliques defined by Shibata and clarify their relation to endpoints of clique trees. Next we define a symmetric binary relation between the set of clique trees and the set of perfect sequences of maximal cliques. We describe the relation as a bipartite graph and prove that the bipartite graph is always connected. Lastly we consider to characterize chordal graphs from the aspect of non-uniqueness of clique trees.
Craig's Interpolation Theorem formalised and mechanised in Isabelle/HOL
Venue: arXiv cs.LO 2006
Year: 2006

We formalise and mechanise a construtive, proof theoretic proof of Craig's Interpolation Theorem in Isabelle/HOL. We give all the definitions and lemma statements both formally and informally. We also transcribe informally the formal proofs. We detail the main features of our mechanisation, such as the formalisation of binding for first order formulae. We also give some applications of Craig's Interpolation Theorem.
Islands for SAT
Venue: arXiv cs.AI 2006
Year: 2006

In this note we introduce the notion of islands for restricting local search. We show how we can construct islands for CNF SAT problems, and how much search space can be eliminated by restricting search to the island.
Complex Lattice Reduction Algorithm for Low-Complexity MIMO Detection
Venue: arXiv cs.DS 2006
Year: 2006

Recently, lattice-reduction-aided detectors have been proposed for multiple-input multiple-output (MIMO) systems to give performance with full diversity like maximum likelihood receiver, and yet with complexity similar to linear receivers. However, these lattice-reduction-aided detectors are based on the traditional LLL reduction algorithm that was originally introduced for reducing real lattice bases, in spite of the fact that the channel matrices are inherently complex-valued. In this paper, we introduce the complex LLL algorithm for direct application to reduce the basis of a complex lattice which is naturally defined by a complex-valued channel matrix. We prove that complex LLL reduction-aided detection can also achieve full diversity. Our analysis reveals that the new complex LLL algorithm can achieve a reduction in complexity of nearly 50% over the traditional LLL algorithm, and this is confirmed by simulation. It is noteworthy that the complex LLL algorithm aforementioned has nearly the same bit-error-rate performance as the traditional LLL algorithm.
Système de représentation d'aide au besoin dans le domaine architectural
Venue: arXiv cs.OH 2006
Year: 2006

The image is a very important mean of communication in the field of architectural who intervenes in the various phases of the design of a project. It can be regarded as a tool of decision-making aid. The study of our research aims at to see the contribution of the Economic Intelligence in the resolution of a decisional problem of the various partners (Architect, Contractor, Customer) in the architectural field, in order to make strategic decisions within the framework of the realization or design of an architectural work. The economic Intelligence allows the taking into account of the real needs for the user-decision makers, so that their waiting are considered at the first stage of a search for information and not in the final stage of the development of the tool in the evaluation of this last.
Well quasi-orders and the shuffle closure of finite sets
Venue: arXiv cs.DM 2006
Year: 2006

Given a set I of word, the set of all words obtained by the shuffle of (copies of) words of I is naturally provided with a partial order. In [FS05], the authors have opened the problem of the characterization of the finite sets I such that the order is a well quasi-order . In this paper we give an answer in the case when I consists of a single word w.
Upright-Quad Drawing of st-Planar Learning Spaces
Venue: arXiv cs.CG 2006
Year: 2006

We consider graph drawing algorithms for learning spaces, a type of st-oriented partial cube derived from antimatroids and used to model states of knowledge of students. We show how to draw any st-planar learning space so all internal faces are convex quadrilaterals with the bottom side horizontal and the left side vertical, with one minimal and one maximal vertex. Conversely, every such drawing represents an st-planar learning space. We also describe connections between these graphs and arrangements of translates of a quadrant.
Complexity and Applications of Edge-Induced Vertex-Cuts
Venue: arXiv cs.DM 2006
Year: 2006

Motivated by hypergraph decomposition algorithms, we introduce the notion of edge-induced vertex-cuts and compare it with the well-known notions of edge-cuts and vertex-cuts. We investigate the complexity of computing minimum edge-induced vertex-cuts and demonstrate the usefulness of our notion by applications in network reliability and constraint satisfaction.
Towards Implementing an Enterprise Groupware-Integrated Human Resources Information System
Venue: arXiv cs.SE 2006
Year: 2006

Human resources management software is having a wide audience at present. However, no truly integrate solution has been proposed yet to improve the systems concerned. Approaches to extra data collection for appraisal decision-making are considered on the concept modeling theoretical basis. Current technologies in state-of-the-art HR management software are compared. Design and implementation aspects for a Web-wired truly integrated secure and scalable event-driven enterprise system are described. Benchmark results are presented. Field perspectives are discussed.
Competing with Markov prediction strategies
Venue: arXiv cs.LG 2006
Year: 2006

Assuming that the loss function is convex in the prediction, we construct a prediction strategy universal for the class of Markov prediction strategies, not necessarily continuous. Allowing randomization, we remove the requirement of convexity.
Parallel repetition: simplifications and the no-signaling case
Venue: arXiv cs.CC 2006
Year: 2006

Consider a game where a refereed a referee chooses (x,y) according to a publicly known distribution P_XY, sends x to Alice, and y to Bob. Without communicating with each other, Alice responds with a value "a" and Bob responds with a value "b". Alice and Bob jointly win if a publicly known predicate Q(x,y,a,b) holds. Let such a game be given and assume that the maximum probability that Alice and Bob can win is v<1. Raz (SIAM J. Comput. 27, 1998) shows that if the game is repeated n times in parallel, then the probability that Alice and Bob win all games simultaneously is at most v'^(n/log(s)), where s is the maximal number of possible responses from Alice and Bob in the initial game, and v' is a constant depending only on v. In this work, we simplify Raz's proof in various ways and thus shorten it significantly. Further we study the case where Alice and Bob are not restricted to local computations and can use any strategy which does not imply communication among them.
Pull-Based Data Broadcast with Dependencies: Be Fair to Users, not to Items
Venue: arXiv cs.DS 2006
Year: 2006

Broadcasting is known to be an efficient means of disseminating data in wireless communication environments (such as Satellite, mobile phone networks,...). It has been recently observed that the average service time of broadcast systems can be considerably improved by taking into consideration existing correlations between requests. We study a pull-based data broadcast system where users request possibly overlapping sets of items; a request is served when all its requested items are downloaded. We aim at minimizing the average user perceived latency, i.e. the average flow time of the requests. We first show that any algorithm that ignores the dependencies can yield arbitrary bad performances with respect to the optimum even if it is given arbitrary extra resources. We then design a $(4+ε)$-speed $O(1+1/ε^2)$-competitive algorithm for this setting that consists in 1) splitting evenly the bandwidth among each requested set and in 2) broadcasting arbitrarily the items still missing in each set into the bandwidth the set has received. Our algorithm presents several interesting features: it is simple to implement, non-clairvoyant, fair to users so that no user may starve for a long period of time, and guarantees good performances in presence of correlations between user requests (without any change in the broadcast protocol). We also present a $ (4+ε)$-speed $O(1+1/ε^3)$-competitive algorithm which broadcasts at most one item at any given time and preempts each item broadcast at most once on average. As a side result of our analysis, we design a competitive algorithm for a particular setting of non-clairvoyant job scheduling with dependencies, which might be of independent interest.
The Shannon capacity of a graph and the independence numbers of its powers
Venue: arXiv cs.IT 2006
Year: 2006

The independence numbers of powers of graphs have been long studied, under several definitions of graph products, and in particular, under the strong graph product. We show that the series of independence numbers in strong powers of a fixed graph can exhibit a complex structure, implying that the Shannon Capacity of a graph cannot be approximated (up to a sub-polynomial factor of the number of vertices) by any arbitrarily large, yet fixed, prefix of the series. This is true even if this prefix shows a significant increase of the independence number at a given power, after which it stabilizes for a while.
Optimal resource allocation for OFDM multiuser channels
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, a unifying framework for orthogonal frequency division multiplexing (OFDM) multiuser resource allocation is presented. The isolated seeming problems of maximizing a weighted sum of rates for a given power budget $\bar{P}$ and minimizing sum power for given rate requirements $\mathbf{\bar{R}}$ can be interpreted jointly in this framework. To this end we embed the problems in a higher dimensional space. Based on these results, we subsequently consider the combined problem of maximizing a weighted sum of rates under given rate requirements $\mathbf{\bar{R}}$ and a fixed power budget $\bar{P}$. This new problem is challenging, since the additional constraints do not allow to use the hitherto existing approaches. Interestingly, the optimal decoding orders turn out to be the ordering of the Lagrangian factors in all problems.
myADS-arXiv - a Tailor-Made, Open Access, Virtual Journal
Venue: arXiv cs.DL 2006
Year: 2006

The myADS-arXiv service provides the scientific community with a one stop shop for staying up-to-date with a researcher's field of interest. The service provides a powerful and unique filter on the enormous amount of bibliographic information added to the ADS on a daily basis. It also provides a complete view with the most relevant papers available in the subscriber's field of interest. With this service, the subscriber will get to know the lastest developments, popular trends and the most important papers. This makes the service not only unique from a technical point of view, but also from a content point of view. On this poster we will argue why myADS-arXiv is a tailor-made, open access, virtual journal and we will illustrate its unique character.
Using Sets of Probability Measures to Represent Uncertainty
Venue: arXiv cs.AI 2006
Year: 2006

I explore the use of sets of probability measures as a representation of uncertainty.