OpenRaiser/Intern-Atlas huggingface dataset:
Synthesizing Customized Planners from Specifications
Venue: arXiv cs.AI 1998
Year: 1998

Existing plan synthesis approaches in artificial intelligence fall into two categories -- domain independent and domain dependent. The domain independent approaches are applicable across a variety of domains, but may not be very efficient in any one given domain. The domain dependent approaches need to be (re)designed for each domain separately, but can be very efficient in the domain for which they are designed. One enticing alternative to these approaches is to automatically synthesize domain independent planners given the knowledge about the domain and the theory of planning. In this paper, we investigate the feasibility of using existing automated software synthesis tools to support such synthesis. Specifically, we describe an architecture called CLAY in which the Kestrel Interactive Development System (KIDS) is used to derive a domain-customized planner through a semi-automatic combination of a declarative theory of planning, and the declarative control knowledge specific to a given domain, to semi-automatically combine them to derive domain-customized planners. We discuss what it means to write a declarative theory of planning and control knowledge for KIDS, and illustrate our approach by generating a class of domain-specific planners using state space refinements. Our experiments show that the synthesized planners can outperform classical refinement planners (implemented as instantiations of UCP, Kambhampati & Srivastava, 1995), using the same control knowledge. We will contrast the costs and benefits of the synthesis approach with conventional methods for customizing domain independent planners.
Integrative Windowing
Venue: arXiv cs.AI 1998
Year: 1998

In this paper we re-investigate windowing for rule learning algorithms. We show that, contrary to previous results for decision tree learning, windowing can in fact achieve significant run-time gains in noise-free domains and explain the different behavior of rule learning algorithms by the fact that they learn each rule independently. The main contribution of this paper is integrative windowing, a new type of algorithm that further exploits this property by integrating good rules into the final theory right after they have been discovered. Thus it avoids re-learning these rules in subsequent iterations of the windowing process. Experimental evidence in a variety of noise-free domains shows that integrative windowing can in fact achieve substantial run-time gains. Furthermore, we discuss the problem of noise in windowing and present an algorithm that is able to achieve run-time gains in a set of experiments in a simple domain with artificial noise.
Computational Geometry Column 34
Venue: arXiv cs.CG 1998
Year: 1998

Problems presented at the open-problem session of the 14th Annual ACM Symposium on Computational Geometry are listed.
The Computational Complexity of Probabilistic Planning
Venue: arXiv cs.AI 1998
Year: 1998

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the process of proving that certain planning problems are complete for NP^PP, we introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.
The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb
Venue: arXiv cs.DB 1998
Year: 1998

Simple economic and performance arguments suggest appropriate lifetimes for main memory pages and suggest optimal page sizes. The fundamental tradeoffs are the prices and bandwidths of RAMs and disks. The analysis indicates that with today's technology, five minutes is a good lifetime for randomly accessed pages, one minute is a good lifetime for two-pass sequentially accessed pages, and 16 KB is a good size for index pages. These rules-of-thumb change in predictable ways as technology ratios change. They also motivate the importance of the new Kaps, Maps, Scans, and $/Kaps, $/Maps, $/TBscan metrics.
Microsoft TerraServer
Venue: arXiv cs.DB 1998
Year: 1998

The Microsoft TerraServer stores aerial and satellite images of the earth in a SQL Server Database served to the public via the Internet. It is the world's largest atlas, combining five terabytes of image data from the United States Geodetic Survey, Sovinformsputnik, and Encarta Virtual Globe. Internet browsers provide intuitive spatial and gazetteer interfaces to the data. The TerraServer is also an E-Commerce application. Users can buy the right to use the imagery using Microsoft Site Servers managed by the USGS and Aerial Images. This paper describes the TerraServer's design and implementation.
A Fully Polynomial Randomized Approximation Scheme for the All Terminal Network Reliability Problem
Venue: arXiv cs.DS 1998
Year: 1998

The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability.
Correspondences between Classical, Intuitionistic and Uniform Provability
Venue: arXiv cs.LO 1998
Year: 1998

Based on an analysis of the inference rules used, we provide a characterization of the situations in which classical provability entails intuitionistic provability. We then examine the relationship of these derivability notions to uniform provability, a restriction of intuitionistic provability that embodies a special form of goal-directedness. We determine, first, the circumstances in which the former relations imply the latter. Using this result, we identify the richest versions of the so-called abstract logic programming languages in classical and intuitionistic logic. We then study the reduction of classical and, derivatively, intuitionistic provability to uniform provability via the addition to the assumption set of the negation of the formula to be proved. Our focus here is on understanding the situations in which this reduction is achieved. However, our discussions indicate the structure of a proof procedure based on the reduction, a matter also considered explicitly elsewhere.
Similarity-Based Queries for Time Series Data
Venue: arXiv cs.DB 1998
Year: 1998

We study a set of linear transformations on the Fourier series representation of a sequence that can be used as the basis for similarity queries on time-series data. We show that our set of transformations is rich enough to formulate operations such as moving average and time warping. We present a query processing algorithm that uses the underlying R-tree index of a multidimensional data set to answer similarity queries efficiently. Our experiments show that the performance of this algorithm is competitive to that of processing ordinary (exact match) queries using the index, and much faster than sequential scanning. We relate our transformations to the general framework for similarity queries of Jagadish et al.
Security amplification by composition: The case of doubly-iterated, ideal ciphers
Venue: arXiv cs.CR 1998
Year: 1998

We investigate, in the Shannon model, the security of constructions corresponding to double and (two-key) triple DES. That is, we consider F_{k1}(F_{k2}(.)) and F_{k1}(F_{k2}^{-1}(F_{k1}(.))) with the component functions being ideal ciphers. This models the resistance of these constructions to ``generic'' attacks like meet in the middle attacks. We obtain the first proof that composition actually increases the security of these constructions in some meaningful sense. We compute a bound on the probability of breaking the double cipher as a function of the number of computations of the base cipher made, and the number of examples of the composed cipher seen, and show that the success probability is the square of that for a single key cipher. The same bound holds for the two-key triple cipher. The first bound is tight and shows that meet in the middle is the best possible generic attack against the double cipher.
ABR Flow Control for Multipoint Connections
Venue: arXiv cs.NI 1998
Year: 1998

Multipoint capabilities are essential for ATM networks to efficiently support many applications, including IP multicasting and overlay applications. The current signaling and routing specifications for ATM define point-to-multipoint capabilities. Multipoint-to-point connection support is also being discussed by the signaling and PNNI groups, and will be defined in the near future for the unspecified bit rate (UBR) service. We examine point-to-multipoint and multipoint-to-point flow control for the available bit rate (ABR) service, as discussed in the traffic management working group.
Modeling Traffic Management in ATM Networks with OPNET
Venue: arXiv cs.NI 1998
Year: 1998

Asynchronous transfer mode (ATM) is the new generation of computer and communication networks that are being deployed throughout the telecommunication industry as well as in campus backbones. ATM technology distinguishes itself from the previous networking protocols in that it has the latest traffic management technology and thus allows guaranteeing delay, throughput, and other performance measures. This in turn, allows users to integrate voice, video, and data on the same network. Available bit rate (ABR) service in ATM has been designed to fairly distribute all unused capacity to data traffic and is specified in the ATM Forum's Traffic Management (TM4.0) standard. This paper will describe the OPNET models that have been developed for ATM and ABR design and analysis.
A Freely Available Morphological Analyzer, Disambiguator and Context Sensitive Lemmatizer for German
Venue: arXiv cs.CL 1998
Year: 1998

In this paper we present Morphy, an integrated tool for German morphology, part-of-speech tagging and context-sensitive lemmatization. Its large lexicon of more than 320,000 word forms plus its ability to process German compound nouns guarantee a wide morphological coverage. Syntactic ambiguities can be resolved with a standard statistical part-of-speech tagger. By using the output of the tagger, the lemmatizer can determine the correct root even for ambiguous word forms. The complete package is freely available and can be downloaded from the World Wide Web.
Analysis and Simulation of Delay and Buffer Requirements of satellite-ATM Networks for TCP/IP Traffic
Venue: arXiv cs.NI 1998
Year: 1998

In this paper we present a model to study the end-to-end delay performance of a satellite-ATM netowrk. We describe a satellite-ATM network architecture. The architecture presents a trade-off between the on-board switching/processing features and the complexity of the satellite communication systems. The end-to-end delay of a connection passing through a satellite constellation consists of the transmission delay, the uplink and downlink ground terminal-satellite propagation delay, the inter-satellite link delays, the on-board switching, processing and buffering delays. In a broadband satellite network, the propagation and the buffering delays have the most impact on the overall delay. We present an analysis of the propagation and buffering delay components for GEO and LEO systems. We model LEO constellations as satellites evenly spaced in circular orbits around the earth. A simple routing algorithm for LEO systems calculates locally optimal paths for the end-to-end connection. This is used to calculate the end-to-end propagation delays for LEO networks. We present a simulation model to calculate the buffering delay for TCP/IP traffic over ATM ABR and UBR service categories. We apply this model to calculate total end-to-end delays for TCP/IP over satellite-ATM networks.
Satellite ATM Network Architectural Considerations and TCP/IP Performance
Venue: arXiv cs.NI 1998
Year: 1998

In this paper, we have provided a summary of the design options in Satellite-ATM technology. A satellite ATM network consists of a space segment of satellites connected by inter-satellite crosslinks, and a ground segment of the various ATM networks. A satellite-ATM interface module connects the satellite network to the ATM networks and performs various call and control functions. A network control center performs various network management and resource allocation functions. Several issues such as the ATM service model, media access protocols, and traffic management issues must be considered when designing a satellite ATM network to effectively transport Internet traffic. We have presented the buffer requirements for TCP/IP traffic over ATM-UBR for satellite latencies. Our results are based on TCP with selective acknowledgments and a per-VC buffer management policy at the switches. A buffer size of about 0.5 * RTT to 1 * RTT is sufficient to provide over 98% throughput to infinite TCP traffic for long latency networks and a large number of sources. This buffer requirement is independent of the number of sources. The fairness is high for a large numbers of sources because of the per-VC buffer management performed at the switches and the nature of TCP traffic.
Design Considerations for the Virtual Source/Virtual Destination (VS/VD) Feature in the ABR Service of ATM Networks
Venue: arXiv cs.NI 1998
Year: 1998

The Available Bit Rate (ABR) service in ATM networks has been specified to allow fair and efficient support of data applications over ATM utilizing capacity left over after servicing higher priority classes. One of the architectural features in the ABR specification [tm4] is the Virtual Source/Virtual Destination (VS/VD) option. This option allows a switch to divide an end-to-end ABR connection into separately controlled ABR segments by acting like a destination on one segment, and like a source on the other. The coupling in the VS/VD switch between the two ABR control segments is implementation specific. In this paper, we model a VS/VD ATM switch and study the issues in designing coupling between ABR segments. We identify a number of implementation options for the coupling. A good choice significantly improves the stability and transient performance of the system and reduces the buffer requirements at the switches.
UBR+: Improving Performance of TCP over ATM-UBR service
Venue: arXiv cs.NI 1998
Year: 1998

ATM-UBR switches respond to congestion by dropping cells when their buffers become full. TCP connections running over UBR experience low throughput and high unfairness. For 100% TCP throughput each switch needs buffers equal to the sum of the window sizes of all the TCP connections. Intelligent drop policies can improve the performance of TCP over UBR with limited buffers. The UBR+ service proposes enhancements to UBR for intelligent drop. Early Packet Discard improves throughput but does not attempt to improve fairness. Selective packet drop based on per-connection buffer occupancy improves fairness. The Fair Buffer Allocation scheme further improves both throughput and fairness.
Performance of TCP/IP Using ATM ABR and UBR Services over Satellite Networks
Venue: arXiv cs.NI 1998
Year: 1998

We study the buffering requirements for zero cell loss for TCP/IP over satellite links using the available bit rate (ABR) and unspecified bit rate (UBR) services of asynchronous transfer mode (ATM) networks. For the ABR service, we explore the effect of feedback delay (a factor which depends upon the position of the bottleneck), the switch scheme used, and background variable bit rate (VBR) traffic. It is shown that the buffer requirement for TCP over ABR is independent of the number of TCP sources, but depends on the aforementioned factors. For the UBR service, we show that the buffer requirement is the sum of the TCP receiver window sizes. We substantiate our arguments with simulation results.
Potential Networking Applications of Global Positioning Systems (GPS)
Venue: arXiv cs.NI 1998
Year: 1998

The main goal of this study was to survey current applications of GPS to distributed systems and networks. Detailed lists of GPS products, current applications, addresses of manufacturers, and sources for further information are included in this report.
Congestion Control with Explicit Rate Indication
Venue: arXiv cs.NI 1998
Year: 1998

As the speed and the dynamic range of computer networks evolve, the issue of efficient traffic management becomes increasingly important. This work describes an approach to traffic management using explicit rate information provided to the source by the network. We present an asynchronous distributed algorithm for optimal rate calculation across the network, where optimality is understood in the maxmin sense. The algorithm quickly converges to the optimal rates and is shown to be well-behaved in transience.
A Delay Based Approach for Congestion Avoidance in Interconnected Heterogeneous Computer Networks
Venue: arXiv cs.NI 1998
Year: 1998

In heterogeneous networks, achieving congestion avoidance is difficult because the congestion feedback from one subnetwork may have no meaning to source on other other subnetworks. We propose using changes in round-trip delay as an implicit feedback. Using a black-box model of the network, we derive an expression for the optimal window as a function of the gradient of the delay-window curve. The problems of selfish optimum and social optimum are also addressed. It is shown that without a careful design, it is possible to get into a race condition during heavy congestion, where each user wants more resources than others, thereby leading to a diverging congestion It is shown that congestion avoidance using round trip delay is a promising approach. The aproach has the advantage that there is absolutely no overhead for the network itself. It is exemplified by a simple scheme. The performance of the scheme is analyzed using a simulation model. The scheme is shown to be efficient, fair, convergent and adaptive to changes in network configuration. The scheme as described works only for networks that can ne modelled with queueing servers with constant service times. Further research is required to extend it for implementation in practical networks. Several directions for future research have beensuggested.
Learning Nested Agent Models in an Information Economy
Venue: arXiv cs.MA 1998
Year: 1998

We present our approach to the problem of how an agent, within an economic Multi-Agent System, can determine when it should behave strategically (i.e. learn and use models of other agents), and when it should act as a simple price-taker. We provide a framework for the incremental implementation of modeling capabilities in agents, and a description of the forms of knowledge required. The agents were implemented and different populations simulated in order to learn more about their behavior and the merits of using and learning agent models. Our results show, among other lessons, how savvy buyers can avoid being ``cheated'' by sellers, how price volatility can be used to quantitatively predict the benefits of deeper models, and how specific types of agent populations influence system behavior.
Linear Complexity Hexahedral Mesh Generation
Venue: arXiv cs.CG 1998
Year: 1998

We show that any polyhedron forming a topological ball with an even number of quadrilateral sides can be partitioned into O(n) topological cubes, meeting face to face. The result generalizes to non-simply-connected polyhedra satisfying an additional bipartiteness condition. The same techniques can also be used to reduce the geometric version of the hexahedral mesh generation problem to a finite case analysis amenable to machine solution.
Evolution of Neural Networks to Play the Game of Dots-and-Boxes
Venue: arXiv cs.NE 1998
Year: 1998

Dots-and-Boxes is a child's game which remains analytically unsolved. We implement and evolve artificial neural networks to play this game, evaluating them against simple heuristic players. Our networks do not evaluate or predict the final outcome of the game, but rather recommend moves at each stage. Superior generalisation of play by co-evolved populations is found, and a comparison made with networks trained by back-propagation using simple heuristics as an oracle.
On the Evaluation and Comparison of Taggers: The Effect of Noise in Testing Corpora
Venue: arXiv cs.CL 1998
Year: 1998

This paper addresses the issue of {\sc pos} tagger evaluation. Such evaluation is usually performed by comparing the tagger output with a reference test corpus, which is assumed to be error-free. Currently used corpora contain noise which causes the obtained performance to be a distortion of the real value. We analyze to what extent this distortion may invalidate the comparison between taggers or the measure of the improvement given by a new system. The main conclusion is that a more rigorous testing experimentation setting/designing is needed to reliably evaluate and compare tagger accuracies.
Hard instance generation for SAT
Venue: arXiv cs.CC 1998
Year: 1998

We propose an algorithm of generating hard instances for the Satisfying Assignment Search Problem (in short, SAT). The algorithm transforms instances of the integer factorization problem into SAT instances efficiently by using the Chinese Remainder Theorem. For example, it is possible to construct SAT instances with about 5,600 variables that is as hard as factorizing 100 bit integers.
Droems: experimental mathematics, informatics and infinite dimensional geometry
Venue: arXiv cs.HC 1998
Year: 1998

The article is devoted to a problem of elaboration of the real-time interactive videosystems for accelerated nonverbal cognitive computer and telecommunications. The proposed approach is based on the using of droems (dynamically reconstructed objects of experimental mathematics) and interpretational figures as pointers to them. Four paragraphs of the article are devoted to (1) an exposition of basic notions of the interpretational geometry, (2) the operator methods in the theory of interactive dynamical videosystems, (3) the general concept of organization of the integrated interactive real-time videocognitive systems, (4) the droems and processes of their dynamical reconstruction, where the general notions are illustrated by a concrete example related to the infinite dimensional geometry. The exposition is presumably heuristic and conceptual (the first and the third paragraphs) though some particular aspects such as content of the second and the fourth paragraphs, which allow deeper formalization and detailing in present, are exposed on the mathematical level of rigor.
The Design of EzWindows: A Graphics API for an Introductory Programming Course
Venue: arXiv cs.CY 1998
Year: 1998

Teaching object-oriented programming in an introductory programming course poses considerable challenges to the instructor. An often advocated approach to meeting this challenge is the use of a simple, object-oriented graphics library. We have developed a simple, portable graphics library for teaching object-oriented programming using C++. The library, EzWindows, allows beginning programmers to design and write programs that use the graphical display found on all modern desktop computers. In addition to providing simple graphical objects such as windows, geometric shapes, and bitmaps, EzWindows provides facilities for introducing event-based programming using the mouse and timers. EzWindows has proven to be extremely popular; it is currently in use at over 200 universities, colleges, and high schools. This paper describes the rationale for EzWindows and its high-level design.