OpenRaiser/Intern-Atlas huggingface dataset:
A Lexicalized Tree Adjoining Grammar for English
Venue: arXiv cs.CL 1998
Year: 1998

This document describes a sizable grammar of English written in the TAG formalism and implemented for use with the XTAG system. This report and the grammar described herein supersedes the TAG grammar described in an earlier 1995 XTAG technical report. The English grammar described in this report is based on the TAG formalism which has been extended to include lexicalization, and unification-based feature structures. The range of syntactic phenomena that can be handled is large and includes auxiliaries (including inversion), copula, raising and small clause constructions, topicalization, relative clauses, infinitives, gerunds, passives, adjuncts, it-clefts, wh-clefts, PRO constructions, noun-noun modifications, extraposition, determiner sequences, genitives, negation, noun-verb contractions, sentential adjuncts and imperatives. This technical report corresponds to the XTAG Release 8/31/98. The XTAG grammar is continuously updated with the addition of new analyses and modification of old ones, and an online version of this report can be found at the XTAG web page at http://www.cis.upenn.edu/~xtag/
Incremental Parser Generation for Tree Adjoining Grammars
Venue: arXiv cs.CL 1998
Year: 1998

This paper describes the incremental generation of parse tables for the LR-type parsing of Tree Adjoining Languages (TALs). The algorithm presented handles modifications to the input grammar by updating the parser generated so far. In this paper, a lazy generation of LR-type parsers for TALs is defined in which parse tables are created by need while parsing. We then describe an incremental parser generator for TALs which responds to modification of the input grammar by updating parse tables built so far.
Stable models and an alternative logic programming paradigm
Venue: arXiv cs.LO 1998
Year: 1998

In this paper we reexamine the place and role of stable model semantics in logic programming and contrast it with a least Herbrand model approach to Horn programs. We demonstrate that inherent features of stable model semantics naturally lead to a logic programming system that offers an interesting alternative to more traditional logic programming styles of Horn logic programming, stratified logic programming and logic programming with well-founded semantics. The proposed approach is based on the interpretation of program clauses as constraints. In this setting programs do not describe a single intended model, but a family of stable models. These stable models encode solutions to the constraint satisfaction problem described by the program. Our approach imposes restrictions on the syntax of logic programs. In particular, function symbols are eliminated from the language. We argue that the resulting logic programming system is well-attuned to problems in the class NP, has a well-defined domain of applications, and an emerging methodology of programming. We point out that what makes the whole approach viable is recent progress in implementations of algorithms to compute stable models of propositional logic programs.
Separation-Sensitive Collision Detection for Convex Objects
Venue: arXiv cs.CG 1998
Year: 1998

We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during their motion. For two convex polygons in the plane, let $D$ be the maximum diameter of the polygons, and let $s$ be the minimum distance between them during their motion. Our separation certificate changes $O(\log(D/s))$ times when the relative motion of the two polygons is a translation along a straight line or convex curve, $O(\sqrt{D/s})$ for translation along an algebraic trajectory, and $O(D/s)$ for algebraic rigid motion (translation and rotation). Each certificate update is performed in $O(\log(D/s))$ time. Variants of these data structures are also shown that exhibit \emph{hysteresis}---after a separation certificate fails, the new certificate cannot fail again until the objects have moved by some constant fraction of their current separation. We can then bound the number of events by the combinatorial size of a certain cover of the motion path by balls.
Fairness for ABR multipoint-to-point connections
Venue: arXiv cs.NI 1998
Year: 1998

In multipoint-to-point connections, the traffic at the root (destination) is the combination of all traffic originating at the leaves. A crucial concern in the case of multiple senders is how to define fairness within a multicast group and among groups and point-to-point connections. Fairness definition can be complicated since the multipoint connection can have the same identifier (VPI/VCI) on each link, and senders might not be distinguishable in this case. Many rate allocation algorithms implicitly assume that there is only one sender in each VC, which does not hold for multipoint-to-point cases. We give various possibilities for defining fairness for multipoint connections, and show the tradeoffs involved. In addition, we show that ATM bandwidth allocation algorithms need to be adapted to give fair allocations for multipoint-to-point connections.
Feedback Consolidation Algorithms for ABR Point-to-Multipoint Connections in ATM Networks
Venue: arXiv cs.NI 1998
Year: 1998

ABR traffic management for point-to-multipoint connections controls the source rate to the minimum rate supported by all the branches of the multicast tree. A number of algorithms have been developed for extending ABR congestion avoidance algorithms to perform feedback consolidation at the branch points. This paper discusses various design options and implementation alternatives for the consolidation algorithms, and proposes a number of new algorithms. The performance of the proposed algorithms and the previous algorithms is compared under a variety of conditions. Results indicate that the algorithms we propose eliminate the consolidation noise (caused if the feedback is returned before all branches respond), while exhibiting a fast transient response.
Performance of TCP over ABR on ATM backbone and with various VBR traffic patterns
Venue: arXiv cs.NI 1998
Year: 1998

We extend our earlier studies of buffer requirements of TCP over ABR in two directions. First, we study the performance of TCP over ABR in an ATM backbone. On the backbone, the TCP queues are at the edge router and not inside the ATM network. The router requires buffer equal to the sum of the receiver window sizes of the participating TCP connections. Second, we introduce various patterns of VBR background traffic. The VBR background introduces variance in the ABR capacity and the TCP traffic introduces variance in the ABR demand. Some simple switch schemes are unable to keep up with the combined effect of highly varying demands and highly varying ABR capacity. We present our experiences with refining the ERICA+ switch scheme to handle these conditions.
Congestion Control and Traffic Management in ATM Networks: Recent Advances and A Survey
Venue: arXiv cs.NI 1998
Year: 1998

Congestion control mechanisms for ATM networks as selected by the ATM Forum traffic management group are described. Reasons behind these selections are explained. In particular, selection criteria for selection between rate-based and credit-based approach and the key points of the debate between the two approaches are presented. The approach that was finally selected and several other schemes that were considered are described.
Characteristics of Destination Address Locality in Computer Networks: A Comparison of Caching Schemes
Venue: arXiv cs.NI 1998
Year: 1998

The size of computer networks, along with their bandwidths, is growing exponentially. To support these large, high-speed networks, it is neccessary to be able to forward packets in a few microseconds. One part of the forwarding operation consists of searching through a large address databse. This problem is encountered in the design of bridges, routers, gateways and name servers. Caching can reduce the lookup time if there is a locality in the address reference pattern. Using a destination reference trace measured on an extended local are a network, we attempt to see if the destination refernces do have a significant locality. We compared the performance of MIN, LRU, FIFO, and random cache replacement algorithms. We found that the interactive (terminal) traffic in our sample had quite different locality behavior than that of the noninteractive traffic. The interactive traffic did not follow the LRU stack model while the noninteractivetraffic did. Examples are shown of the environments in which caching can help as well as those in which caching can hurt, unless the cache size is large.
Analysis of Performance of Dynamic Multicast Routing Algorithms
Venue: arXiv cs.NI 1998
Year: 1998

In this paper, three new dynamic multicast routing algorithms based on the greedy tree technique are proposed; Source Optimised Tree, Topology Based Tree and Minimum Diameter Tree. A simulation analysis is presented showing various performance aspects of the algorithms, in which a comparison is made with the greedy and core based tree techniques. The effects of the tree source location on dynamic membership change are also examined. The simulations demonstrate that the Source Optimised Tree algorithm achieves a significant improvement in terms of delay and link usage when compared to the Core Based Tree, and greedy algorithm.
A Natural Deduction style proof system for propositional $μ$-calculus and its formalization in inductive type theories
Venue: arXiv cs.LO 1998
Year: 1998

In this paper, we present a formalization of Kozen's propositional modal $μ$-calculus, in the Calculus of Inductive Constructions. We address several problematic issues, such as the use of higher-order abstract syntax in inductive sets in presence of recursive constructors, the encoding of modal (``proof'') rules and of context sensitive grammars. The encoding can be used in the \Coq system, providing an experimental computer-aided proof environment for the interactive development of error-free proofs in the $μ$-calculus. The techniques we adopted can be readily ported to other languages and proof systems featuring similar problematic issues.
The Tiny Tera: A Packet Switch Core
Venue: arXiv cs.NI 1998
Year: 1998

The objective is to design and build a small, high-bandwidth switch.
C++ Templates as Partial Evaluation
Venue: arXiv cs.PL 1998
Year: 1998

This paper explores the relationship between C++ templates and partial evaluation. Templates were designed to support generic programming, but unintentionally provided the ability to perform compile-time computations and code generation. These features are completely accidental, and as a result their syntax is awkward. By recasting these features in terms of partial evaluation, a much simpler syntax can be achieved. C++ may be regarded as a two-level language in which types are first-class values. Template instantiation resembles an offline partial evaluator. This paper describes preliminary work toward a single mechanism based on Partial Evaluation which unifies generic programming, compile-time computation and code generation. The language Catat is introduced to illustrate these ideas.
Restrictions on Tree Adjoining Languages
Venue: arXiv cs.CL 1998
Year: 1998

Several methods are known for parsing languages generated by Tree Adjoining Grammars (TAGs) in O(n^6) worst case running time. In this paper we investigate which restrictions on TAGs and TAG derivations are needed in order to lower this O(n^6) time complexity, without introducing large runtime constants, and without losing any of the generative power needed to capture the syntactic constructions in natural language that can be handled by unrestricted TAGs. In particular, we describe an algorithm for parsing a strict subclass of TAG in O(n^5), and attempt to show that this subclass retains enough generative power to make it useful in the general case.
A Proof Theoretic View of Constraint Programming
Venue: arXiv cs.AI 1998
Year: 1998

We provide here a proof theoretic account of constraint programming that attempts to capture the essential ingredients of this programming style. We exemplify it by presenting proof rules for linear constraints over interval domains, and illustrate their use by analyzing the constraint propagation process for the {\tt SEND + MORE = MONEY} puzzle. We also show how this approach allows one to build new constraint solvers.
A Winnow-Based Approach to Context-Sensitive Spelling Correction
Venue: arXiv cs.LG 1998
Year: 1998

A large class of machine-learning problems in natural language require the characterization of linguistic context. Two characteristic properties of such problems are that their feature space is of very high dimensionality, and their target concepts refer to only a small subset of the features in the space. Under such conditions, multiplicative weight-update algorithms such as Winnow have been shown to have exceptionally good theoretical properties. We present an algorithm combining variants of Winnow and weighted-majority voting, and apply it to a problem in the aforementioned class: context-sensitive spelling correction. This is the task of fixing spelling errors that happen to result in valid words, such as substituting "to" for "too", "casual" for "causal", etc. We evaluate our algorithm, WinSpell, by comparing it against BaySpell, a statistics-based method representing the state of the art for this task. We find: (1) When run with a full (unpruned) set of features, WinSpell achieves accuracies significantly higher than BaySpell was able to achieve in either the pruned or unpruned condition; (2) When compared with other systems in the literature, WinSpell exhibits the highest performance; (3) The primary reason that WinSpell outperforms BaySpell is that WinSpell learns a better linear separator; (4) When run on a test set drawn from a different corpus than the training set was drawn from, WinSpell is better able than BaySpell to adapt, using a strategy we will present that combines supervised learning on the training set with unsupervised learning on the (noisy) test set.
Formulas as Programs
Venue: arXiv cs.LO 1998
Year: 1998

We provide here a computational interpretation of first-order logic based on a constructive interpretation of satisfiability w.r.t. a fixed but arbitrary interpretation. In this approach the formulas themselves are programs. This contrasts with the so-called formulas as types approach in which the proofs of the formulas are typed terms that can be taken as programs. This view of computing is inspired by logic programming and constraint logic programming but differs from them in a number of crucial aspects. Formulas as programs is argued to yield a realistic approach to programming that has been realized in the implemented programming language ALMA-0 (Apt et al.) that combines the advantages of imperative and logic programming. The work here reported can also be used to reason about the correctness of non-recursive ALMA-0 programs that do not include destructive assignment.
Automatic Hardware Synthesis for a Hybrid Reconfigurable CPU Featuring Philips CPLDs
Venue: arXiv cs.PL 1998
Year: 1998

A high-level architecture of a Hybrid Reconfigurable CPU, based on a Philips-supported core processor, is introduced. It features the Philips XPLA2 CPLD as a reconfigurable functional unit. A compilation chain is presented, in which automatic implementation of time-critical program segments in custom hardware is performed. The entire process is transparent from the programmer's point of view. The hardware synthesis module of the chain, which translates segments of assembly code into a hardware netlist, is discussed in details. Application examples are also presented.
Speech Synthesis with Neural Networks
Venue: arXiv cs.NE 1998
Year: 1998

Text-to-speech conversion has traditionally been performed either by concatenating short samples of speech or by using rule-based systems to convert a phonetic representation of speech into an acoustic representation, which is then converted into speech. This paper describes a system that uses a time-delay neural network (TDNN) to perform this phonetic-to-acoustic mapping, with another neural network to control the timing of the generated speech. The neural network system requires less memory than a concatenation system, and performed well in tests comparing it to commercial systems using other technologies.
Optimal Multi-Paragraph Text Segmentation by Dynamic Programming
Venue: arXiv cs.CL 1998
Year: 1998

There exist several methods of calculating a similarity curve, or a sequence of similarity values, representing the lexical cohesion of successive text constituents, e.g., paragraphs. Methods for deciding the locations of fragment boundaries are, however, scarce. We propose a fragmentation method based on dynamic programming. The method is theoretically sound and guaranteed to provide an optimal splitting on the basis of a similarity curve, a preferred fragment length, and a cost function defined. The method is especially useful when control on fragment size is of importance.
The Computing Research Repository: Promoting the Rapid Dissemination and Archiving of Computer Science Research
Venue: arXiv cs.DL 1998
Year: 1998

We describe the Computing Research Repository (CoRR), a new electronic archive for rapid dissemination and archiving of computer science research results. CoRR was initiated in September 1998 through the cooperation of ACM, LANL (Los Alamos National Laboratory) e-Print archive, and NCSTRL (Networked Computer Science Technical Research Library. Through its implementation of the Dienst protocol, CoRR combines the open and extensible architecture of NCSTRL with the reliable access and well-established management practices of the LANL XXX e-Print repository. This architecture will allow integration with other e-Print archives and provides a foundation for a future broad-based scholarly digital library. We describe the decisions that were made in creating CoRR, the architecture of the CoRR/NCSTRL interoperation, and issues that have arisen during the operation of CoRR.
An Empirical Approach to Temporal Reference Resolution (journal version)
Venue: arXiv cs.CL 1999
Year: 1999

Scheduling dialogs, during which people negotiate the times of appointments, are common in everyday life. This paper reports the results of an in-depth empirical investigation of resolving explicit temporal references in scheduling dialogs. There are four phases of this work: data annotation and evaluation, model development, system implementation and evaluation, and model evaluation and analysis. The system and model were developed primarily on one set of data, and then applied later to a much more complex data set, to assess the generalizability of the model for the task being performed. Many different types of empirical methods are applied to pinpoint the strengths and weaknesses of the approach. Detailed annotation instructions were developed and an intercoder reliability study was performed, showing that naive annotators can reliably perform the targeted annotations. A fully automatic system has been developed and evaluated on unseen test data, with good results on both data sets. We adopt a pure realization of a recency-based focus model to identify precisely when it is and is not adequate for the task being addressed. In addition to system results, an in-depth evaluation of the model itself is presented, based on detailed manual annotations. The results are that few errors occur specifically due to the model of focus being used, and the set of anaphoric relations defined in the model are low in ambiguity for both data sets.
Managing Object-Oriented Integration and Regression Testing
Venue: arXiv cs.SE 1999
Year: 1999

Systematic testing of object-oriented software turned out to be much more complex than testing conventional software. Especially the highly incremental and iterative development cycle demands both many more changes and partially implemented resp. re-implemented classes. Much more integration and regression testing has to be done to reach stable stages during the development. In this presentation we propose a diagram capturing all possible dependencies and interactions in an object-oriented program. Then we give algorithms and coverage criteria to identify integration resp. regression test strategys and all test cases to be executed after some implementation resp. modification activities. Finally, we summarize some practical experiences and heuristics.
Digital Library Technology for Locating and Accessing Scientific Data
Venue: arXiv cs.DL 1999
Year: 1999

In this paper we describe our efforts to bring scientific data into the digital library. This has required extension of the standard WWW, and also the extension of metadata standards far beyond the Dublin Core. Our system demonstrates this technology for real scientific data from astronomy.
ZBroker: A Query Routing Broker for Z39.50 Databases
Venue: arXiv cs.DL 1999
Year: 1999

A query routing broker is a software agent that determines from a large set of accessing information sources the ones most relevant to a user's information need. As the number of information sources on the Internet increases dramatically, future users will have to rely on query routing brokers to decide a small number of information sources to query without incurring too much query processing overheads. In this paper, we describe a query routing broker known as ZBroker developed for bibliographic database servers that support the Z39.50 protocol. ZBroker samples the content of each bibliographic database by using training queries and their results, and summarizes the bibliographic database content into a knowledge base. We present the design and implementation of ZBroker and describe its Web-based user interface.
Introduction to the RSA algorithm and modular arithmetic
Venue: arXiv cs.CR 1999
Year: 1999

These notes are a brief introduction to the RSA algorithm and modular arithmetic. They are intended for an undergraduate audience.
Brittle System Analysis
Venue: arXiv cs.NI 1999
Year: 1999

The goal of this paper is to define and analyze systems which exhibit brittle behavior. This behavior is characterized by a sudden and steep decline in performance as the system approaches the limits of tolerance. This can be due to input parameters which exceed a specified input, or environmental conditions which exceed specified operating boundaries. An analogy is made between brittle commmunication systems in particular and materials science.
Using Collective Intelligence to Route Internet Traffic
Venue: arXiv cs.LG 1999
Year: 1999

A COllective INtelligence (COIN) is a set of interacting reinforcement learning (RL) algorithms designed in an automated fashion so that their collective behavior optimizes a global utility function. We summarize the theory of COINs, then present experiments using that theory to design COINs to control internet traffic routing. These experiments indicate that COINs outperform all previously investigated RL-based, shortest path routing algorithms.
Statistical Inference and Probabilistic Modelling for Constraint-Based NLP
Venue: arXiv cs.CL 1999
Year: 1999

We present a probabilistic model for constraint-based grammars and a method for estimating the parameters of such models from incomplete, i.e., unparsed data. Whereas methods exist to estimate the parameters of probabilistic context-free grammars from incomplete data (Baum 1970), so far for probabilistic grammars involving context-dependencies only parameter estimation techniques from complete, i.e., fully parsed data have been presented (Abney 1997). However, complete-data estimation requires labor-intensive, error-prone, and grammar-specific hand-annotating of large language corpora. We present a log-linear probability model for constraint logic programming, and a general algorithm to estimate the parameters of such models from incomplete data by extending the estimation algorithm of Della-Pietra, Della-Pietra, and Lafferty (1997) to incomplete data settings.