OpenRaiser/Intern-Atlas huggingface dataset:
Constraint Exploration and Envelope of Simulation Trajectories
Venue: arXiv cs.PL 2000
Year: 2000

The implicit theory that a simulation represents is precisely not in the individual choices but rather in the 'envelope' of possible trajectories - what is important is the shape of the whole envelope. Typically a huge amount of computation is required when experimenting with factors bearing on the dynamics of a simulation to tease out what affects the shape of this envelope. In this paper we present a methodology aimed at systematically exploring this envelope. We propose a method for searching for tendencies and proving their necessity relative to a range of parameterisations of the model and agents' choices, and to the logic of the simulation language. The exploration consists of a forward chaining generation of the trajectories associated to and constrained by such a range of parameterisations and choices. Additionally, we propose a computational procedure that helps implement this exploration by translating a Multi Agent System simulation into a constraint-based search over possible trajectories by 'compiling' the simulation rules into a more specific form, namely by partitioning the simulation rules using appropriate modularity in the simulation. An example of this procedure is exhibited. Keywords: Constraint Search, Constraint Logic Programming, Proof, Emergence, Tendencies
Naive Bayes and Exemplar-Based approaches to Word Sense Disambiguation Revisited
Venue: arXiv cs.CL 2000
Year: 2000

This paper describes an experimental comparison between two standard supervised learning methods, namely Naive Bayes and Exemplar-based classification, on the Word Sense Disambiguation (WSD) problem. The aim of the work is twofold. Firstly, it attempts to contribute to clarify some confusing information about the comparison between both methods appearing in the related literature. In doing so, several directions have been explored, including: testing several modifications of the basic learning algorithms and varying the feature space. Secondly, an improvement of both algorithms is proposed, in order to deal with large attribute sets. This modification, which basically consists in using only the positive information appearing in the examples, allows to improve greatly the efficiency of the methods, with no loss in accuracy. The experiments have been performed on the largest sense-tagged corpus available containing the most frequent and ambiguous English words. Results show that the Exemplar-based approach to WSD is generally superior to the Bayesian approach, especially when a specific metric for dealing with symbolic attributes is used.
Phase Clocks for Transient Fault Repair
Venue: arXiv cs.DC 2000
Year: 2000

Phase clocks are synchronization tools that implement a form of logical time in distributed systems. For systems tolerating transient faults by self-repair of damaged data, phase clocks can enable reasoning about the progress of distributed repair procedures. This paper presents a phase clock algorithm suited to the model of transient memory faults in asynchronous systems with read/write registers. The algorithm is self-stabilizing and guarantees accuracy of phase clocks within O(k) time following an initial state that is k-faulty. Composition theorems show how the algorithm can be used for the timing of distributed procedures that repair system outputs.
Two Steps Feature Selection and Neural Network Classification for the TREC-8 Routing
Venue: arXiv cs.CL 2000
Year: 2000

For the TREC-8 routing, one specific filter is built for each topic. Each filter is a classifier trained to recognize the documents that are relevant to the topic. When presented with a document, each classifier estimates the probability for the document to be relevant to the topic for which it has been trained. Since the procedure for building a filter is topic-independent, the system is fully automatic. By making use of a sample of documents that have previously been evaluated as relevant or not relevant to a particular topic, a term selection is performed, and a neural network is trained. Each document is represented by a vector of frequencies of a list of selected terms. This list depends on the topic to be filtered; it is constructed in two steps. The first step defines the characteristic words used in the relevant documents of the corpus; the second one chooses, among the previous list, the most discriminant ones. The length of the vector is optimized automatically for each topic. At the end of the term selection, a vector of typically 25 words is defined for the topic, so that each document which has to be processed is represented by a vector of term frequencies. This vector is subsequently input to a classifier that is trained from the same sample. After training, the classifier estimates for each document of a test set its probability of being relevant; for submission to TREC, the top 1000 documents are ranked in order of decreasing relevance.
PushPush and Push-1 are NP-hard in 2D
Venue: arXiv cs.CG 2000
Year: 2000

We prove that two pushing-blocks puzzles are intractable in 2D. One of our constructions improves an earlier result that established intractability in 3D [OS99] for a puzzle inspired by the game PushPush. The second construction answers a question we raised in [DDO00] for a variant we call Push-1. Both puzzles consist of unit square blocks on an integer lattice; all blocks are movable. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover when a block is pushed it slides the maximal extent of its free range. In the Push-1 version, the agent can only push one block one square at a time, the minimal extent---one square. Both NP-hardness proofs are by reduction from SAT, and rely on a common construction.
A Moment of Perfect Clarity I: The Parallel Census Technique
Venue: arXiv cs.CC 2000
Year: 2000

We discuss the history and uses of the parallel census technique---an elegant tool in the study of certain computational objects having polynomially bounded census functions. A sequel will discuss advances (including Cai, Naik, and Sivakumar [CNS95] and Glasser [Gla00]), some related to the parallel census technique and some due to other approaches, in the complexity-class collapses that follow if NP has sparse hard sets under reductions weaker than (full) truth-table reductions.
Parameter-free Model of Rank Polysemantic Distribution
Venue: arXiv cs.CL 2000
Year: 2000

A model of rank polysemantic distribution with a minimal number of fitting parameters is offered. In an ideal case a parameter-free description of the dependence on the basis of one or several immediate features of the distribution is possible.
The Competitiveness of On-Line vis-a-vis Conventional Retailing: A Preliminary Study
Venue: arXiv cs.OH 2000
Year: 2000

Previous research has directly studied whether on-line retailing is more competitive than conventional retail markets. The evidence from books and music CDs is mixed. Here, I use an indirect approach to compare the competitiveness of on-line with conventional markets. Focusing on the retail market for books, I identify a peculiarity in the pricing of bestsellers relative to other titles. Supposing that competitive barriers are lower in on-line retailing, I analyze how the lower barriers would affect the relative pricing of bestsellers. The empirical data indicates that on-line retailing is more competitive than conventional retailing.
Computational Geometry Column 39
Venue: arXiv cs.CG 2000
Year: 2000

The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.
Data Mining to Measure and Improve the Success of Web Sites
Venue: arXiv cs.LG 2000
Year: 2000

For many companies, competitiveness in e-commerce requires a successful presence on the web. Web sites are used to establish the company's image, to promote and sell goods and to provide customer support. The success of a web site affects and reflects directly the success of the company in the electronic market. In this study, we propose a methodology to improve the ``success'' of web sites, based on the exploitation of navigation pattern discovery. In particular, we present a theory, in which success is modelled on the basis of the navigation behaviour of the site's users. We then exploit WUM, a navigation pattern discovery miner, to study how the success of a site is reflected in the users' behaviour. With WUM we measure the success of a site's components and obtain concrete indications of how the site should be improved. We report on our first experiments with an online catalog, the success of which we have studied. Our mining analysis has shown very promising results, on the basis of which the site is currently undergoing concrete improvements.
An Experimental Comparison of Naive Bayesian and Keyword-Based Anti-Spam Filtering with Personal E-mail Messages
Venue: arXiv cs.CL 2000
Year: 2000

The growing problem of unsolicited bulk e-mail, also known as "spam", has generated a need for reliable anti-spam e-mail filters. Filters of this type have so far been based mostly on manually constructed keyword patterns. An alternative approach has recently been proposed, whereby a Naive Bayesian classifier is trained automatically to detect spam messages. We test this approach on a large collection of personal e-mail messages, which we make publicly available in "encrypted" form contributing towards standard benchmarks. We introduce appropriate cost-sensitive measures, investigating at the same time the effect of attribute-set size, training-corpus size, lemmatization, and stop lists, issues that have not been explored in previous experiments. Finally, the Naive Bayesian filter is compared, in terms of performance, to a filter that uses keyword patterns, and which is part of a widely used e-mail reader.
Selectional Restrictions in HPSG
Venue: arXiv cs.CL 2000
Year: 2000

Selectional restrictions are semantic sortal constraints imposed on the participants of linguistic constructions to capture contextually-dependent constraints on interpretation. Despite their limitations, selectional restrictions have proven very useful in natural language applications, where they have been used frequently in word sense disambiguation, syntactic disambiguation, and anaphora resolution. Given their practical value, we explore two methods to incorporate selectional restrictions in the HPSG theory, assuming that the reader is familiar with HPSG. The first method employs HPSG's Background feature and a constraint-satisfaction component pipe-lined after the parser. The second method uses subsorts of referential indices, and blocks readings that violate selectional restrictions during parsing. While theoretically less satisfactory, we have found the second method particularly useful in the development of practical systems.
Estimators for Stochastic ``Unification-Based'' Grammars
Venue: arXiv cs.CL 2000
Year: 2000

Log-linear models provide a statistically sound framework for Stochastic ``Unification-Based'' Grammars (SUBGs) and stochastic versions of other kinds of grammars. We describe two computationally-tractable ways of estimating the parameters of such grammars from a training corpus of syntactic analyses, and apply these to estimate a stochastic version of Lexical-Functional Grammar.
Fast Approximation of Centrality
Venue: arXiv cs.DS 2000
Year: 2000

Social studies researchers use graphs to model group activities in social networks. An important property in this context is the centrality of a vertex: the inverse of the average distance to each other vertex. We describe a randomized approximation algorithm for centrality in weighted graphs. For graphs exhibiting the small world phenomenon, our method estimates the centrality of all vertices with high probability within a (1+epsilon) factor in near-linear time.
Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction
Venue: arXiv cs.DS 2000
Year: 2000

We consider worst case time bounds for NP-complete problems including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a constraint satisfaction (CSP) formulation of these problems; 3-SAT is equivalent to (2,3)-CSP while the other problems above are special cases of (3,2)-CSP. We give a fast algorithm for (3,2)-CSP and use it to improve the time bounds for solving the other problems listed above. Our techniques involve a mixture of Davis-Putnam-style backtracking with more sophisticated matching and network flow based ideas.
Learning to Filter Spam E-Mail: A Comparison of a Naive Bayesian and a Memory-Based Approach
Venue: arXiv cs.CL 2000
Year: 2000

We investigate the performance of two machine learning algorithms in the context of anti-spam filtering. The increasing volume of unsolicited bulk e-mail (spam) has generated a need for reliable anti-spam filters. Filters of this type have so far been based mostly on keyword patterns that are constructed by hand and perform poorly. The Naive Bayesian classifier has recently been suggested as an effective method to construct automatically anti-spam filters with superior performance. We investigate thoroughly the performance of the Naive Bayesian filter on a publicly available corpus, contributing towards standard benchmarks. At the same time, we compare the performance of the Naive Bayesian filter to an alternative memory-based learning approach, after introducing suitable cost-sensitive evaluation measures. Both methods achieve very accurate spam filtering, outperforming clearly the keyword-based filter of a widely used e-mail reader.
Contextual Inference in Computational Semantics
Venue: arXiv cs.CL 2000
Year: 2000

In this paper, an application of automated theorem proving techniques to computational semantics is considered. In order to compute the presuppositions of a natural language discourse, several inference tasks arise. Instead of treating these inferences independently of each other, we show how integrating techniques from formal approaches to context into deduction can help to compute presuppositions more efficiently. Contexts are represented as Discourse Representation Structures and the way they are nested is made explicit. In addition, a tableau calculus is present which keeps track of contextual information, and thereby allows to avoid carrying out redundant inference steps as it happens in approaches that neglect explicit nesting of contexts.
A Tableau Calculus for Pronoun Resolution
Venue: arXiv cs.CL 2000
Year: 2000

We present a tableau calculus for reasoning in fragments of natural language. We focus on the problem of pronoun resolution and the way in which it complicates automated theorem proving for natural language processing. A method for explicitly manipulating contextual information during deduction is proposed, where pronouns are resolved against this context during deduction. As a result, pronoun resolution and deduction can be interleaved in such a way that pronouns are only resolved if this is licensed by a deduction rule; this helps us to avoid the combinatorial complexity of total pronoun disambiguation.
Computing Presuppositions by Contextual Reasoning
Venue: arXiv cs.AI 2000
Year: 2000

This paper describes how automated deduction methods for natural language processing can be applied more efficiently by encoding context in a more elaborate way. Our work is based on formal approaches to context, and we provide a tableau calculus for contextual reasoning. This is explained by considering an example from the problem area of presupposition projection.
From Syntactic Theories to Interpreters: A Specification Language and Its Compilation
Venue: arXiv cs.PL 2000
Year: 2000

Recent years have seen an increasing need of high-level specification languages and tools generating code from specifications. In this paper, we introduce a specification language, {\splname}, which is tailored to the writing of syntactic theories of language semantics. More specifically, the language supports specifying primitive notions such as dynamic constraints, contexts, axioms, and inference rules. We also introduce a system which generates interpreters from {\splname} specifications. A prototype system is implemented and has been tested on a number of examples, including a syntactic theory for Verilog.
A Public-key based Information Management Model for Mobile Agents
Venue: arXiv cs.CR 2000
Year: 2000

Mobile code based computing requires development of protection schemes that allow digital signature and encryption of data collected by the agents in untrusted hosts. These algorithms could not rely on carrying encryption keys if these keys could be stolen or used to counterfeit data by hostile hosts and agents. As a consequence, both information and keys must be protected in a way that only authorized hosts, that is the host that provides information and the server that has sent the mobile agent, could modify (by changing or removing) retrieved data. The data management model proposed in this work allows the information collected by the agents to be protected against handling by other hosts in the information network. It has been done by using standard public-key cryptography modified to support protection of data in distributed environments without requiring an interactive protocol with the host that has dropped the agent. Their significance stands on the fact that it is the first model that supports a full-featured protection of mobile agents allowing remote hosts to change its own information if required before agent returns to its originating server.
Enriching very large ontologies using the WWW
Venue: arXiv cs.CL 2000
Year: 2000

This paper explores the possibility to exploit text on the world wide web in order to enrich the concepts in existing ontologies. First, a method to retrieve documents from the WWW related to a concept is described. These document collections are used 1) to construct topic signatures (lists of topically related words) for each concept in WordNet, and 2) to build hierarchical clusters of the concepts (the word senses) that lexicalize a given word. The overall goal is to overcome two shortcomings of WordNet: the lack of topical links among concepts, and the proliferation of senses. Topic signatures are validated on a word sense disambiguation task with good results, which are improved when the hierarchical clusters are used.
Collecting Graphical Abstract Views of Mercury Program Executions
Venue: arXiv cs.SE 2000
Year: 2000

A program execution monitor is a program that collects and abstracts information about program executions. The "collect" operator is a high level, general purpose primitive which lets users implement their own monitors. "Collect" is built on top of the Mercury trace. In previous work, we have demonstrated how this operator can be used to efficiently collect various kinds of statistics about Mercury program executions. In this article we further demonstrate the expressive power and effectiveness of "collect" by providing more monitor examples. In particular, we show how to implement monitors that generate graphical abstractions of program executions such as proof trees, control flow graphs and dynamic call graphs. We show how those abstractions can be easily modified and adapted, since those monitors only require several dozens of lines of code. Those abstractions are intended to serve as front-ends of software visualization tools. Although "collect" is currently implemented on top of the Mercury trace, none of its underlying concepts depend of Mercury and it can be implemented on top of any tracer for any programming language.
A Novelty-based Evaluation Method for Information Retrieval
Venue: arXiv cs.CL 2000
Year: 2000

In information retrieval research, precision and recall have long been used to evaluate IR systems. However, given that a number of retrieval systems resembling one another are already available to the public, it is valuable to retrieve novel relevant documents, i.e., documents that cannot be retrieved by those existing systems. In view of this problem, we propose an evaluation method that favors systems retrieving as many novel documents as possible. We also used our method to evaluate systems that participated in the IREX workshop.
Extension Language Automation of Embedded System Debugging
Venue: arXiv cs.SE 2000
Year: 2000

Embedded systems contain several layers of target processing abstraction. These layers include electronic circuit, binary machine code, mnemonic assembly code, and high-level procedural and object-oriented abstractions. Physical and temporal constraints and artifacts within physically embedded systems make it impossible for software engineers to operate at a single layer of processor abstraction. The Luxdbg embedded system debugger exposes these layers to debugger users, and it adds an additional layer, the extension language layer, that allows users to extend both the debugger and its target processor capabilities. Tcl is Luxdbg's extension language. Luxdbg users can apply Tcl to automate interactive debugging steps, to redirect and to interconnect target processor input-output facilities, to schedule multiple processor execution, to log and to react to target processing exceptions, and to automate target system testing. Inclusion of an extension language like Tcl in a debugger promises additional advantages for distributed debugging, where debuggers can pass extension language expressions across computer networks.
Transformation-Based Bottom-Up Computation of the Well-Founded Model
Venue: arXiv cs.LO 2000
Year: 2000

We present a framework for expressing bottom-up algorithms to compute the well-founded model of non-disjunctive logic programs. Our method is based on the notion of conditional facts and elementary program transformations studied by Brass and Dix for disjunctive programs. However, even if we restrict their framework to nondisjunctive programs, their residual program can grow to exponential size, whereas for function-free programs our program remainder is always polynomial in the size of the extensional database (EDB). We show that particular orderings of our transformations (we call them strategies) correspond to well-known computational methods like the alternating fixpoint approach, the well-founded magic sets method and the magic alternating fixpoint procedure. However, due to the confluence of our calculi, we come up with computations of the well-founded model that are provably better than these methods. In contrast to other approaches, our transformation method treats magic set transformed programs correctly, i.e. it always computes a relevant part of the well-founded model of the original program.
A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions
Venue: arXiv cs.CC 2000
Year: 2000

This paper discusses advances, due to the work of Cai, Naik, and Sivakumar and Glasser, in the complexity class collapses that follow if NP has sparse hard sets under reductions weaker than (full) truth-table reductions.
Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions
Venue: arXiv cs.CE 2000
Year: 2000

This paper studies some basic problems in a multiple-object auction model using methodologies from theoretical computer science. We are especially concerned with situations where an adversary bidder knows the bidding algorithms of all the other bidders. In the two-bidder case, we derive an optimal randomized bidding algorithm, by which the disadvantaged bidder can procure at least half of the auction objects despite the adversary's a priori knowledge of his algorithm. In the general $k$-bidder case, if the number of objects is a multiple of $k$, an optimal randomized bidding algorithm is found. If the $k-1$ disadvantaged bidders employ that same algorithm, each of them can obtain at least $1/k$ of the objects regardless of the bidding algorithm the adversary uses. These two algorithms are based on closed-form solutions to certain multivariate probability distributions. In situations where a closed-form solution cannot be obtained, we study a restricted class of bidding algorithms as an approximation to desired optimal algorithms.