OpenRaiser/Intern-Atlas huggingface dataset:
Pronoun Resolution in Japanese Sentences Using Surface Expressions and Examples
Venue: arXiv cs.CL 1999
Year: 1999

In this paper, we present a method of estimating referents of demonstrative pronouns, personal pronouns, and zero pronouns in Japanese sentences using examples, surface expressions, topics and foci. Unlike conventional work which was semantic markers for semantic constraints, we used examples for semantic constraints and showed in our experiments that examples are as useful as semantic markers. We also propose many new methods for estimating referents of pronouns. For example, we use the form ``X of Y'' for estimating referents of demonstrative adjectives. In addition to our new methods, we used many conventional methods. As a result, experiments using these methods obtained a precision rate of 87% in estimating referents of demonstrative pronouns, personal pronouns, and zero pronouns for training sentences, and obtained a precision rate of 78% for test sentences.
Avoiding Braess' Paradox through Collective Intelligence
Venue: arXiv cs.DC 1999
Year: 1999

In an Ideal Shortest Path Algorithm (ISPA), at each moment each router in a network sends all of its traffic down the path that will incur the lowest cost to that traffic. In the limit of an infinitesimally small amount of traffic for a particular router, its routing that traffic via an ISPA is optimal, as far as cost incurred by that traffic is concerned. We demonstrate though that in many cases, due to the side-effects of one router's actions on another routers performance, having routers use ISPA's is suboptimal as far as global aggregate cost is concerned, even when only used to route infinitesimally small amounts of traffic. As a particular example of this we present an instance of Braess' paradox for ISPA's, in which adding new links to a network decreases overall throughput. We also demonstrate that load-balancing, in which the routing decisions are made to optimize the global cost incurred by all traffic currently being routed, is suboptimal as far as global cost averaged across time is concerned. This is also due to "side-effects", in this case of current routing decision on future traffic. The theory of COllective INtelligence (COIN) is concerned precisely with the issue of avoiding such deleterious side-effects. We present key concepts from that theory and use them to derive an idealized algorithm whose performance is better than that of the ISPA, even in the infinitesimal limit. We present experiments verifying this, and also showing that a machine-learning-based version of this COIN algorithm in which costs are only imprecisely estimated (a version potentially applicable in the real world) also outperforms the ISPA, despite having access to less information than does the ISPA. In particular, this COIN algorithm avoids Braess' paradox.
Multivariate Regression Depth
Venue: arXiv cs.CG 1999
Year: 1999

The regression depth of a hyperplane with respect to a set of n points in R^d is the minimum number of points the hyperplane must pass through in a rotation to vertical. We generalize hyperplane regression depth to k-flats for any k between 0 and d-1. The k=0 case gives the classical notion of center points. We prove that for any k and d, deep k-flats exist, that is, for any set of n points there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1+epsilon)-approximation algorithm for the deepest flat.
Comparative Analysis of Five XML Query Languages
Venue: arXiv cs.DB 1999
Year: 1999

XML is becoming the most relevant new standard for data representation and exchange on the WWW. Novel languages for extracting and restructuring the XML content have been proposed, some in the tradition of database query languages (i.e. SQL, OQL), others more closely inspired by XML. No standard for XML query language has yet been decided, but the discussion is ongoing within the World Wide Web Consortium and within many academic institutions and Internet-related major companies. We present a comparison of five, representative query languages for XML, highlighting their common features and differences.
Compositionality, Synonymy, and the Systematic Representation of Meaning
Venue: arXiv cs.CL 2000
Year: 2000

In a recent issue of Linguistics and Philosophy Kasmi and Pelletier (1998) (K&P), and Westerstahl (1998) criticize Zadrozny's (1994) argument that any semantics can be represented compositionally. The argument is based upon Zadrozny's theorem that every meaning function m can be encoded by a function μsuch that (i) for any expression E of a specified language L, m(E) can be recovered from μ(E), and (ii) μis a homomorphism from the syntactic structures of L to interpretations of L. In both cases, the primary motivation for the objections brought against Zadrozny's argument is the view that his encoding of the original meaning function does not properly reflect the synonymy relations posited for the language. In this paper, we argue that these technical criticisms do not go through. In particular, we prove that μproperly encodes synonymy relations, i.e. if two expressions are synonymous, then their compositional meanings are identical. This corrects some misconceptions about the function μ, e.g. Janssen (1997). We suggest that the reason that semanticists have been anxious to preserve compositionality as a significant constraint on semantic theory is that it has been mistakenly regarded as a condition that must be satisfied by any theory that sustains a systematic connection between the meaning of an expression and the meanings of its parts. Recent developments in formal and computational semantics show that systematic theories of meanings need not be compositional.
A Real World Implementation of Answer Extraction
Venue: arXiv cs.CL 2000
Year: 2000

In this paper we describe ExtrAns, an answer extraction system. Answer extraction (AE) aims at retrieving those exact passages of a document that directly answer a given user question. AE is more ambitious than information retrieval and information extraction in that the retrieval results are phrases, not entire documents, and in that the queries may be arbitrarily specific. It is less ambitious than full-fledged question answering in that the answers are not generated from a knowledge base but looked up in the text of documents. The current version of ExtrAns is able to parse unedited Unix "man pages", and derive the logical form of their sentences. User queries are also translated into logical forms. A theorem prover then retrieves the relevant phrases, which are presented through selective highlighting in their context.
Stochastic Model Checking for Multimedia
Venue: arXiv cs.MM 2000
Year: 2000

Modern distributed systems include a class of applications in which non-functional requirements are important. In particular, these applications include multimedia facilities where real time constraints are crucial to their correct functioning. In order to specify such systems it is necessary to describe that events occur at times given by probability distributions and stochastic automata have emerged as a useful technique by which such systems can be specified and verified. However, stochastic descriptions are very general, in particular they allow the use of general probability distribution functions, and therefore their verification can be complex. In the last few years, model checking has emerged as a useful verification tool for large systems. In this paper we describe two model checking algorithms for stochastic automata. These algorithms consider how properties written in a simple probabilistic real-time logic can be checked against a given stochastic automaton.
Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees
Venue: arXiv cs.DC 2000
Year: 2000

In this paper, we present a fully-dynamic distributed algorithm for maintaining a minimum spanning tree on general graphs with positive real edge weights. The goal of a dynamic MST algorithm is to update efficiently the minimum spanning tree after dynamic changes like edge weight changes, rather than having to recompute it from scatch each time. The first part of the paper surveys various algorithms available today both in sequential and distributed environments to solve static MST problem. We also present some of the efficient sequential algorithms for computing dynamic MST like the Frederickson's algorithm and Eppstein's sparsification technique. Lastly we present our new sequential and distributed algorithms for dynamic MST problem. To our knowledge, this is the first of the distributed algorithms for computing dynamic MSTs.
Safe cooperative robot dynamics on graphs
Venue: arXiv cs.RO 2000
Year: 2000

This paper initiates the use of vector fields to design, optimize, and implement reactive schedules for safe cooperative robot patterns on planar graphs. We consider Automated Guided Vehicles (AGV's) operating upon a predefined network of pathways. In contrast to the case of locally Euclidean configuration spaces, regularization of collisions is no longer a local procedure, and issues concerning the global topology of configuration spaces must be addressed. The focus of the present inquiry is the achievement of safe, efficient, cooperative patterns in the simplest nontrivial example (a pair of robots on a Y-network) by means of a state-event heirarchical controller.
Materialized View Selection and Maintenance Using Multi-Query Optimization
Venue: arXiv cs.DB 2000
Year: 2000

Because the presence of views enhances query performance, materialized views are increasingly being supported by commercial database/data warehouse systems. Whenever the data warehouse is updated, the materialized views must also be updated. However, whereas the amount of data entering a warehouse, the query loads, and the need to obtain up-to-date responses are all increasing, the time window available for making the warehouse up-to-date is shrinking. These trends necessitate efficient techniques for the maintenance of materialized views. In this paper, we show how to find an efficient plan for maintenance of a {\em set} of views, by exploiting common subexpressions between different view maintenance expressions. These common subexpressions may be materialized temporarily during view maintenance. Our algorithms also choose subexpressions/indices to be materialized permanently (and maintained along with other materialized views), to speed up view maintenance. While there has been much work on view maintenance in the past, our novel contributions lie in exploiting a recently developed framework for multiquery optimization to efficiently find good view maintenance plans as above. In addition to faster view maintenance, our algorithms can also be used to efficiently select materialized views to speed up workloads containing queries.
TSIA: A Dataflow Model
Venue: arXiv cs.PL 2000
Year: 2000

The Task System and Item Architecture (TSIA) is a model for transparent application execution. In many real-world projects, a TSIA provides a simple application with a transparent reliable, distributed, heterogeneous, adaptive, dynamic, real-time, parallel, secure or other execution. TSIA is suitable for many applications, not just for the simple applications served to date. This presentation shows that TSIA is a dataflow model - a long-standing model for transparent parallel execution. The advances to the dataflow model include a simple semantics, as well as support for input/output, for modifiable items and for other such effects.
Automatic Belief Revision in SNePS
Venue: arXiv cs.AI 2000
Year: 2000

SNePS is a logic- and network- based knowledge representation, reasoning, and acting system, based on a monotonic, paraconsistent, first-order term logic, with compositional intensional semantics. It has an ATMS-style facility for belief contraction, and an acting component, including a well-defined syntax and semantics for primitive and composite acts, as well as for ``rules'' that allow for acting in support of reasoning and reasoning in support of acting. SNePS has been designed to support natural language competent cognitive agents. When the current version of SNePS detects an explicit contradiction, it interacts with the user, providing information that helps the user decide what to remove from the knowledge base in order to remove the contradiction. The forthcoming SNePS 2.6 will also do automatic belief contraction if the information in the knowledge base warrents it.
The lexicographic closure as a revision process
Venue: arXiv cs.AI 2000
Year: 2000

The connections between nonmonotonic reasoning and belief revision are well-known. A central problem in the area of nonmonotonic reasoning is the problem of default entailment, i.e., when should an item of default information representing "if A is true then, normally, B is true" be said to follow from a given set of items of such information. Many answers to this question have been proposed but, surprisingly, virtually none have attempted any explicit connection to belief revision. The aim of this paper is to give an example of how such a connection can be made by showing how the lexicographic closure of a set of defaults may be conceptualised as a process of iterated revision by sets of sentences. Specifically we use the revision process of Nayak.
Probabilistic Default Reasoning with Conditional Constraints
Venue: arXiv cs.AI 2000
Year: 2000

We propose a combination of probabilistic reasoning from conditional constraints with approaches to default reasoning from conditional knowledge bases. In detail, we generalize the notions of Pearl's entailment in system Z, Lehmann's lexicographic entailment, and Geffner's conditional entailment to conditional constraints. We give some examples that show that the new notions of z-, lexicographic, and conditional entailment have similar properties like their classical counterparts. Moreover, we show that the new notions of z-, lexicographic, and conditional entailment are proper generalizations of both their classical counterparts and the classical notion of logical entailment for conditional constraints.
Fuzzy Approaches to Abductive Inference
Venue: arXiv cs.AI 2000
Year: 2000

This paper proposes two kinds of fuzzy abductive inference in the framework of fuzzy rule base. The abductive inference processes described here depend on the semantic of the rule. We distinguish two classes of interpretation of a fuzzy rule, certainty generation rules and possible generation rules. In this paper we present the architecture of abductive inference in the first class of interpretation. We give two kinds of problem that we can resolve by using the proposed models of inference.
On the tractable counting of theory models and its application to belief revision and truth maintenance
Venue: arXiv cs.AI 2000
Year: 2000

We introduced decomposable negation normal form (DNNF) recently as a tractable form of propositional theories, and provided a number of powerful logical operations that can be performed on it in polynomial time. We also presented an algorithm for compiling any conjunctive normal form (CNF) into DNNF and provided a structure-based guarantee on its space and time complexity. We present in this paper a linear-time algorithm for converting an ordered binary decision diagram (OBDD) representation of a propositional theory into an equivalent DNNF, showing that DNNFs scale as well as OBDDs. We also identify a subclass of DNNF which we call deterministic DNNF, d-DNNF, and show that the previous complexity guarantees on compiling DNNF continue to hold for this stricter subclass, which has stronger properties. In particular, we present a new operation on d-DNNF which allows us to count its models under the assertion, retraction and flipping of every literal by traversing the d-DNNF twice. That is, after such traversal, we can test in constant-time: the entailment of any literal by the d-DNNF, and the consistency of the d-DNNF under the retraction or flipping of any literal. We demonstrate the significance of these new operations by showing how they allow us to implement linear-time, complete truth maintenance systems and linear-time, complete belief revision systems for two important classes of propositional theories.
Linear Tabulated Resolution Based on Prolog Control Strategy
Venue: arXiv cs.AI 2000
Year: 2000

Infinite loops and redundant computations are long recognized open problems in Prolog. Two ways have been explored to resolve these problems: loop checking and tabling. Loop checking can cut infinite loops, but it cannot be both sound and complete even for function-free logic programs. Tabling seems to be an effective way to resolve infinite loops and redundant computations. However, existing tabulated resolutions, such as OLDT-resolution, SLG- resolution, and Tabulated SLS-resolution, are non-linear because they rely on the solution-lookup mode in formulating tabling. The principal disadvantage of non-linear resolutions is that they cannot be implemented using a simple stack-based memory structure like that in Prolog. Moreover, some strictly sequential operators such as cuts may not be handled as easily as in Prolog. In this paper, we propose a hybrid method to resolve infinite loops and redundant computations. We combine the ideas of loop checking and tabling to establish a linear tabulated resolution called TP-resolution. TP-resolution has two distinctive features: (1) It makes linear tabulated derivations in the same way as Prolog except that infinite loops are broken and redundant computations are reduced. It handles cuts as effectively as Prolog. (2) It is sound and complete for positive logic programs with the bounded-term-size property. The underlying algorithm can be implemented by an extension to any existing Prolog abstract machines such as WAM or ATOAM.
BDD-based reasoning in the fluent calculus - first results
Venue: arXiv cs.AI 2000
Year: 2000

The paper reports on first preliminary results and insights gained in a project aiming at implementing the fluent calculus using methods and techniques based on binary decision diagrams. After reporting on an initial experiment showing promising results we discuss our findings concerning various techniques and heuristics used to speed up the reasoning process.
PAL: Pertinence Action Language
Venue: arXiv cs.AI 2000
Year: 2000

The current document contains a brief description of a system for Reasoning about Actions and Change called PAL (Pertinence Action Language) which makes use of several reasoning properties extracted from a Temporal Expert Systems tool called Medtool.
Local Diagnosis
Venue: arXiv cs.AI 2000
Year: 2000

In an earlier work, we have presented operations of belief change which only affect the relevant part of a belief base. In this paper, we propose the application of the same strategy to the problem of model-based diangosis. We first isolate the subset of the system description which is relevant for a given observation and then solve the diagnosis problem for this subset.
A note on knowledge-based programs and specifications
Venue: arXiv cs.DC 2000
Year: 2000

Knowledge-based program are programs with explicit tests for knowledge. They have been used successfully in a number of applications. Sanders has pointed out what seem to be a counterintuitive property of knowledge-based programs. Roughly speaking, they do not satisfy a certain monotonicity property, while standard programs (ones without tests for knowledge) do. It is shown that there are two ways of defining the monotonicity property, which agree for standard programs. Knowledge-based programs satisfy the first, but do not satisfy the second. It is further argued by example that the fact that they do not satisfy the second is actually a feature, not a problem. Moreover, once we allow the more general class of knowledge-based specifications, standard programs do not satisfy the monotonicity property either.
Differential Invariants under Gamma Correction
Venue: arXiv cs.CV 2000
Year: 2000

This paper presents invariants under gamma correction and similarity transformations. The invariants are local features based on differentials which are implemented using derivatives of the Gaussian. The use of the proposed invariant representation is shown to yield improved correlation results in a template matching scenario.
Programming in Alma-0, or Imperative and Declarative Programming Reconciled
Venue: arXiv cs.LO 2000
Year: 2000

In (Apt et al, TOPLAS 1998) we introduced the imperative programming language Alma-0 that supports declarative programming. In this paper we illustrate the hybrid programming style of Alma-0 by means of various examples that complement those presented in (Apt et al, TOPLAS 1998). The presented Alma-0 programs illustrate the versatility of the language and show that ``don't know'' nondeterminism can be naturally combined with assignment.
Mathematical Software: Past, Present, and Future
Venue: arXiv cs.MS 2000
Year: 2000

This paper provides some reflections on the field of mathematical software on the occasion of John Rice's 65th birthday. I describe some of the common themes of research in this field and recall some significant events in its evolution. Finally, I raise a number of issues that are of concern to future developments.
On Redundancy Elimination Tolerant Scheduling Rules
Venue: arXiv cs.PL 2000
Year: 2000

In (Ferrucci, Pacini and Sessa, 1995) an extended form of resolution, called Reduced SLD resolution (RSLD), is introduced. In essence, an RSLD derivation is an SLD derivation such that redundancy elimination from resolvents is performed after each rewriting step. It is intuitive that redundancy elimination may have positive effects on derivation process. However, undesiderable effects are also possible. In particular, as shown in this paper, program termination as well as completeness of loop checking mechanisms via a given selection rule may be lost. The study of such effects has led us to an analysis of selection rule basic concepts, so that we have found convenient to move the attention from rules of atom selection to rules of atom scheduling. A priority mechanism for atom scheduling is built, where a priority is assigned to each atom in a resolvent, and primary importance is given to the event of arrival of new atoms from the body of the applied clause at rewriting time. This new computational model proves able to address the study of redundancy elimination effects, giving at the same time interesting insights into general properties of selection rules. As a matter of fact, a class of scheduling rules, namely the specialisation independent ones, is defined in the paper by using not trivial semantic arguments. As a quite surprising result, specialisation independent scheduling rules turn out to coincide with a class of rules which have an immediate structural characterisation (named stack-queue rules). Then we prove that such scheduling rules are tolerant to redundancy elimination, in the sense that neither program termination nor completeness of equality loop check is lost passing from SLD to RSLD.
Task Frames
Venue: arXiv cs.PL 2000
Year: 2000

Forty years ago Dijkstra introduced the current conventional execution of routines. It places activation frames onto a stack. Each frame is the internal state of an executing routine. The resulting application execution is not easily helped by an external system. This presentation proposes an alternative execution of routines. It places task frames onto the stack. A task frame is the call of a routine to be executed. The feasibility of the alternative execution is demonstrated by a crude implementation. As described elsewhere, an application which executes in terms of tasks can be provided by an external system with a transparent reliable, distributed, heterogeneous, adaptive, dynamic, real-time, parallel, secure or other execution. By extending the crude implementation, this presentation outlines a simple transparent parallel execution.