OpenRaiser/Intern-Atlas huggingface dataset:
Spoken Language Dialogue Systems and Components: Best practice in development and evaluation (DISC 24823) - Periodic Progress Report 1: Basic Details of the Action
Venue: arXiv cs.CL 1998
Year: 1998

The DISC project aims to (a) build an in-depth understanding of the state-of-the-art in spoken language dialogue systems (SLDSs) and components development and evaluation with the purpose of (b) developing a first best practice methodology in the field. The methodology will be accompanied by (c) a series of development and evaluation support tools. To the limited extent possible within the duration of the project, the draft versions of the methodology and the tools will be (d) tested by SLDS developers from industry and research, and will be (e) packaged to best suit their needs. In the first year of DISC, (a) has been accomplished, and (b) and (c) have started. A proposal to complete the work proposed above by adding 12 months to the 18 months of the present project, has been submitted to Esprit Long-Term Research in March 1998.
New Applications of the Incompressibility Method: Part II
Venue: arXiv cs.CC 1998
Year: 1998

The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit new simple proofs using the incompressibility method.
TCP Selective Acknowledgments and UBR Drop Policies to Improve ATM-UBR Performance over Terrestrial and Satellite Networks
Venue: arXiv cs.NI 1998
Year: 1998

We study the performance of Selective Acknowledgments with TCP over the ATM-UBR service category. We examine various UBR drop policies, TCP mechanisms and network configurations to recommend optimal parameters for TCP over UBR. We discuss various TCP congestion control mechanisms compare their performance for LAN and WAN networks. We describe the effect of satellite delays on TCP performance over UBR and present simulation results for LAN, WAN and satellite networks. SACK TCP improves the performance of TCP over UBR, especially for large delay networks. Intelligent drop policies at the switches are an important factor for good performance in local area networks.
A Survey of Protocols and Open Issues in ATM Multipoint Communication
Venue: arXiv cs.NI 1998
Year: 1998

Asynchronous transfer mode (ATM) networks must define multicast capabilities in order to efficiently support numerous applications, such as video conferencing and distributed applications, in addition to LAN emulation (LANE) and Internet protocol (IP) multicasting. Several problems and issues arise in ATM multicasting, such as signaling, routing, connection admission control, and traffic management problems. IP integrated services over ATM poses further challenges to ATM multicasting. Scalability and simplicity are the two main concerns for ATM multicasting. This paper provides a survey of the current work on multicasting problems in general, and ATM multicasting in particular. A number of proposed schemes is examined, such as the schemes MARS, MCS, SEAM, SMART, RSVP, and various multipoint traffic management and transport-layer schemes. The paper also indicates a number of key open issues that remain unresolved.
Optimal Point Placement for Mesh Smoothing
Venue: arXiv cs.CG 1998
Year: 1998

We study the problem of moving a vertex in an unstructured mesh of triangular, quadrilateral, or tetrahedral elements to optimize the shapes of adjacent elements. We show that many such problems can be solved in linear time using generalized linear programming. We also give efficient algorithms for some mesh smoothing problems that do not fit into the generalized linear programming paradigm.
Myths about Congestion Management in High Speed Networks
Venue: arXiv cs.NI 1998
Year: 1998

Weaknesses in several recently proposed ideas about congestion control and avoidance in high-speed netwroks are identified. Both sides of the debate concerning prior reservation of resources versus walk-in service, open-loop control versus feedback control, rate control versus window control, and router-based control versus source-based control are presented. The circumstances under which backpressure is useful or not are discussed, and it is argued that a single congestion scheme is not sufficient, but that a combination of several schemes is required for complete congestion management in a network.
Performance Analysis of FDDI Token Ring Networks: Effect of Parameters and Guidelines for Setting TTRT
Venue: arXiv cs.NI 1998
Year: 1998

The performance of Fiber-Distributed Data Interface (FDDI) depends upon several workload parameters; for example; the arrival pattern, frame size, and configuration parameters, such as the number of stations on the ring, extent of the ring, and number of stations that are waiting to transmit. In addition, the performance is affected by a parameter called the Target Token Rotation Time (TTRT), which can be controlled by the network manager. We considered the effect of TTRT on various performance metrics for different ring configurations and concluded that a TTRT value of 8 ms provides a good performance over a wide range of configurations and workloads.
Bicriteria Network Design Problems
Venue: arXiv cs.CC 1998
Year: 1998

We study a general class of bicriteria network design problems. A generic problem in this class is as follows: Given an undirected graph and two minimization objectives (under different cost functions), with a budget specified on the first, find a <subgraph \from a given subgraph-class that minimizes the second objective subject to the budget on the first. We consider three different criteria - the total edge cost, the diameter and the maximum degree of the network. Here, we present the first polynomial-time approximation algorithms for a large class of bicriteria network design problems for the above mentioned criteria. The following general types of results are presented. First, we develop a framework for bicriteria problems and their approximations. Second, when the two criteria are the same %(note that the cost functions continue to be different) we present a ``black box'' parametric search technique. This black box takes in as input an (approximation) algorithm for the unicriterion situation and generates an approximation algorithm for the bicriteria case with only a constant factor loss in the performance guarantee. Third, when the two criteria are the diameter and the total edge costs we use a cluster-based approach to devise a approximation algorithms --- the solutions output violate both the criteria by a logarithmic factor. Finally, for the class of treewidth-bounded graphs, we provide pseudopolynomial-time algorithms for a number of bicriteria problems using dynamic programming. We show how these pseudopolynomial-time algorithms can be converted to fully polynomial-time approximation schemes using a scaling technique.
Processing Unknown Words in HPSG
Venue: arXiv cs.CL 1998
Year: 1998

The lexical acquisition system presented in this paper incrementally updates linguistic properties of unknown words inferred from their surrounding context by parsing sentences with an HPSG grammar for German. We employ a gradual, information-based concept of ``unknownness'' providing a uniform treatment for the range of completely known to maximally unknown lexical entries. ``Unknown'' information is viewed as revisable information, which is either generalizable or specializable. Updating takes place after parsing, which only requires a modified lexical lookup. Revisable pieces of information are identified by grammar-specified declarations which provide access paths into the parse feature structure. The updating mechanism revises the corresponding places in the lexical feature structures iff the context actually provides new information. For revising generalizable information, type union is required. A worked-out example demonstrates the inferential capacity of our implemented system.
The descriptive complexity approach to LOGCFL
Venue: arXiv cs.CC 1998
Year: 1998

Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's ``hardest context-free language'' is LOGCFL-complete under quantifier-free BIT-free projections. We then prove that FO with unary groupoidal quantifiers is strictly more expressive with the BIT predicate than without. Considering a particular groupoidal quantifier, we prove that first-order logic with majority of pairs is strictly more expressive than first-order with majority of individuals. As a technical tool of independent interest, we define the notion of an aperiodic nondeterministic finite automaton and prove that FO translations are precisely the mappings computed by single-valued aperiodic nondeterministic finite transducers.
Randomization yields simple O(n log star n) algorithms for difficult Omega(n) problems
Venue: arXiv cs.CG 1998
Year: 1998

We use here the results on the influence graph by Boissonnat et al. to adapt them for particular cases where additional information is available. In some cases, it is possible to improve the expected randomized complexity of algorithms from O(n log n) to O(n log star n). This technique applies in the following applications: triangulation of a simple polygon, skeleton of a simple polygon, Delaunay triangulation of points knowing the EMST (euclidean minimum spanning tree).
Flysig: Dataflow Oriented Delay-Insensitive Processor for Rapid Prototyping of Signal Processing
Venue: arXiv cs.AR 1998
Year: 1998

As the one-chip integration of HW-modules designed by different companies becomes more and more popular reliability of a HW-design and evaluation of the timing behavior during the prototype stage are absolutely necessary. One way to guarantee reliability is the use of robust design styles, e.g., delay-insensitivity. For early timing evaluation two aspects must be considered: a) The timing needs to be proportional to technology variations and b) the implemented architecture should be identical for prototype and target. The first can be met also by delay-insensitive implementation. The latter one is the key point. A unified architecture is needed for prototyping as well as implementation. Our new approach to rapid prototyping of signal processing tasks is based on a configurable, delay-insensitive implemented processor called Flysig. In essence, the Flysig processor can be understood as a complex FPGA where the CLBs are substituted by bit-serial operators. In this paper the general concept is detailed and first experimental results are given for demonstration of the main advantages: delay-insensitive design style, direct correspondence between prototyping and target architecture, high performance and reasonable shortening of the design cycle.
Computational Geometry Column 33
Venue: arXiv cs.CG 1998
Year: 1998

Several recent SIGGRAPH papers on surface simplification are described.
Broy-Lamport Specification Problem: A Gurevich Abstract State Machine Solution
Venue: arXiv cs.SE 1998
Year: 1998

We apply the Gurevich Abstract State Machine methodology to a benchmark specification problem of Broy and Lamport.
An Offline Partial Evaluator for Evolving Algebras
Venue: arXiv cs.SE 1998
Year: 1998

We describe the architecture of an evolving algebra partial evaluator, a program which specializes an evolving algebra with respect to a portion of its input. We discuss the particular analysis, specialization, and optimization techniques used and show an example of its use.
Writing and Editing Complexity Theory: Tales and Tools
Venue: arXiv cs.GL 1998
Year: 1998

Each researcher should have a full shelf---physical or virtual---of books on writing and editing prose. Though we make no claim to any special degree of expertise, we recently edited a book of complexity theory surveys (Complexity Theory Retrospective II, Springer-Verlag, 1997), and in doing so we were brought into particularly close contact with the subject of this article, and with a number of the excellent resources available to writers and editors. In this article, we list some of these resources, and we also relate some of the adventures we had as our book moved from concept to reality.
An Emptiness Algorithm for Regular Types with Set Operators
Venue: arXiv cs.LO 1998
Year: 1998

An algorithm to decide the emptiness of a regular type expression with set operators given a set of parameterised type definitions is presented. The algorithm can also be used to decide the equivalence of two regular type expressions and the inclusion of one regular type expression in another. The algorithm strictly generalises previous work in that tuple distributivity is not assumed and set operators are permitted in type expressions.
Push vs. Pull in Web-Based Network Management
Venue: arXiv cs.NI 1998
Year: 1998

In this paper, we show how Web technologies can be used effectively to (i) address some of the deficiencies of traditional IP network management platforms, and (ii) render these expensive platforms redundant. We build on the concept of embedded management application, proposed by Wellens and Auerbach, and present two models of network management application designs that rely on Web technologies. First, the pull model is based on the request/response paradigm. It is typically used to perform data polling. Several commercial management platforms already use Web technologies that rely on this model to provide for ad hoc management; we demonstrate how to extend this to regular management. Second, the push model is a novel approach which relies on the publish/subscribe/distribute paradigm. It is better suited to regular management than the pull model, and allows administrators to conserve network bandwidth as well as CPU time on the management station. It can be seen as a generalization of the paradigm commonly used for notification delivery. Finally, we introduce the concept of the collapsed network management platform, where these two models coexist.
A Human - machine interface for teleoperation of arm manipulators in a complex environment
Venue: arXiv cs.RO 1998
Year: 1998

This paper discusses the feasibility of using configuration space (C-space) as a means of visualization and control in operator-guided real-time motion of a robot arm manipulator. The motivation is to improve performance of the human operator in tasks involving the manipulator motion in an environment with obstacles. Unlike some other motion planning tasks, operators are known to make expensive mistakes in such tasks, even in a simpler two-dimensional case. They have difficulty learning better procedures and their performance improves very little with practice. Using an example of a two-dimensional arm manipulator, we show that translating the problem into C-space improves the operator performance rather remarkably, on the order of magnitude compared to the usual work space control. An interface that makes the transfer possible is described, and an example of its use in a virtual environment is shown.
A Probabilistic Approach to Lexical Semantic Knowledge Acquisition and S tructural Disambiguation
Venue: arXiv cs.CL 1998
Year: 1998

In this thesis, I address the problem of automatically acquiring lexical semantic knowledge, especially that of case frame patterns, from large corpus data and using the acquired knowledge in structural disambiguation. The approach I adopt has the following characteristics: (1) dividing the problem into three subproblems: case slot generalization, case dependency learning, and word clustering (thesaurus construction). (2) viewing each subproblem as that of statistical estimation and defining probability models for each subproblem, (3) adopting the Minimum Description Length (MDL) principle as learning strategy, (4) employing efficient learning algorithms, and (5) viewing the disambiguation problem as that of statistical prediction. Major contributions of this thesis include: (1) formalization of the lexical knowledge acquisition problem, (2) development of a number of learning methods for lexical knowledge acquisition, and (3) development of a high-performance disambiguation method.
Quantum simulations of classical random walks and undirected graph connectivity
Venue: arXiv cs.CC 1998
Year: 1998

It is not currently known if quantum Turing machines can efficiently simulate probabilistic computations in the space-bounded case. In this paper we show that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes: random walks on undirected graphs. By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and halt absolutely. It follows that symmetric logspace is contained in the quantum analogue of randomized logspace.
The Self-Organizing Symbiotic Agent
Venue: arXiv cs.NE 1998
Year: 1998

In [N. A. Baas, Emergence, Hierarchies, and Hyper-structures, in C.G. Langton ed., Artificial Life III, Addison Wesley, 1994.] a general framework for the study of Emergence and hyper-structure was presented. This approach is mostly concerned with the description of such systems. In this paper we will try to bring forth a different aspect of this model we feel will be useful in the engineering of agent based solutions, namely the symbiotic approach. In this approach a self-organizing method of dividing the more complex "main-problem" to a hyper-structure of "sub-problems" with the aim of reducing complexity is desired. A description of the general problem will be given along with some instances of related work. This paper is intended to serve as an introductory challenge for general solutions to the described problem.
KnightCap: A chess program that learns by combining TD(lambda) 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 game-tree search. We present some experiments in which our chess program ``KnightCap'' used TDLeaf(lambda) to learn its evaluation function while playing on the Free Internet Chess Server (FICS, fics.onenet.net). The main success we report is that KnightCap improved from a 1650 rating to a 2150 rating in just 308 games and 3 days of play. As a reference, a rating of 1650 corresponds to about level B human play (on a scale from E (1000) to A (1800)), while 2150 is human master level. We discuss some of the reasons for this success, principle among them being the use of on-line, rather than self-play.
Average-Case Complexity of Shellsort
Venue: arXiv cs.DS 1999
Year: 1999

We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a $p$-pass Shellsort for any incremental sequence is $Ω(pn^{1 + 1/p)$ for all $p \leq \log n$. Using similar arguments, we analyze the average-case complexity of several other sorting algorithms.
Minimum Description Length Induction, Bayesianism, and Kolmogorov Complexity
Venue: arXiv cs.LG 1999
Year: 1999

The relationship between the Bayesian approach and the minimum description length approach is established. We sharpen and clarify the general modeling principles MDL and MML, abstracted as the ideal MDL principle and defined from Bayes's rule by means of Kolmogorov complexity. The basic condition under which the ideal principle should be applied is encapsulated as the Fundamental Inequality, which in broad terms states that the principle is valid when the data are random, relative to every contemplated hypothesis and also these hypotheses are random relative to the (universal) prior. Basically, the ideal principle states that the prior probability associated with the hypothesis should be given by the algorithmic universal probability, and the sum of the log universal probability of the model plus the log of the probability of the data given the model should be minimized. If we restrict the model class to the finite sets then application of the ideal principle turns into Kolmogorov's minimal sufficient statistic. In general we show that data compression is almost always the best strategy, both in hypothesis identification and prediction.
MyLibrary: A Model for Implementing a User-centered, Customizable Interface to a Library's Collection of Information Resources
Venue: arXiv cs.DL 1999
Year: 1999

The paper describes an extensible model for implementing a user-centered, customizable interface to a library's collection of information resources. This model, called MyLibrary, integrates the principles of librarianship (collection, organization, dissemination, and evaluation) with globally networked computing resources creating a dynamic, customer-driven front-end to any library's set of materials. The model supports a framework for libraries to provide enhanced access to local and remote sets of data, information, and knowledge. At the same, the model does not overwhelm its users with too much information because the users control exactly how much information is displayed to them at any given time. The model is active and not passive; direct human interaction, computer mediated guidance and communication technologies, as well as current awareness services all play indispensable roles in this system.
The Alex Catalogue, A Collection of Digital Texts with Automatic Methods for Acquisition and Cataloging, User-Defined Typography, Cross-searching of Indexed Content, and a Sense of Community
Venue: arXiv cs.DL 1999
Year: 1999

This paper describes the Alex Catalogue of Electronic Texts, the only Internet-accessible collection of digital documents allowing the user to 1) dynamically create customized, typographically readable documents on demand, 2) search the content of one or more documents from the collection simultaneously, 3) create sets of documents from the collection for review and annotation, and 4) publish these sets of annotated documents in turn fostering a sense of community around the Catalogue. More than a just a collection of links that will break over time, Alex is an archive of electronic texts providing unprecedented access to its content and features allowing it to meet the needs of a wide variety of users and settings. Furthermore, the process of maintaining the Catalogue is streamlined with tools for automatic acquisition and cataloging making it possible to sustain the service with a minimum of personnel.
Resource Discovery in Trilogy
Venue: arXiv cs.DL 1999
Year: 1999

Trilogy is a collaborative project whose key aim is the development of an integrated virtual laboratory to support research training within each institution and collaborative projects between the partners. In this paper, the architecture and underpinning platform of the system is described with particular emphasis being placed on the structure and the integration of the distributed database. A key element is the ontology that provides the multi-agent system with a conceptualisation specification of the domain; this ontology is explained, accompanied by a discussion how such a system is integrated and used within the virtual laboratory. Although in this paper, Telecommunications and in particular Broadband networks are used as exemplars, the underlying system principles are applicable to any domain where a combination of experimental and literature-based resources are required.