OpenRaiser/Intern-Atlas huggingface dataset:
Defining Rough Sets by Extended Logic Programs
Venue: arXiv cs.LO 2002
Year: 2002

We show how definite extended logic programs can be used for defining and reasoning with rough sets. Moreover, a rough-set-specific query language is presented and an answering algorithm is outlined. Thus, we not only show a possible application of a paraconsistent logic to the field of rough sets as we also establish a link between rough set theory and logic programming, making possible transfer of expertise between both fields.
Optimal Ordered Problem Solver
Venue: arXiv cs.AI 2002
Year: 2002

We present a novel, general, optimally fast, incremental way of searching for a universal algorithm that solves each task in a sequence of tasks. The Optimal Ordered Problem Solver (OOPS) continually organizes and exploits previously found solutions to earlier tasks, efficiently searching not only the space of domain-specific algorithms, but also the space of search algorithms. Essentially we extend the principles of optimal nonincremental universal search to build an incremental universal learner that is able to improve itself through experience. In illustrative experiments, our self-improver becomes the first general system that learns to solve all n disk Towers of Hanoi tasks (solution size 2^n-1) for n up to 30, profiting from previously solved, simpler tasks involving samples of a simple context free language.
Soft Concurrent Constraint Programming
Venue: arXiv cs.PL 2002
Year: 2002

Soft constraints extend classical constraints to represent multiple consistency levels, and thus provide a way to express preferences, fuzziness, and uncertainty. While there are many soft constraint solving formalisms, even distributed ones, by now there seems to be no concurrent programming framework where soft constraints can be handled. In this paper we show how the classical concurrent constraint (cc) programming framework can work with soft constraints, and we also propose an extension of cc languages which can use soft constraints to prune and direct the search for a solution. We believe that this new programming paradigm, called soft cc (scc), can be also very useful in many web-related scenarios. In fact, the language level allows web agents to express their interaction and negotiation protocols, and also to post their requests in terms of preferences, and the underlying soft constraint solver can find an agreement among the agents even if their requests are incompatible.
Online Scientific Data Curation, Publication, and Archiving
Venue: arXiv cs.DL 2002
Year: 2002

Science projects are data publishers. The scale and complexity of current and future science data changes the nature of the publication process. Publication is becoming a major project component. At a minimum, a project must preserve the ephemeral data it gathers. Derived data can be reconstructed from metadata, but metadata is ephemeral. Longer term, a project should expect some archive to preserve the data. We observe that pub-lished scientific data needs to be available forever ? this gives rise to the data pyramid of versions and to data inflation where the derived data volumes explode. As an example, this article describes the Sloan Digital Sky Survey (SDSS) strategies for data publication, data access, curation, and preservation.
Spatial Clustering of Galaxies in Large Datasets
Venue: arXiv cs.DB 2002
Year: 2002

Datasets with tens of millions of galaxies present new challenges for the analysis of spatial clustering. We have built a framework that integrates a database of object catalogs, tools for creating masks of bad regions, and a fast (NlogN) correlation code. This system has enabled unprecedented efficiency in carrying out the analysis of galaxy clustering in the SDSS catalog. A similar approach is used to compute the three-dimensional spatial clustering of galaxies on very large scales. We describe our strategy to estimate the effect of photometric errors using a database. We discuss our efforts as an early example of data-intensive science. While it would have been possible to get these results without the framework we describe, it will be infeasible to perform these computations on the future huge datasets without using this framework.
Contact-Based Architecture for Resource Discovery (CARD) in Large Scale MANets
Venue: arXiv cs.NI 2002
Year: 2002

In this paper we propose a novel architecture, CARD, for resource discovery in large scale Mobile Ad hoc Networks (MANets) which, may scale up to thousands of nodes and may span wide geographical regions. Unlike previously proposed schemes, our architecture avoids expensive mechanisms such as global flooding as well as complex coordination between nodes to form a hierarchy. CARD is also independent of any external source of information such as GPS. In our architecture nodes within a limited number of hops from each node form the neighborhood of that node. Resources within the neighborhood can be readily accessed with the help of a proactive scheme within the neighborhood. For accessing resources beyond the neighborhood, each node also maintains a few distant nodes called contacts. Contacts help in creating a small world in the network and provide an efficient way to query for resources beyond the neighborhood. As the number of contacts of a node increases, the network view (reachability) of the node increases. Paths to contacts are validated periodically to adapt to mobility. We present mechanisms for contact selection and maintenance that attempt to increase reachability while minimizing overhead. Our simulation results show a clear trade-off between increase in reachability on one hand, and contact selection and maintenance overhead on the other. Our results suggest that CARD can be configured to provide a desirable reachability distribution for different network sizes. Comparisons with other schemes for resource discovery, such as flooding and bordercasting, show our architecture to be much more efficient and scalable.
Evaluation of Coreference Rules on Complex Narrative Texts
Venue: arXiv cs.CL 2002
Year: 2002

This article studies the problem of assessing relevance to each of the rules of a reference resolution system. The reference solver described here stems from a formal model of reference and is integrated in a reference processing workbench. Evaluation of the reference resolution is essential, as it enables differential evaluation of individual rules. Numerical values of these measures are given, and discussed, for simple selection rules and other processing rules; such measures are then studied for numerical parameters.
Analysis of Non-Gaussian Nature of Network Traffic and its Implication on Network Performance
Venue: arXiv cs.NI 2002
Year: 2002

We analyzed the non-Gaussian nature of network traffic using some Internet traffic data. We found that (1) the non-Gaussian nature degrades network performance, (2) it is caused by `greedy flows' that exist with non-negligible probability, and (3) a large majority of `greedy flows' are TCP flows having relatively small hop counts, which correspond to small round-trip times. We conclude that in a network hat has greedy flows with non-negligible probability, a traffic controlling scheme or bandwidth design that considers non-Gaussian nature is essential.
Minimum-Energy Mobile Wireless Networks Revisited
Venue: arXiv cs.NI 2002
Year: 2002

We propose a protocol that, given a communication network, computes a subnetwork such that, for every pair $(u,v)$ of nodes connected in the original network, there is a minimum-energy path between $u$ and $v$ in the subnetwork (where a minimum-energy path is one that allows messages to be transmitted with a minimum use of energy). The network computed by our protocol is in general a subnetwork of the one computed by the protocol given in [13]. Moreover, our protocol is computationally simpler. We demonstrate the performance improvements obtained by using the subnetwork computed by our protocol through simulation.
Sorting with a forklift
Venue: arXiv cs.DM 2002
Year: 2002

A fork stack is a generalised stack which allows pushes and pops of several items at a time. We consider the problem of determining which input streams can be sorted using a single forkstack, or dually, which permutations of a fixed input stream can be produced using a single forkstack. An algorithm is given to solve the sorting problem and the minimal unsortable sequences are found. The results are extended to fork stacks where there are bounds on how many items can be pushed and popped at one time. In this context we also establish how to enumerate the collection of sortable sequences.
Activities, Context and Ubiquitous Computing
Venue: arXiv cs.IR 2002
Year: 2002

Context and context-awareness provides computing environments with the ability to usefully adapt the services or information they provide. It is the ability to implicitly sense and automatically derive the user needs that separates context-aware applications from traditionally designed applications, and this makes them more attentive, responsive, and aware of their user's identity, and their user's environment. This paper argues that context-aware applications capable of supporting complex, cognitive activities can be built from a model of context called Activity-Centric Context. A conceptual model of Activity-Centric context is presented. The model is illustrated via a detailed example.
Practical Load Balancing for Content Requests in Peer-to-Peer Networks
Venue: arXiv cs.NI 2002
Year: 2002

This paper studies the problem of load-balancing the demand for content in a peer-to-peer network across heterogeneous peer nodes that hold replicas of the content. Previous decentralized load balancing techniques in distributed systems base their decisions on periodic updates containing information about load or available capacity observed at the serving entities. We show that these techniques do not work well in the peer-to-peer context; either they do not address peer node heterogeneity, or they suffer from significant load oscillations. We propose a new decentralized algorithm, Max-Cap, based on the maximum inherent capacities of the replica nodes and show that unlike previous algorithms, it is not tied to the timeliness or frequency of updates. Yet, Max-Cap can handle the heterogeneity of a peer-to-peer environment without suffering from load oscillations.
A universal alphabet and rewrite system
Venue: arXiv cs.OH 2002
Year: 2002

We present two ways in which an infinite universal alphabet may be generated using a novel rewrite system that conserves zero (a special character of the alphabet and the symbol for that character) at every step. The recursive method delivers the entire alphabet in one step when invoked with the zero character as the initial subset alphabet. The iterative method with the same start delivers characters that act as ciphers for properties that the developing subset alphabet contains. These properties emerge in an arbitrary sequence and there are an infinite number of ways they may be selected. The subset alphabets in addition to having mathematical interpretation as algebra can also be constrained to emerge in a minimal way which then has application as a foundational physical system. Each subset alphabet may itself be the basis of a rewrite system where rules that operate on symbols (representing characters) or collections of symbols manipulate the specific properties in a dynamic way.
Remarks on d-Dimensional TSP Optimal Tour Length Behaviour
Venue: arXiv cs.CG 2002
Year: 2002

The well-known $O(n^{1-1/d})$ behaviour of the optimal tour length for TSP in d-dimensional Cartesian space causes breaches of the triangle inequality. Other practical inadequacies of this model are discussed, including its use as basis for approximation of the TSP optimal tour length or bounds derivations, which I attempt to remedy.
Locating Data in (Small-World?) Peer-to-Peer Scientific Collaborations
Venue: arXiv cs.DC 2002
Year: 2002

Data-sharing scientific collaborations have particular characteristics, potentially different from the current peer-to-peer environments. In this paper we advocate the benefits of exploiting emergent patterns in self-configuring networks specialized for scientific data-sharing collaborations. We speculate that a peer-to-peer scientific collaboration network will exhibit small-world topology, as do a large number of social networks for which the same pattern has been documented. We propose a solution for locating data in decentralized, scientific, data-sharing environments that exploits the small-worlds topology. The research challenge we raise is: what protocols should be used to allow a self-configuring peer-to-peer network to form small worlds similar to the way in which the humans that use the network do in their social interactions?
On the Cell-based Complexity of Recognition of Bounded Configurations by Finite Dynamic Cellular Automata
Venue: arXiv cs.CC 2002
Year: 2002

This paper studies complexity of recognition of classes of bounded configurations by a generalization of conventional cellular automata (CA) -- finite dynamic cellular automata (FDCA). Inspired by the CA-based models of biological and computer vision, this study attempts to derive the properties of a complexity measure and of the classes of input configurations that make it beneficial to realize the recognition via a two-layered automaton as compared to a one-layered automaton. A formalized model of an image pattern recognition task is utilized to demonstrate that the derived conditions can be satisfied for a non-empty set of practical problems.
Tetris is Hard, Even to Approximate
Venue: arXiv cs.CC 2002
Year: 2002

In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled squares; any completely filled row of the gameboard is cleared and all pieces above it drop by one row. We prove that in the offline version of Tetris, it is NP-complete to maximize the number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously filled and cleared), minimize the maximum height of an occupied square, or maximize the number of pieces placed before the game ends. We furthermore show the extreme inapproximability of the first and last of these objectives to within a factor of p^(1-epsilon), when given a sequence of p pieces, and the inapproximability of the third objective to within a factor of (2 - epsilon), for any epsilon>0. Our results hold under several variations on the rules of Tetris, including different models of rotation, limitations on player agility, and restricted piece sets.
Prosody Based Co-analysis for Continuous Recognition of Coverbal Gestures
Venue: arXiv cs.CV 2002
Year: 2002

Although speech and gesture recognition has been studied extensively, all the successful attempts of combining them in the unified framework were semantically motivated, e.g., keyword-gesture cooccurrence. Such formulations inherited the complexity of natural language processing. This paper presents a Bayesian formulation that uses a phenomenon of gesture and speech articulation for improving accuracy of automatic recognition of continuous coverbal gestures. The prosodic features from the speech signal were coanalyzed with the visual signal to learn the prior probability of co-occurrence of the prominent spoken segments with the particular kinematical phases of gestures. It was found that the above co-analysis helps in detecting and disambiguating visually small gestures, which subsequently improves the rate of continuous gesture recognition. The efficacy of the proposed approach was demonstrated on a large database collected from the weather channel broadcast. This formulation opens new avenues for bottom-up frameworks of multimodal integration.
Integration of Computational Techniques for the Modelling of Signal Transduction
Venue: arXiv cs.MA 2002
Year: 2002

A cell can be seen as an adaptive autonomous agent or as a society of adaptive autonomous agents, where each can exhibit a particular behaviour depending on its cognitive capabilities. We present an intracellular signalling model obtained by integrating several computational techniques into an agent-based paradigm. Cellulat, the model, takes into account two essential aspects of the intracellular signalling networks: cognitive capacities and a spatial organization. Exemplifying the functionality of the system by modelling the EGFR signalling pathway, we discuss the methodology as well as the purposes of an intracellular signalling virtual laboratory, presently under development.
Propositional satisfiability in declarative programming
Venue: arXiv cs.LO 2002
Year: 2002

Answer-set programming (ASP) paradigm is a way of using logic to solve search problems. Given a search problem, to solve it one designs a theory in the logic so that models of this theory represent problem solutions. To compute a solution to a problem one needs to compute a model of the corresponding theory. Several answer-set programming formalisms have been developed on the basis of logic programming with the semantics of stable models. In this paper we show that also the logic of predicate calculus gives rise to effective implementations of the ASP paradigm, similar in spirit to logic programming with stable model semantics and with a similar scope of applicability. Specifically, we propose two logics based on predicate calculus as formalisms for encoding search problems. We show that the expressive power of these logics is given by the class NP-search. We demonstrate how to use them in programming and develop computational tools for model finding. In the case of one of the logics our techniques reduce the problem to that of propositional satisfiability and allow one to use off-the-shelf satisfiability solvers. The language of the other logic has more complex syntax and provides explicit means to model some high-level constraints. For theories in this logic, we designed our own solver that takes advantage of the expanded syntax. We present experimental results demonstrating computational effectiveness of the overall approach.
Dynamic Adjustment of the Motivation Degree in an Action Selection Mechanism
Venue: arXiv cs.AI 2002
Year: 2002

This paper presents a model for dynamic adjustment of the motivation degree, using a reinforcement learning approach, in an action selection mechanism previously developed by the authors. The learning takes place in the modification of a parameter of the model of combination of internal and external stimuli. Experiments that show the claimed properties are presented, using a VR simulation developed for such purposes. The importance of adaptation by learning in action selection is also discussed.
Action Selection Properties in a Software Simulated Agent
Venue: arXiv cs.AI 2002
Year: 2002

This article analyses the properties of the Internal Behaviour network, an action selection mechanism previously proposed by the authors, with the aid of a simulation developed for such ends. A brief review of the Internal Behaviour network is followed by the explanation of the implementation of the simulation. Then, experiments are presented and discussed analysing the properties of the action selection in the proposed model.
On the survey-propagation equations for the random K-satisfiability problem
Venue: arXiv cs.CC 2002
Year: 2002

In this note we study the existence of a solution to the survey-propagation equations for the random K-satisfiability problem for a given instance. We conjecture that when the number of variables goes to infinity, the solution of these equations for a given instance can be approximated by the solution of the corresponding equations on an infinite tree. We conjecture (and we bring numerical evidence) that the survey-propagation equations on the infinite tree have an unique solution in the suitable range of parameters.
Unsupervised Learning of Semantic Orientation from a Hundred-Billion-Word Corpus
Venue: arXiv cs.LG 2002
Year: 2002

The evaluative character of a word is called its semantic orientation. A positive semantic orientation implies desirability (e.g., "honest", "intrepid") and a negative semantic orientation implies undesirability (e.g., "disturbing", "superfluous"). This paper introduces a simple algorithm for unsupervised learning of semantic orientation from extremely large corpora. The method involves issuing queries to a Web search engine and using pointwise mutual information to analyse the results. The algorithm is empirically evaluated using a training corpus of approximately one hundred billion words -- the subset of the Web that is indexed by the chosen search engine. Tested with 3,596 words (1,614 positive and 1,982 negative), the algorithm attains an accuracy of 80%. The 3,596 test words include adjectives, adverbs, nouns, and verbs. The accuracy is comparable with the results achieved by Hatzivassiloglou and McKeown (1997), using a complex four-stage supervised learning algorithm that is restricted to determining the semantic orientation of adjectives.
Extraction of Keyphrases from Text: Evaluation of Four Algorithms
Venue: arXiv cs.LG 2002
Year: 2002

This report presents an empirical evaluation of four algorithms for automatically extracting keywords and keyphrases from documents. The four algorithms are compared using five different collections of documents. For each document, we have a target set of keyphrases, which were generated by hand. The target keyphrases were generated for human readers; they were not tailored for any of the four keyphrase extraction algorithms. Each of the algorithms was evaluated by the degree to which the algorithm's keyphrases matched the manually generated keyphrases. The four algorithms were (1) the AutoSummarize feature in Microsoft's Word 97, (2) an algorithm based on Eric Brill's part-of-speech tagger, (3) the Summarize feature in Verity's Search 97, and (4) NRC's Extractor algorithm. For all five document collections, NRC's Extractor yields the best match with the manually generated keyphrases.
Real numbers having ultimately periodic representations in abstract numeration systems
Venue: arXiv cs.CC 2002
Year: 2002

Using a genealogically ordered infinite regular language, we know how to represent an interval of R. Numbers having an ultimately periodic representation play a special role in classical numeration systems. The aim of this paper is to characterize the numbers having an ultimately periodic representation in generalized systems built on a regular language. The syntactical properties of these words are also investigated. Finally, we show the equivalence of the classical "theta"-expansions with our generalized representations in some special case related to a Pisot number "theta".
Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments
Venue: arXiv cs.RO 2002
Year: 2002

We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire region. An environment is composed of pixels that form a connected subset of the integer grid. There is at most one robot per pixel and robots move horizontally or vertically at unit speed. Robots enter R by means of k>=1 door pixels Robots are primitive finite automata, only having local communication, local sensors, and a constant-sized memory. We first give algorithms for the single-door case (i.e., k=1), analyzing the algorithms both theoretically and experimentally. We prove that our algorithms have optimal makespan 2A-1, where A is the area of R. We next give an algorithm for the multi-door case (k>1), based on a wall-following version of the leader-follower strategy. We prove that our strategy is O(log(k+1))-competitive, and that this bound is tight for our strategy and other related strategies.