OpenRaiser/Intern-Atlas huggingface dataset:
Issues in Communication Game
Venue: arXiv cs.CL 2003
Year: 2003

As interaction between autonomous agents, communication can be analyzed in game-theoretic terms. Meaning game is proposed to formalize the core of intended communication in which the sender sends a message and the receiver attempts to infer its meaning intended by the sender. Basic issues involved in the game of natural language communication are discussed, such as salience, grammaticality, common sense, and common belief, together with some demonstration of the feasibility of game-theoretic account of language.
Small-World File-Sharing Communities
Venue: arXiv cs.DC 2003
Year: 2003

Web caches, content distribution networks, peer-to-peer file sharing networks, distributed file systems, and data grids all have in common that they involve a community of users who generate requests for shared data. In each case, overall system performance can be improved significantly if we can first identify and then exploit interesting structure within a community's access patterns. To this end, we propose a novel perspective on file sharing based on the study of the relationships that form among users based on the files in which they are interested. We propose a new structure that captures common user interests in data--the data-sharing graph-- and justify its utility with studies on three data-distribution systems: a high-energy physics collaboration, the Web, and the Kazaa peer-to-peer network. We find small-world patterns in the data-sharing graphs of all three communities. We analyze these graphs and propose some probable causes for these emergent small-world patterns. The significance of small-world patterns is twofold: it provides a rigorous support to intuition and, perhaps most importantly, it suggests ways to design mechanisms that exploit these naturally emerging patterns.
A ternary Relation Algebra of directed lines
Venue: arXiv cs.AI 2003
Year: 2003

We define a ternary Relation Algebra (RA) of relative position relations on two-dimensional directed lines (d-lines for short). A d-line has two degrees of freedom (DFs): a rotational DF (RDF), and a translational DF (TDF). The representation of the RDF of a d-line will be handled by an RA of 2D orientations, CYC_t, known in the literature. A second algebra, TA_t, which will handle the TDF of a d-line, will be defined. The two algebras, CYC_t and TA_t, will constitute, respectively, the translational and the rotational components of the RA, PA_t, of relative position relations on d-lines: the PA_t atoms will consist of those pairs <t,r> of a TA_t atom and a CYC_t atom that are compatible. We present in detail the RA PA_t, with its converse table, its rotation table and its composition tables. We show that a (polynomial) constraint propagation algorithm, known in the literature, is complete for a subset of PA_t relations including almost all of the atomic relations. We will discuss the application scope of the RA, which includes incidence geometry, GIS (Geographic Information Systems), shape representation, localisation in (multi-)robot navigation, and the representation of motion prepositions in NLP (Natural Language Processing). We then compare the RA to existing ones, such as an algebra for reasoning about rectangles parallel to the axes of an (orthogonal) coordinate system, a ``spatial Odyssey'' of Allen's interval algebra, and an algebra for reasoning about 2D segments.
Contributions to the Development and Improvement of a Regulatory and Pre-Regulatory Digitally System for the Tools within Flexible Fabrication Systems
Venue: arXiv cs.CE 2003
Year: 2003

The paper reports the obtained results for the projection and realization of a digitally system aiming to assist the equipment for a regulatory and pre-regulatory tools and holding tools within the flexible fabrication systems (FFS). Moreover, based on the present results, the same methodology can be applied for assisting tools from the point of view of their integrity and to wear compensation in the FFS framework.
Learning Analogies and Semantic Relations
Venue: arXiv cs.LG 2003
Year: 2003

We present an algorithm for learning from unlabeled text, based on the Vector Space Model (VSM) of information retrieval, that can solve verbal analogy questions of the kind found in the Scholastic Aptitude Test (SAT). A verbal analogy has the form A:B::C:D, meaning "A is to B as C is to D"; for example, mason:stone::carpenter:wood. SAT analogy questions provide a word pair, A:B, and the problem is to select the most analogous word pair, C:D, from a set of five choices. The VSM algorithm correctly answers 47% of a collection of 374 college-level analogy questions (random guessing would yield 20% correct). We motivate this research by relating it to work in cognitive science and linguistics, and by applying it to a difficult problem in natural language processing, determining semantic relations in noun-modifier pairs. The problem is to classify a noun-modifier pair, such as "laser printer", according to the semantic relation between the noun (printer) and the modifier (laser). We use a supervised nearest-neighbour algorithm that assigns a class to a given noun-modifier pair by finding the most analogous noun-modifier pair in the training data. With 30 classes of semantic relations, on a collection of 600 labeled noun-modifier pairs, the learning algorithm attains an F value of 26.5% (random guessing: 3.3%). With 5 classes of semantic relations, the F value is 43.2% (random: 20%). The performance is state-of-the-art for these challenging problems.
Augernome & XtremWeb: Monte Carlos computation on a global computing platform
Venue: arXiv cs.DC 2003
Year: 2003

In this paper, we present XtremWeb, a Global Computing platform used to generate monte carlos showers in Auger, an HEP experiment to study the highest energy cosmic rays at Mallargue-Mendoza, Argentina. XtremWeb main goal, as a Global Computing platform, is to compute distributed applications using idle time of widely interconnected machines. It is especially dedicated to -but not limited to- multi-parameters applications such as monte carlos computations; its security mechanisms ensuring not only hosts integrity but also results certification and its fault tolerant features, encouraged us to test it and, finally, to deploy it as to support our CPU needs to simulate showers. We first introduce Auger computing needs and how Global Computing could help. We then detail XtremWeb architecture and goals. The fourth and last part presents the profits we have gained to choose this platform. We conclude on what could be done next.
Modeling Belief in Dynamic Systems, Part II: Revisions and Update
Venue: arXiv cs.AI 2003
Year: 2003

The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. In a companion paper, we introduce a new framework to model belief change. This framework combines temporal and epistemic modalities with a notion of plausibility, allowing us to examine the change of beliefs over time. In this paper, we show how belief revision and belief update can be captured in our framework. This allows us to compare the assumptions made by each method, and to better understand the principles underlying them. In particular, it shows that Katsuno and Mendelzon's notion of belief update depends on several strong assumptions that may limit its applicability in artificial intelligence. Finally, our analysis allow us to identify a notion of minimal change that underlies a broad range of belief change operations including revision and update.
Short Cycles Connectivity
Venue: arXiv cs.DS 2003
Year: 2003

Short cycles connectivity is a generalization of ordinary connectivity. Instead by a path (sequence of edges), two vertices have to be connected by a sequence of short cycles, in which two adjacent cycles have at least one common vertex. If all adjacent cycles in the sequence share at least one edge, we talk about edge short cycles connectivity. It is shown that the short cycles connectivity is an equivalence relation on the set of vertices, while the edge short cycles connectivity components determine an equivalence relation on the set of edges. Efficient algorithms for determining equivalence classes are presented. Short cycles connectivity can be extended to directed graphs (cyclic and transitive connectivity). For further generalization we can also consider connectivity by small cliques or other families of graphs.
Collaborative Creation of Digital Content in Indian Languages
Venue: arXiv cs.CL 2003
Year: 2003

The world is passing through a major revolution called the information revolution, in which information and knowledge is becoming available to people in unprecedented amounts wherever and whenever they need it. Those societies which fail to take advantage of the new technology will be left behind, just like in the industrial revolution. The information revolution is based on two major technologies: computers and communication. These technologies have to be delivered in a COST EFFECTIVE manner, and in LANGUAGES accessible to people. One way to deliver them in cost effective manner is to make suitable technology choices, and to allow people to access through shared resources. This could be done throuch street corner shops (for computer usage, e-mail etc.), schools, community centres and local library centres.
On Decidability of Expressive Description Logics with Composition of Roles in Number Restrictions
Venue: arXiv cs.LO 2003
Year: 2003

Description Logics are knowledge representation formalisms which have been used in a wide range of application domains. Owing to their appealing expressiveness, we consider in this paper extensions of the well-known concept language ALC allowing for number restrictions on complex role expressions. These have been first introduced by Baader and Sattler as ALCN(M) languages, with the adoption of role constructors M subset-of {o,-,And,Or}. In particular, they showed in 1999 that, although ALCN(o) is decidable, the addition of other operators may easily lead to undecidability: in fact, ALCN(o,And) and ALCN(o,-,Or) were proved undecidable. In this work, we further investigate the computational properties of the ALCN family, aiming at narrowing the decidability gap left open by Baader and Sattler's results. In particular, we will show that ALCN(o) extended with inverse roles both in number and in value restrictions becomes undecidable, whereas it can be safely extended with qualified number restrictions without losing decidability.
Distributed and Parallel Net Imaging
Venue: arXiv cs.CV 2003
Year: 2003

A very complex vision system is developed to detect luminosity variations connected with the discovery of new planets in the Universe. The traditional imaging system can not manage a so large load. A private net is implemented to perform an automatic vision and decision architecture. It lets to carry out an on-line discrimination of interesting events by using two levels of triggers. This system can even manage many Tbytes of data per day. The architecture avails itself of a distributed parallel network system based on a maximum of 256 standard workstations with Microsoft Window as OS.
Static Data Structure for Discrete Advance Bandwidth Reservations on the Internet
Venue: arXiv cs.DS 2003
Year: 2003

In this paper we present a discrete data structure for reservations of limited resources. A reservation is defined as a tuple consisting of the time interval of when the resource should be reserved, $I_R$, and the amount of the resource that is reserved, $B_R$, formally $R=\{I_R,B_R\}$. The data structure is similar to a segment tree. The maximum spanning interval of the data structure is fixed and defined in advance. The granularity and thereby the size of the intervals of the leaves is also defined in advance. The data structure is built only once. Neither nodes nor leaves are ever inserted, deleted or moved. Hence, the running time of the operations does not depend on the number of reservations previously made. The running time does not depend on the size of the interval of the reservation either. Let $n$ be the number of leaves in the data structure. In the worst case, the number of touched (i.e. traversed) nodes is in any operation $O(\log n)$, hence the running time of any operation is also $O(\log n)$.
EqRank: A Self-Consistent Equivalence Relation on Graph Vertexes
Venue: arXiv cs.DS 2003
Year: 2003

A new method of hierarchical clustering of graph vertexes is suggested. In the method, the graph partition is determined with an equivalence relation satisfying a recursive definition stating that vertexes are equivalent if the vertexes they point to (or vertexes pointing to them) are equivalent. Iterative application of the partitioning yields a hierarchical clustering of graph vertexes. The method is applied to the citation graph of hep-th. The outcome is a two-level classification scheme for the subject field presented in hep-th, and indexing of the papers from hep-th in this scheme. A number of tests show that the classification obtained is adequate.
Using Simulated Annealing to Calculate the Trembles of Trembling Hand Perfection
Venue: arXiv cs.GT 2003
Year: 2003

Within the literature on non-cooperative game theory, there have been a number of attempts to propose logorithms which will compute Nash equilibria. Rather than derive a new algorithm, this paper shows that the family of algorithms known as Markov chain Monte Carlo (MCMC) can be used to calculate Nash equilibria. MCMC is a type of Monte Carlo simulation that relies on Markov chains to ensure its regularity conditions. MCMC has been widely used throughout the statistics and optimization literature, where variants of this algorithm are known as simulated annealing. This paper shows that there is interesting connection between the trembles that underlie the functioning of this algorithm and the type of Nash refinement known as trembling hand perfection.
Enumerating planar locally finite Cayley graphs
Venue: arXiv cs.DM 2003
Year: 2003

We characterize the set of planar locally finite Cayley graphs, and give a finite representation of these graphs by a special kind of finite state automata called labeling schemes. As a result, we are able to enumerate and describe all planar locally finite Cayley graphs of a given degree. This analysis allows us to solve the problem of decision of the locally finite planarity for a word-problem-decidable presentation. Keywords: vertex-transitive, Cayley graph, planar graph, tiling, labeling scheme
Timestamp Based Execution Control for C and Java Programs
Venue: arXiv cs.SE 2003
Year: 2003

Many programmers have had to deal with an overwritten variable resulting for example from an aliasing problem. The culprit is obviously the last write-access to that memory location before the manifestation of the bug. The usual technique for removing such bugs starts with the debugger by (1) finding the last write and (2) moving the control point of execution back to that time by re-executing the program from the beginning. We wish to automate this. Step (2) is easy if we can somehow mark the last write found in step (1) and control the execution-point to move it back to this time. In this paper we propose a new concept, position, that is, a point in the program execution trace, as needed for step (2) above. The position enables debuggers to automate the control of program execution to support common debugging activities. We have implemented position in C by modifying GCC and in Java with a bytecode transformer. Measurements show that position can be provided with an acceptable amount of overhead.
Measuring Praise and Criticism: Inference of Semantic Orientation from Association
Venue: arXiv cs.CL 2003
Year: 2003

The evaluative character of a word is called its semantic orientation. Positive semantic orientation indicates praise (e.g., "honest", "intrepid") and negative semantic orientation indicates criticism (e.g., "disturbing", "superfluous"). Semantic orientation varies in both direction (positive or negative) and degree (mild to strong). An automated system for measuring semantic orientation would have application in text classification, text filtering, tracking opinions in online discussions, analysis of survey responses, and automated chat systems (chatbots). This paper introduces a method for inferring the semantic orientation of a word from its statistical association with a set of positive and negative paradigm words. Two instances of this approach are evaluated, based on two different statistical measures of word association: pointwise mutual information (PMI) and latent semantic analysis (LSA). The method is experimentally tested with 3,596 words (including adjectives, adverbs, nouns, and verbs) that have been manually labeled positive (1,614 words) and negative (1,982 words). The method attains an accuracy of 82.8% on the full test set, but the accuracy rises above 95% when the algorithm is allowed to abstain from classifying mild words.
The combinatorics of resource sharing
Venue: arXiv cs.OS 2003
Year: 2003

We discuss general models of resource-sharing computations, with emphasis on the combinatorial structures and concepts that underlie the various deadlock models that have been proposed, the design of algorithms and deadlock-handling policies, and concurrency issues. These structures are mostly graph-theoretic in nature, or partially ordered sets for the establishment of priorities among processes and acquisition orders on resources. We also discuss graph-coloring concepts as they relate to resource sharing.
The Graphics Card as a Streaming Computer
Venue: arXiv cs.GR 2003
Year: 2003

Massive data sets have radically changed our understanding of how to design efficient algorithms; the streaming paradigm, whether it in terms of number of passes of an external memory algorithm, or the single pass and limited memory of a stream algorithm, appears to be the dominant method for coping with large data. A very different kind of massive computation has had the same effect at the level of the CPU. The most prominent example is that of the computations performed by a graphics card. The operations themselves are very simple, and require very little memory, but require the ability to perform many computations extremely fast and in parallel to whatever degree possible. What has resulted is a stream processor that is highly optimized for stream computations. An intriguing side effect of this is the growing use of a graphics card as a general purpose stream processing engine. In an ever-increasing array of applications, researchers are discovering that performing a computation on a graphics card is far faster than performing it on a CPU, and so are using a GPU as a stream co-processor.
Transient Diversity in Multi-Agent Systems
Venue: arXiv cs.AI 2003
Year: 2003

Diversity is an important aspect of highly efficient multi-agent teams. We introduce the main factors that drive a multi-agent system in either direction along the diversity scale. A metric for diversity is described, and we speculate on the concept of transient diversity. Finally, an experiment on social entropy using a RoboCup simulated soccer team is presented.
Debugging Backwards in Time
Venue: arXiv cs.SE 2003
Year: 2003

By recording every state change in the run of a program, it is possible to present the programmer every bit of information that might be desired. Essentially, it becomes possible to debug the program by going ``backwards in time,'' vastly simplifying the process of debugging. An implementation of this idea, the ``Omniscient Debugger,'' is used to demonstrate its viability and has been used successfully on a number of large programs. Integration with an event analysis engine for searching and control is presented. Several small-scale user studies provide encouraging results. Finally performance issues and implementation are discussed along with possible optimizations. This paper makes three contributions of interest: the concept and technique of ``going backwards in time,'' the GUI which presents a global view of the program state and has a formal notion of ``navigation through time,'' and the integration with an event analyzer.
Circle and sphere blending with conformal geometric algebra
Venue: arXiv cs.CG 2003
Year: 2003

Blending schemes based on circles provide smooth `fair' interpolations between series of points. Here we demonstrate a simple, robust set of algorithms for performing circle blends for a range of cases. An arbitrary level of G-continuity can be achieved by simple alterations to the underlying parameterisation. Our method exploits the computational framework provided by conformal geometric algebra. This employs a five-dimensional representation of points in space, in contrast to the four-dimensional representation typically used in projective geometry. The advantage of the conformal scheme is that straight lines and circles are treated in a single, unified framework. As a further illustration of the power of the conformal framework, the basic idea is extended to the case of sphere blending to interpolate over a surface.
Application of Kullback-Leibler Metric to Speech Recognition
Venue: arXiv cs.AI 2003
Year: 2003

Article discusses the application of Kullback-Leibler divergence to the recognition of speech signals and suggests three algorithms implementing this divergence criterion: correlation algorithm, spectral algorithm and filter algorithm. Discussion covers an approach to the problem of speech variability and is illustrated with the results of experimental modeling of speech signals. The article gives a number of recommendations on the choice of appropriate model parameters and provides a comparison to some other methods of speech recognition.
A Hash of Hash Functions
Venue: arXiv cs.CR 2003
Year: 2003

In this paper, we present a general review of hash functions in a cryptographic sense. We give special emphasis on some particular topics such as cipher block chaining message authentication code (CBC MAC) and its variants. This paper also broadens the information given in some well known surveys, by including more details on block-cipher based hash functions and security of different hash schemes.
Supporting Exploratory Queries in Database Centric Web Applications
Venue: arXiv cs.DB 2003
Year: 2003

Users of database-centric Web applications, especially in the e-commerce domain, often resort to exploratory ``trial-and-error'' queries since the underlying data space is huge and unfamiliar, and there are several alternatives for search attributes in this space. For example, scouting for cheap airfares typically involves posing multiple queries, varying flight times, dates, and airport locations. Exploratory queries are problematic from the perspective of both the user and the server. For the database server, it results in a drastic reduction in effective throughput since much of the processing is duplicated in each successive query. For the client, it results in a marked increase in response times, especially when accessing the service through wireless channels. In this paper, we investigate the design of automated techniques to minimize the need for repetitive exploratory queries. Specifically, we present SAUNA, a server-side query relaxation algorithm that, given the user's initial range query and a desired cardinality for the answer set, produces a relaxed query that is expected to contain the required number of answers. The algorithm incorporates a range-query-specific distance metric that is weighted to produce relaxed queries of a desired shape (e.g. aspect ratio preserving), and utilizes multi-dimensional histograms for query size estimation. A detailed performance evaluation of SAUNA over a variety of multi-dimensional data sets indicates that its relaxed queries can significantly reduce the costs associated with exploratory query processing.