OpenRaiser/Intern-Atlas huggingface dataset:
Object-Oriented Design of Graph Oriented Data Structures
Venue: arXiv cs.SE 1998
Year: 1998

Applied research in graph algorithms and combinatorial structures needs comprehensive and versatile software libraries. However, the design and the implementation of flexible libraries are challenging activities. Among the other problems involved in such a difficult field, a very special role is played by graph classification issues. We propose new techniques devised to help the designer and the programmer in the development activities. Such techniques are especially suited for dealing with graph classification problems and rely on an extension of the usual object-oriented paradigm. In order to support the usage of our approach, we devised an extension of the C++ programming language and implemented the corresponding pre-compiler.
Resources for Evaluation of Summarization Techniques
Venue: arXiv cs.CL 1998
Year: 1998

We report on two corpora to be used in the evaluation of component systems for the tasks of (1) linear segmentation of text and (2) summary-directed sentence extraction. We present characteristics of the corpora, methods used in the collection of user judgments, and an overview of the application of the corpora to evaluating the component system. Finally, we discuss the problems and issues with construction of the test set which apply broadly to the construction of evaluation resources for language technologies.
Equivalence is in the Eye of the Beholder
Venue: arXiv cs.SE 1998
Year: 1998

In a recent provocative paper, Lamport points out "the insubstantiality of processes" by proving the equivalence of two different decompositions of the same intuitive algorithm by means of temporal formulas. We point out that the correct equivalence of algorithms is itself in the eye of the beholder. We discuss a number of related issues and, in particular, whether algorithms can be proved equivalent directly.
Evolving Algebras and Partial Evaluation
Venue: arXiv cs.SE 1998
Year: 1998

We describe an automated partial evaluator for evolving algebras implemented at the University of Michigan.
The Railroad Crossing Problem: An Experiment with Instantaneous Actions and Immediate Reactions
Venue: arXiv cs.SE 1998
Year: 1998

We give an evolving algebra solution for the well-known railroad crossing problem and use the occasion to experiment with agents that perform instantaneous actions in continuous time and in particular with agents that fire at the moment they are enabled.
TCP Trunking
Venue: arXiv cs.NI 1998
Year: 1998

A TCP trunk is an IP tunnel under TCP control, capable of carrying packets from any number of user flows. By exploiting properties of TCP, a TCP trunk provides elastic and reliable transmission over a network, and automatically shares the network fairly with other competing trunks. Moreover, by aggregating user flows into a single trunk flow, TCP trunking can significantly reduce the number of flows that the network needs to manage, thereby allowing use of simplified management to achieve improved perfor mance. For example, when dealing with only a small number of TCP trunk flows, a router with a simple FIFO buffer can experience low packet loss rates. A TCP trunk is a "soft" circuit in the sense that it requires no flow states to be maintained inside the network. Setting up a TCP trunk involves only configuring the two end nodes. This is in contrast with traditional methods of configuring circuits via signaling of network nodes. A simple packet-dropping mechanism based on packet accounting at the transmitter of a TCP trunk assures that, when the trunk reduces its bandwidth in response to network congestion, user TCP flows carried by the trunk will reduce their bandwidths by the same proportion. Simu lation results have demonstrated that TCP trunks can provide improved network performance to users, while achieving high network utilization.
Text-To-Speech Conversion with Neural Networks: A Recurrent TDNN Approach
Venue: arXiv cs.NE 1998
Year: 1998

This paper describes the design of a neural network that performs the phonetic-to-acoustic mapping in a speech synthesis system. The use of a time-domain neural network architecture limits discontinuities that occur at phone boundaries. Recurrent data input also helps smooth the output parameter tracks. Independent testing has demonstrated that the voice quality produced by this system compares favorably with speech from existing commercial text-to-speech systems.
Neural Network Methods for Boundary Value Problems Defined in Arbitrarily Shaped Domains
Venue: arXiv cs.NE 1998
Year: 1998

Partial differential equations (PDEs) with Dirichlet boundary conditions defined on boundaries with simple geometry have been succesfuly treated using sigmoidal multilayer perceptrons in previous works. This article deals with the case of complex boundary geometry, where the boundary is determined by a number of points that belong to it and are closely located, so as to offer a reasonable representation. Two networks are employed: a multilayer perceptron and a radial basis function network. The later is used to account for the satisfaction of the boundary conditions. The method has been successfuly tested on two-dimensional and three-dimensional PDEs and has yielded accurate solutions.
Name Strategy: Its Existence and Implications
Venue: arXiv cs.CL 1998
Year: 1998

It is argued that colour name strategy, object name strategy, and chunking strategy in memory are all aspects of the same general phenomena, called stereotyping. It is pointed out that the Berlin-Kay universal partial ordering of colours and the frequency of traffic accidents classified by colour are surprisingly similar. Some consequences of the existence of a name strategy for the philosophy of language and mathematics are discussed. It is argued that real valued quantities occur {\it ab initio}. The implication of real valued truth quantities is that the {\bf Continuum Hypothesis} of pure mathematics is side-stepped. The existence of name strategy shows that thought/sememes and talk/phonemes can be separate, and this vindicates the assumption of thought occurring before talk used in psycholinguistic speech production models.
Vocal Access to a Newspaper Archive: Design Issues and Preliminary Investigation
Venue: arXiv cs.DL 1998
Year: 1998

This paper presents the design and the current prototype implementation of an interactive vocal Information Retrieval system that can be used to access articles of a large newspaper archive using a telephone. The results of preliminary investigation into the feasibility of such a system are also presented.
Adaptive Interaction Using the Adaptive Agent Oriented Software Architecture (AAOSA)
Venue: arXiv cs.HC 1998
Year: 1998

User interfaces that adapt their characteristics to those of the user are referred to as adaptive interfaces. We propose Adaptive Agent Oriented Software Architecture (AAOSA) as a new way of designing adaptive interfaces. AAOSA is a new approach to software design based on an agent-oriented architecture. In this approach agents are considered adaptively communicating concurrent modules which are divided into a white box module responsible for the communications and learning, and a black box which is responsible for the independent specialized processes of the agent. A distributed learning policy that makes use of this architecture is used for purposes of system adaptability.
A reusable iterative optimization software library to solve combinatorial problems with approximate reasoning
Venue: arXiv cs.AI 1998
Year: 1998

Real world combinatorial optimization problems such as scheduling are typically too complex to solve with exact methods. Additionally, the problems often have to observe vaguely specified constraints of different importance, the available data may be uncertain, and compromises between antagonistic criteria may be necessary. We present a combination of approximate reasoning based constraints and iterative optimization based heuristics that help to model and solve such problems in a framework of C++ software libraries called StarFLIP++. While initially developed to schedule continuous caster units in steel plants, we present in this paper results from reusing the library components in a shift scheduling system for the workforce of an industrial production plant.
A Flexible Shallow Approach to Text Generation
Venue: arXiv cs.CL 1998
Year: 1998

In order to support the efficient development of NL generation systems, two orthogonal methods are currently pursued with emphasis: (1) reusable, general, and linguistically motivated surface realization components, and (2) simple, task-oriented template-based techniques. In this paper we argue that, from an application-oriented perspective, the benefits of both are still limited. In order to improve this situation, we suggest and evaluate shallow generation methods associated with increased flexibility. We advise a close connection between domain-motivated and linguistic ontologies that supports the quick adaptation to new tasks and domains, rather than the reuse of general resources. Our method is especially designed for generating reports with limited linguistic variations.
Regression Depth and Center Points
Venue: arXiv cs.CG 1999
Year: 1999

We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.
TDLeaf(lambda): Combining Temporal Difference Learning with Game-Tree Search
Venue: arXiv cs.LG 1999
Year: 1999

In this paper we present TDLeaf(lambda), a variation on the TD(lambda) algorithm that enables it to be used in conjunction with minimax search. We present some experiments in both chess and backgammon which demonstrate its utility and provide comparisons with TD(lambda) and another less radical variant, TD-directed(lambda). In particular, our chess program, ``KnightCap,'' used TDLeaf(lambda) to learn its evaluation function while playing on the Free Internet Chess Server (FICS, fics.onenet.net). It improved from a 1650 rating to a 2100 rating in just 308 games. We discuss some of the reasons for this success and the relationship between our results and Tesauro's results in backgammon.
On the geometry of similarity search: dimensionality curse and concentration of measure
Venue: arXiv cs.IR 1999
Year: 1999

We suggest that the curse of dimensionality affecting the similarity-based search in large datasets is a manifestation of the phenomenon of concentration of measure on high-dimensional structures. We prove that, under certain geometric assumptions on the query domain $Ω$ and the dataset $X$, if $Ω$ satisfies the so-called concentration property, then for most query points $x^\ast$ the ball of radius $(1+\e)d_X(x^\ast)$ centred at $x^\ast$ contains either all points of $X$ or else at least $C_1\exp(-C_2\e^2n)$ of them. Here $d_X(x^\ast)$ is the distance from $x^\ast$ to the nearest neighbour in $X$ and $n$ is the dimension of $Ω$.
Fast Computational Algorithms for the Discrete Wavelet Transform and Applications of Localized Orthonormal Bases in Signal Classification
Venue: arXiv cs.MS 1999
Year: 1999

We construct an algorithm for implementing the discrete wavelet transform by means of matrices in SO_2(R) for orthonormal compactly supported wavelets and matrices in SL_m(R), m > = 2, for compactly supported biorthogonal wavelets. We show that in 1 dimension the total operation count using this algorithm can be reduced to about 50% of the conventional convolution and downsampling by 2-operation for both orthonormal and biorthogonal filters. In the special case of biorthogonal symmetric odd-odd filters, we show an implementation yielding a total operation count of about 38% of the conventional method. In 2 dimensions we show an implementation of this algorithm yielding a reduction in the total operation count of about 70% when the filters are orthonormal, a reduction of about 62% for general biorthogonal filters, and a reduction of about 70% if the filters are symmetric odd-odd length filters. We further extend these results to 3 dimensions. We also show how the SO_2(R)-method for implementing the discrete wavelet transform may be exploited to compute short FIR filters, and we construct edge mappings where we try to improve upon the degree of preservation of regularity in the conventional methods. We also consider a two-class waveform discrimination problem. A statistical space-frequency analysis is performed on a training data set using the LDB-algorithm of N.Saito and R.Coifman. The success of the algorithm on this particular problem is evaluated on a disjoint test data set.
Competition and cooperation: Libraries and publishers in the transition to electronic scholarly journals
Venue: arXiv cs.DL 1999
Year: 1999

The conversion of scholarly journals to digital format is proceeding rapidly, especially for those from large commercial and learned society publishers. This conversion offers the best hope for survival for such publishers. The infamous "journal crisis" is more of a library cost crisis than a publisher pricing problem, with internal library costs much higher than the amount spent on purchasing books and journals. Therefore publishers may be able to retain or even increase their revenues and profits, while at the same time providing a superior service. To do this, they will have to take over many of the function of libraries, and they can do that only in the digital domain. This paper examines publishers' strategies, how they are likely to evolve, and how they will affect libraries.
Extremal problems in logic programming and stable model computation
Venue: arXiv cs.LO 1999
Year: 1999

We study the following problem: given a class of logic programs C, determine the maximum number of stable models of a program from C. We establish the maximum for the class of all logic programs with at most n clauses, and for the class of all logic programs of size at most n. We also characterize the programs for which the maxima are attained. We obtain similar results for the class of all disjunctive logic programs with at most n clauses, each of length at most m, and for the class of all disjunctive logic programs of size at most n. Our results on logic programs have direct implication for the design of algorithms to compute stable models. Several such algorithms, similar in spirit to the Davis-Putnam procedure, are described in the paper. Our results imply that there is an algorithm that finds all stable models of a program with n clauses after considering the search space of size O(3^{n/3}) in the worst case. Our results also provide some insights into the question of representability of families of sets as families of stable models of logic programs.
PSPACE has 2-round quantum interactive proof systems
Venue: arXiv cs.CC 1999
Year: 1999

In this paper we consider quantum interactive proof systems, i.e., interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that every language in PSPACE has a quantum interactive proof system that requires only two rounds of communication between the prover and verifier, while having exponentially small (one-sided) probability of error. It follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level.
Mutual Search
Venue: arXiv cs.DS 1999
Year: 1999

We introduce a search problem called ``mutual search'' where $k$ \agents, arbitrarily distributed over $n$ sites, are required to locate one another by posing queries of the form ``Anybody at site $i$?''. We ask for the least number of queries that is necessary and sufficient. For the case of two \agents using deterministic protocols we obtain the following worst-case results: In an oblivious setting (where all pre-planned queries are executed) there is no savings: $n-1$ queries are required and are sufficient. In a nonoblivious setting we can exploit the paradigm of ``no news is also news'' to obtain significant savings: in the synchronous case $0.586n$ queries suffice and $0.536n$ queries are required; in the asynchronous case $0.896n$ queries suffice and a fortiori 0.536 queries are required; for $o(\sqrt{n})$ \agents using a deterministic protocol less than $n$ queries suffice; there is a simple randomized protocol for two \agents with worst-case expected $0.5n$ queries and all randomized protocols require at least $0.125n$ worst-case expected queries. The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest.
Quality of OCR for Degraded Text Images
Venue: arXiv cs.DL 1999
Year: 1999

Commercial OCR packages work best with high-quality scanned images. They often produce poor results when the image is degraded, either because the original itself was poor quality, or because of excessive photocopying. The ability to predict the word failure rate of OCR from a statistical analysis of the image can help in making decisions in the trade-off between the success rate of OCR and the cost of human correction of errors. This paper describes an investigation of OCR of degraded text images using a standard OCR engine (Adobe Capture). The documents were selected from those in the archive at Los Alamos National Laboratory. By introducing noise in a controlled manner into perfect documents, we show how the quality of OCR can be predicted from the nature of the noise. The preliminary results show that a simple noise model can give good prediction of the number of OCR errors.
Use and usability in a digital library search system
Venue: arXiv cs.DL 1999
Year: 1999

Digital libraries must reach out to users from all walks of life, serving information needs at all levels. To do this, they must attain high standards of usability over an extremely broad audience. This paper details the evolution of one important digital library component as it has grown in functionality and usefulness over several years of use by a live, unrestricted community. Central to its evolution have been user studies, analysis of use patterns, and formative usability evaluation. We extrapolate that all three components are necessary in the production of successful digital library systems.
Multimodal Surrogates for Video Browsing
Venue: arXiv cs.DL 1999
Year: 1999

Three types of video surrogates - visual (keyframes), verbal (keywords/phrases), and combination of the two - were designed and studied in a qualitative investigation of user cognitive processes. The results favor the combined surrogates in which verbal information and images reinforce each other, lead to better comprehension, and may actually require less processing time. The results also highlight image features users found most helpful. These findings will inform the interface design and video representation for video retrieval and browsing.
Algorithms of Two-Level Parallelization for DSMC of Unsteady Flows in Molecular Gasdynamics
Venue: arXiv cs.CE 1999
Year: 1999

The general scheme of two-level parallelization (TLP) for direct simulation Monte Carlo of unsteady gas flows on shared memory multiprocessor computers has been described. The high efficient algorithm of parallel independent runs is used on the first level. The data parallelization is employed for the second one. Two versions of TLP algorithm are elaborated with static and dynamic load balancing. The method of dynamic processor reallocation is used for dynamic load balancing. Two gasdynamic unsteady problems were used to study speedup and efficiency of the algorithms. The conditions of efficient application field for the algorithms have been determined.
The "Fodor"-FODOR fallacy bites back
Venue: arXiv cs.CL 1999
Year: 1999

The paper argues that Fodor and Lepore are misguided in their attack on Pustejovsky's Generative Lexicon, largely because their argument rests on a traditional, but implausible and discredited, view of the lexicon on which it is effectively empty of content, a view that stands in the long line of explaining word meaning (a) by ostension and then (b) explaining it by means of a vacuous symbol in a lexicon, often the word itself after typographic transmogrification. (a) and (b) both share the wrong belief that to a word must correspond a simple entity that is its meaning. I then turn to the semantic rules that Pustejovsky uses and argue first that, although they have novel features, they are in a well-established Artificial Intelligence tradition of explaining meaning by reference to structures that mention other structures assigned to words that may occur in close proximity to the first. It is argued that Fodor and Lepore's view that there cannot be such rules is without foundation, and indeed systems using such rules have proved their practical worth in computational systems. Their justification descends from line of argument, whose high points were probably Wittgenstein and Quine that meaning is not to be understood by simple links to the world, ostensive or otherwise, but by the relationship of whole cultural representational structures to each other and to the world as a whole.
Empirically Evaluating an Adaptable Spoken Dialogue System
Venue: arXiv cs.CL 1999
Year: 1999

Recent technological advances have made it possible to build real-time, interactive spoken dialogue systems for a wide variety of applications. However, when users do not respect the limitations of such systems, performance typically degrades. Although users differ with respect to their knowledge of system limitations, and although different dialogue strategies make system limitations more apparent to users, most current systems do not try to improve performance by adapting dialogue behavior to individual users. This paper presents an empirical evaluation of TOOT, an adaptable spoken dialogue system for retrieving train schedules on the web. We conduct an experiment in which 20 users carry out 4 tasks with both adaptable and non-adaptable versions of TOOT, resulting in a corpus of 80 dialogues. The values for a wide range of evaluation measures are then extracted from this corpus. Our results show that adaptable TOOT generally outperforms non-adaptable TOOT, and that the utility of adaptation depends on TOOT's initial dialogue strategies.
LuaJava - A Scripting Tool for Java
Venue: arXiv cs.SE 1999
Year: 1999

Scripting languages are becoming more and more important as a tool for software development, as they provide great flexibility for rapid prototyping and for configuring componentware applications. In this paper we present LuaJava, a scripting tool for Java. LuaJava adopts Lua, a dynamically typed interpreted language, as its script language. Great emphasis is given to the transparency of the integration between the two languages, so that objects from one language can be used inside the other like native objects. The final result of this integration is a tool that allows the construction of configurable Java applications, using off-the-shelf components, in a high abstraction level.