OpenRaiser/Intern-Atlas huggingface dataset:
PALS: Efficient Or-Parallelism on Beowulf Clusters
Venue: arXiv cs.DC 2006
Year: 2006

This paper describes the development of the PALS system, an implementation of Prolog capable of efficiently exploiting or-parallelism on distributed-memory platforms--specifically Beowulf clusters. PALS makes use of a novel technique, called incremental stack-splitting. The technique proposed builds on the stack-splitting approach, previously described by the authors and experimentally validated on shared-memory systems, which in turn is an evolution of the stack-copying method used in a variety of parallel logic and constraint systems--e.g., MUSE, YAP, and Penny. The PALS system is the first distributed or-parallel implementation of Prolog based on the stack-splitting method ever realized. The results presented confirm the superiority of this method as a simple yet effective technique to transition from shared-memory to distributed-memory systems. PALS extends stack-splitting by combining it with incremental copying; the paper provides a description of the implementation of PALS, including details of how distributed scheduling is handled. We also investigate methodologies to effectively support order-sensitive predicates (e.g., side-effects) in the context of the stack-splitting scheme. Experimental results obtained from running PALS on both Shared Memory and Beowulf systems are presented and analyzed.
PAC Classification based on PAC Estimates of Label Class Distributions
Venue: arXiv cs.LG 2006
Year: 2006

A standard approach in pattern classification is to estimate the distributions of the label classes, and then to apply the Bayes classifier to the estimates of the distributions in order to classify unlabeled examples. As one might expect, the better our estimates of the label class distributions, the better the resulting classifier will be. In this paper we make this observation precise by identifying risk bounds of a classifier in terms of the quality of the estimates of the label class distributions. We show how PAC learnability relates to estimates of the distributions that have a PAC guarantee on their $L_1$ distance from the true distribution, and we bound the increase in negative log likelihood risk in terms of PAC bounds on the KL-divergence. We give an inefficient but general-purpose smoothing method for converting an estimated distribution that is good under the $L_1$ metric into a distribution that is good under the KL-divergence.
Dealing with Metonymic Readings of Named Entities
Venue: arXiv cs.AI 2006
Year: 2006

The aim of this paper is to propose a method for tagging named entities (NE), using natural language processing techniques. Beyond their literal meaning, named entities are frequently subject to metonymy. We show the limits of current NE type hierarchies and detail a new proposal aiming at dynamically capturing the semantics of entities in context. This model can analyze complex linguistic phenomena like metonymy, which are known to be difficult for natural language processing but crucial for most applications. We present an implementation and some test using the French ESTER corpus and give significant results.
Elementary Proof of a Theorem of Jean Ville
Venue: arXiv cs.CC 2006
Year: 2006

Considerable thought has been devoted to an adequate definition of the class of infinite, random binary sequences (the sort of sequence that almost certainly arises from flipping a fair coin indefinitely). The first mathematical exploration of this problem was due to R. Von Mises, and based on his concept of a "selection function." A decisive objection to Von Mises' idea was formulated in a theorem offered by Jean Ville in 1939. It shows that some sequences admitted by Von Mises as "random" in fact manifest a certain kind of systematicity. Ville's proof is challenging, and an alternative approach has appeared only in condensed form. We attempt to provide an expanded version of the latter, alternative argument.
Computation of the Weight Distribution of CRC Codes
Venue: arXiv cs.IT 2006
Year: 2006

In this article, we illustrate an algorithm for the computation of the weight distribution of CRC codes. The recursive structure of CRC codes will give us an iterative way to compute the weight distribution of their dual codes starting from just some ``representative'' words. Thanks to MacWilliams Theorem, the computation of the weight distribution of dual codes can be easily brought back to that of CRC codes. This algorithm is a good alternative to the standard algorithm that involves listing every word of the code.
Capacity of Cooperative Fusion in the Presence of Byzantine Sensors
Venue: arXiv cs.IT 2006
Year: 2006

The problem of cooperative fusion in the presence of Byzantine sensors is considered. An information theoretic formulation is used to characterize the Shannon capacity of sensor fusion. It is shown that when less than half of the sensors are Byzantine, the effect of Byzantine attack can be entirely mitigated, and the fusion capacity is identical to that when all sensors are honest. But when at least half of the sensors are Byzantine, they can completely defeat the sensor fusion so that no information can be transmitted reliably. A capacity achieving transmit-then-verify strategy is proposed for the case that less than half of the sensors are Byzantine, and its error probability and coding rate is analyzed by using a Markov decision process modeling of the transmission protocol.
Representing Knowledge about Norms
Venue: arXiv cs.AI 2006
Year: 2006

Norms are essential to extend inference: inferences based on norms are far richer than those based on logical implications. In the recent decades, much effort has been devoted to reason on a domain, once its norms are represented. How to extract and express those norms has received far less attention. Extraction is difficult: as the readers are supposed to know them, the norms of a domain are seldom made explicit. For one thing, extracting norms requires a language to represent them, and this is the topic of this paper. We apply this language to represent norms in the domain of driving, and show that it is adequate to reason on the causes of accidents, as described by car-crash reports.
Un filtre temporel crédibiliste pour la reconnaissance d'actions humaines dans les vidéos
Venue: arXiv cs.MM 2006
Year: 2006

In the context of human action recognition in video sequences, a temporal belief filter is presented. It allows to cope with human action disparity and low quality videos. The whole system of action recognition is based on the Transferable Belief Model (TBM) proposed by P. Smets. The TBM allows to explicitly model the doubt between actions. Furthermore, the TBM emphasizes the conflict which is exploited for action recognition. The filtering performance is assessed on real video sequences acquired by a moving camera and under several unknown view angles.
Using Answer Set Programming in an Inference-Based approach to Natural Language Semantics
Venue: arXiv cs.CL 2006
Year: 2006

Using Answer Set Programming in an Inference-Based approach to Natural Language Semantics
Superregular Matrices and the Construction of Convolutional Codes having a Maximum Distance Profile
Venue: arXiv cs.IT 2006
Year: 2006

Superregular matrices are a class of lower triangular Toeplitz matrices that arise in the context of constructing convolutional codes having a maximum distance profile. These matrices are characterized by the property that no submatrix has a zero determinant unless it is trivially zero due to the lower triangular structure. In this paper, we discuss how superregular matrices may be used to construct codes having a maximum distance profile. We also introduce group actions that preserve the superregularity property and present an upper bound on the minimum size a finite field must have in order that a superregular matrix of a given size can exist over that field.
Logical settings for concept learning from incomplete examples in First Order Logic
Venue: arXiv cs.LG 2006
Year: 2006

We investigate here concept learning from incomplete examples. Our first purpose is to discuss to what extent logical learning settings have to be modified in order to cope with data incompleteness. More precisely we are interested in extending the learning from interpretations setting introduced by L. De Raedt that extends to relational representations the classical propositional (or attribute-value) concept learning from examples framework. We are inspired here by ideas presented by H. Hirsh in a work extending the Version space inductive paradigm to incomplete data. H. Hirsh proposes to slightly modify the notion of solution when dealing with incomplete examples: a solution has to be a hypothesis compatible with all pieces of information concerning the examples. We identify two main classes of incompleteness. First, uncertainty deals with our state of knowledge concerning an example. Second, generalization (or abstraction) deals with what part of the description of the example is sufficient for the learning purpose. These two main sources of incompleteness can be mixed up when only part of the useful information is known. We discuss a general learning setting, referred to as "learning from possibilities" that formalizes these ideas, then we present a more specific learning setting, referred to as "assumption-based learning" that cope with examples which uncertainty can be reduced when considering contextual information outside of the proper description of the examples. Assumption-based learning is illustrated on a recent work concerning the prediction of a consensus secondary structure common to a set of RNA sequences.
Linear Predictive Coding as an Estimator of Volatility
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, we present a method of estimating the volatility of a signal that displays stochastic noise (such as a risky asset traded on an open market) utilizing Linear Predictive Coding. The main purpose is to associate volatility with a series of statistical properties that can lead us, through further investigation, toward a better understanding of structural volatility as well as to improve the quality of our current estimates.
Improving convergence of Belief Propagation decoding
Venue: arXiv cs.IT 2006
Year: 2006

The decoding of Low-Density Parity-Check codes by the Belief Propagation (BP) algorithm is revisited. We check the iterative algorithm for its convergence to a codeword (termination), we run Monte Carlo simulations to find the probability distribution function of the termination time, n_it. Tested on an example [155, 64, 20] code, this termination curve shows a maximum and an extended algebraic tail at the highest values of n_it. Aiming to reduce the tail of the termination curve we consider a family of iterative algorithms modifying the standard BP by means of a simple relaxation. The relaxation parameter controls the convergence of the modified BP algorithm to a minimum of the Bethe free energy. The improvement is experimentally demonstrated for Additive-White-Gaussian-Noise channel in some range of the signal-to-noise ratios. We also discuss the trade-off between the relaxation parameter of the improved iterative scheme and the number of iterations.
Trees with Convex Faces and Optimal Angles
Venue: arXiv cs.CG 2006
Year: 2006

We consider drawings of trees in which all edges incident to leaves can be extended to infinite rays without crossing, partitioning the plane into infinite convex polygons. Among all such drawings we seek the one maximizing the angular resolution of the drawing. We find linear time algorithms for solving this problem, both for plane trees and for trees without a fixed embedding. In any such drawing, the edge lengths may be set independently of the angles, without crossing; we describe multiple strategies for setting these lengths.
Revising Type-2 Computation and Degrees of Discontinuity
Venue: arXiv cs.LO 2006
Year: 2006

By the sometimes so-called MAIN THEOREM of Recursive Analysis, every computable real function is necessarily continuous. Weihrauch and Zheng (TCS'2000), Brattka (MLQ'2005), and Ziegler (ToCS'2006) have considered different relaxed notions of computability to cover also discontinuous functions. The present work compares and unifies these approaches. This is based on the concept of the JUMP of a representation: both a TTE-counterpart to the well known recursion-theoretic jump on Kleene's Arithmetical Hierarchy of hypercomputation: and a formalization of revising computation in the sense of Shoenfield. We also consider Markov and Banach/Mazur oracle-computation of discontinuous fu nctions and characterize the computational power of Type-2 nondeterminism to coincide with the first level of the Analytical Hierarchy.
Expressing Implicit Semantic Relations without Supervision
Venue: arXiv cs.CL 2006
Year: 2006

We present an unsupervised learning algorithm that mines large text corpora for patterns that express implicit semantic relations. For a given input word pair X:Y with some unspecified semantic relations, the corresponding output list of patterns <P1,...,Pm> is ranked according to how well each pattern Pi expresses the relations between X and Y. For example, given X=ostrich and Y=bird, the two highest ranking output patterns are "X is the largest Y" and "Y such as the X". The output patterns are intended to be useful for finding further pairs with the same relations, to support the construction of lexicons, ontologies, and semantic networks. The patterns are sorted by pertinence, where the pertinence of a pattern Pi for a word pair X:Y is the expected relational similarity between the given pair and typical pairs for Pi. The algorithm is empirically evaluated on two tasks, solving multiple-choice SAT word analogy questions and classifying semantic relations in noun-modifier pairs. On both tasks, the algorithm achieves state-of-the-art results, performing significantly better than several alternative pattern ranking algorithms, based on tf-idf.
Enterprise Portal Development Tools: Problem-Oriented Approach
Venue: arXiv cs.SE 2006
Year: 2006

The paper deals with problem-oriented visual information system (IS) engineering for enterprise Internet-based applications, which is a vital part of the whole development process. The suggested approach is based on semantic network theory and a novel ConceptModeller CASE tool.
ConceptModeller: a Problem-Oriented Visual SDK for Globally Distributed Enterprise Systems
Venue: arXiv cs.SE 2006
Year: 2006

The paper describes problem-oriented approach to software development. The approach is a part of the original integrated methodology of enterprise Internet-based software design and implementation. All aspects of software development, from theory to implementation, are covered.
Enterprise Portal: from Model to Implementation
Venue: arXiv cs.SE 2006
Year: 2006

Portal technology can significantly improve the entire corporate information infrastructure. The approach proposed is based on rigorous and consistent (meta)data model and provides for efficient and accurate front-end integration of heterogeneous corporate applications including enterprise resource planning (ERP) systems, multimedia data warehouses and proprietary content databases. The methodology proposed embraces entire software lifecycle; it is illustrated by an enterprise-level Intranet portal implementation.
On q-ary codes correcting all unidirectional errors of a limited magnitude
Venue: arXiv cs.IT 2006
Year: 2006

We consider codes over the alphabet Q={0,1,..,q-1}intended for the control of unidirectional errors of level l. That is, the transmission channel is such that the received word cannot contain both a component larger than the transmitted one and a component smaller than the transmitted one. Moreover, the absolute value of the difference between a transmitted component and its received version is at most l. We introduce and study q-ary codes capable of correcting all unidirectional errors of level l. Lower and upper bounds for the maximal size of those codes are presented. We also study codes for this aim that are defined by a single equation on the codeword coordinates(similar to the Varshamov-Tenengolts codes for correcting binary asymmetric errors). We finally consider the problem of detecting all unidirectional errors of level l.
Self-Replication and Self-Assembly for Manufacturing
Venue: arXiv cs.MA 2006
Year: 2006

It has been argued that a central objective of nanotechnology is to make products inexpensively, and that self-replication is an effective approach to very low-cost manufacturing. The research presented here is intended to be a step towards this vision. We describe a computational simulation of nanoscale machines floating in a virtual liquid. The machines can bond together to form strands (chains) that self-replicate and self-assemble into user-specified meshes. There are four types of machines and the sequence of machine types in a strand determines the shape of the mesh they will build. A strand may be in an unfolded state, in which the bonds are straight, or in a folded state, in which the bond angles depend on the types of machines. By choosing the sequence of machine types in a strand, the user can specify a variety of polygonal shapes. A simulation typically begins with an initial unfolded seed strand in a soup of unbonded machines. The seed strand replicates by bonding with free machines in the soup. The child strands fold into the encoded polygonal shape, and then the polygons drift together and bond to form a mesh. We demonstrate that a variety of polygonal meshes can be manufactured in the simulation, by simply changing the sequence of machine types in the seed.
Multicasting with selective delivery: A SafetyNet for vertical handoffs
Venue: arXiv cs.NI 2006
Year: 2006

In future mobility support will require handling roaming in heterogeneous access networks. In order to enable seamless roaming it is necessary to minimize the impact of the vertical handoffs. Localized mobility management schemes such as FMIPv6 and HMIPv6 do not provide sufficient handoff performance, since they have been designed for horizontal handoffs. In this paper, we propose the SafetyNet protocol, which allows a Mobile Node to perform seamless vertical handoffs. Further, we propose a handoff timing algorithm which allows a Mobile Node to delay or even completely avoid upward vertical handoffs. We implement the SafetyNet protocol and compare its performance with the Fast Handovers for Mobile IPv6 protocol in our wireless test bed and analyze the results. The experimental results indicate that the proposed SafetyNet protocol can provide an improvement of up to 95% for TCP performance in vertical handoffs, when compared with FMIPv6 and an improvement of 64% over FMIPv6 with bicasting. We use numerical analysis of the protocol to show that its signaling and data transmission overhead is comparable to Fast Mobile IPv6 and significantly smaller than that of FMIPv6 with bicasting.
Stylized Facts in Internal Rates of Return on Stock Index and its Derivative Transactions
Venue: arXiv cs.IT 2006
Year: 2006

Universal features in stock markets and their derivative markets are studied by means of probability distributions in internal rates of return on buy and sell transaction pairs. Unlike the stylized facts in log normalized returns, the probability distributions for such single asset encounters encorporate the time factor by means of the internal rate of return defined as the continuous compound interest. Resulting stylized facts are shown in the probability distributions derived from the daily series of TOPIX, S & P 500 and FTSE 100 index close values. The application of the above analysis to minute-tick data of NIKKEI 225 and its futures market, respectively, reveals an interesting diffference in the behavior of the two probability distributions, in case a threshold on the minimal duration of the long position is imposed. It is therefore suggested that the probability distributions of the internal rates of return could be used for causality mining between the underlying and derivative stock markets. The highly specific discrete spectrum, which results from noise trader strategies as opposed to the smooth distributions observed for fundamentalist strategies in single encounter transactions may be also useful in deducing the type of investment strategy from trading revenues of small portfolio investors.
Employing Trusted Computing for the forward pricing of pseudonyms in reputation systems
Venue: arXiv cs.CR 2006
Year: 2006

Reputation and recommendation systems are fundamental for the formation of community market places. Yet, they are easy targets for attacks which disturb a market's equilibrium and are often based on cheap pseudonyms used to submit ratings. We present a method to price ratings using trusted computing, based on pseudonymous tickets.
A Finite Equational Base for CCS with Left Merge and Communication Merge
Venue: arXiv cs.LO 2006
Year: 2006

Using the left merge and communication merge from ACP, we present an equational base (i.e., a ground-complete and $ω$-complete set of valid equations) for the fragment of CCS without recursion, restriction and relabelling. Our equational base is finite if the set of actions is finite.
On a solution to display non-filled-in quaternionic Julia sets
Venue: arXiv cs.GR 2006
Year: 2006

During early 1980s, the so-called `escape time' method, developed to display the Julia sets for complex dynamical systems, was exported to quaternions in order to draw analogous pictures in this wider numerical field. Despite of the fine results in the complex plane, where all topological configurations of Julia sets have been successfully displayed, the `escape time' method fails to render properly the non-filled-in variety of quaternionic Julia sets. So their digital visualisation remained an open problem for several years. Both the solution for extending this old method to non-filled-in quaternionic Julia sets and its implementation into a program are explained here.
Separating the articles of authors with the same name
Venue: arXiv cs.DL 2006
Year: 2006

I describe a method to separate the articles of different authors with the same name. It is based on a distance between any two publications, defined in terms of the probability that they would have as many coincidences if they were drawn at random from all published documents. Articles with a given author name are then clustered according to their distance, so that all articles in a cluster belong very likely to the same author. The method has proven very useful in generating groups of papers that are then selected manually. This simplifies considerably citation analysis when the author publication lists are not available.
A Graph-based Framework for Transmission of Correlated Sources over Broadcast Channels
Venue: arXiv cs.IT 2006
Year: 2006

In this paper we consider the communication problem that involves transmission of correlated sources over broadcast channels. We consider a graph-based framework for this information transmission problem. The system involves a source coding module and a channel coding module. In the source coding module, the sources are efficiently mapped into a nearly semi-regular bipartite graph, and in the channel coding module, the edges of this graph are reliably transmitted over a broadcast channel. We consider nearly semi-regular bipartite graphs as discrete interface between source coding and channel coding in this multiterminal setting. We provide an information-theoretic characterization of (1) the rate of exponential growth (as a function of the number of channel uses) of the size of the bipartite graphs whose edges can be reliably transmitted over a broadcast channel and (2) the rate of exponential growth (as a function of the number of source samples) of the size of the bipartite graphs which can reliably represent a pair of correlated sources to be transmitted over a broadcast channel.