OpenRaiser/Intern-Atlas huggingface dataset:
Locally Served Network Computers
Venue: arXiv cs.AR 1998
Year: 1998

NCs are the natural evolution of PCs, ubiquitous computers everywhere. The current vision of NCs requires two improbable developments: (1) inexpensive high-bandwidth WAN links to the Internet, and (2) inexpensive centralized servers. The large NC bandwidth requirements will force each home or office to have a local server LAN attached to the NCs. These servers will be much less expensive to purchase and manage than a centralized solution. Centralized staff are expensive and unresponsive.
The Revolution Yet to Happen
Venue: arXiv cs.GL 1998
Year: 1998

All information about physical objects including humans, buildings, processes, and organizations will be online. This trend is both desirable and inevitable. Cyberspace will provide the basis for wonderful new ways to inform, entertain, and educate people. The information and the corresponding systems will streamline commerce, but will also provide new levels of personal service, health care, and automation. The most significant benefit will be a breakthrough in our ability to remotely communicate with one another using all our senses. The ACM and the transistor were born in 1947. At that time the stored program computer was a revolutionary idea and the transistor was just a curiosity. Both ideas evolved rapidly. By the mid 1960s integrated circuits appeared -- allowing mass fabrication of transistors on silicon substrates. This allowed low-cost mass-produced computers. These technologies enabled extraordinary increases in processing speed and memory coupled with extraordinary price declines. The only form of processing and memory more easily, cheaply, and rapidly fabricated is the human brain. Peter Cohrane (1996) estimates the brain to have a processing power of around 1000 million-million operations per second, (one Petaops) and a memory of 10 Terabytes. If current trends continue, computers could have these capabilities by 2047. Such computers could be 'on body' personal assistants able to recall everything one reads, hears, and sees.
Distributed Computation as Hierarchy
Venue: arXiv cs.DC 1998
Year: 1998

This paper presents a new distributed computational model of distributed systems called the phase web that extends V. Pratt's orthocurrence relation from 1986. The model uses mutual-exclusion to express sequence, and a new kind of hierarchy to replace event sequences, posets, and pomsets. The model explicitly connects computation to a discrete Clifford algebra that is in turn extended into homology and co-homology, wherein the recursive nature of objects and boundaries becomes apparent and itself subject to hierarchical recursion. Topsy, a programming environment embodying the phase web, is available from www.cs.auc.dk/topsy.
Modelling Users, Intentions, and Structure in Spoken Dialog
Venue: arXiv cs.CL 1998
Year: 1998

We outline how utterances in dialogs can be interpreted using a partial first order logic. We exploit the capability of this logic to talk about the truth status of formulae to define a notion of coherence between utterances and explain how this coherence relation can serve for the construction of AND/OR trees that represent the segmentation of the dialog. In a BDI model we formalize basic assumptions about dialog and cooperative behaviour of participants. These assumptions provide a basis for inferring speech acts from coherence relations between utterances and attitudes of dialog participants. Speech acts prove to be useful for determining dialog segments defined on the notion of completing expectations of dialog participants. Finally, we sketch how explicit segmentation signalled by cue phrases and performatives is covered by our dialog model.
Conditions on Consistency of Probabilistic Tree Adjoining Grammars
Venue: arXiv cs.CL 1998
Year: 1998

Much of the power of probabilistic methods in modelling language comes from their ability to compare several derivations for the same string in the language. An important starting point for the study of such cross-derivational properties is the notion of _consistency_. The probability model defined by a probabilistic grammar is said to be _consistent_ if the probabilities assigned to all the strings in the language sum to one. From the literature on probabilistic context-free grammars (CFGs), we know precisely the conditions which ensure that consistency is true for a given CFG. This paper derives the conditions under which a given probabilistic Tree Adjoining Grammar (TAG) can be shown to be consistent. It gives a simple algorithm for checking consistency and gives the formal justification for its correctness. The conditions derived here can be used to ensure that probability models that use TAGs can be checked for _deficiency_ (i.e. whether any probability mass is assigned to strings that cannot be generated).
Worst Case Buffer Requirements For Tcp Over ABR
Venue: arXiv cs.NI 1998
Year: 1998

ATM (asynchronous transfer mode) is the technology chosen for the Broadband Integrated Services Digital Network (B-ISDN). The ATM ABR (available bit rate) service can be used to transport ``best-effort'' traffic. In this paper, we extend our earlier work on the buffer requirements problem for TCP over ABR. Here, a worst case scenario is generated such that TCP sources send a burst of data at the time when the sources have large congestion windows and the ACRs (allowed cell rates) for ABR are high. We find that ABR using the ERICA+ switch algorithm can control the maximum queue lengths (hence the buffer requirements) even for the worst case. We present analytical arguments for the expected queue length and simulation results for different number of sources values and parameter values.
Improving the Performance of TCP over the ATM-UBR service
Venue: arXiv cs.NI 1998
Year: 1998

In this paper we study the design issues in improving TCP performance over the ATM UBR service. ATM-UBR switches respond to congestion by dropping cells when their buffers become full. TCP connections running over UBR can experience low throughput and high unfairness. Intelligent switch drop policies and end-system policies can improve the performance of TCP over UBR with limited buffers. We describe the various design options available to the network as well as to the end systems to improve TCP performance over UBR. We study the effects of Early Packet Discard, and two per-VC accounting based buffer management policies. We also study the effects of various TCP end system congestion control policies including slow start and congestion avoidance, fast retransmit and recovery and selective acknowledgments. We present simulation results for various small and large latency configurations with varying buffer sizes and number of sources.
Design Issues for providing Minimum Rate Guarantees to the ATM Unspecified Bit Rate Service
Venue: arXiv cs.NI 1998
Year: 1998

Recent enhancements have been proposed to the ATM Unspecified Bit Rate (UBR) service that guarantee a minimum rate at the frame level to the UBR VCs. These enhancements have been called Guaranteed Frame Rate (GFR). In this paper, we discuss the motivation, design and implementation issues for GFR. We present the design of buffer management and policing mechanisms to implement GFR. We study the effects of policing, per-VC buffer allocation, and per-VC queuing on providing GFR to TCP/IP traffic. We conclude that per-VC scheduling is necessary to provide minimum rate guarantees to TCP traffic. We examine the role of frame tagging in the presence of scheduling and buffer management for providing minumum rate guarantees. The use of GFR to support the Internet Controlled Load Service is also discussed.
Analysis and Modeling of Traffic in Modern Data Communication Networks
Venue: arXiv cs.NI 1998
Year: 1998

In performance analysis and design of communication netword modeling data traffic is important. With introduction of new applications, the characteristics of the data traffic changes. We present a brief review the different models of data traffic and how they have evolved. We present results of data traffic analysis and simulated traffic, which demonstrates that the packet train model fits the traffic at source destination level and long-memory (self-similar) model fits the traffic at the aggregate level.
Performance and Buffering Requirements of Internet Protocols over ATM ABR and UBR Services
Venue: arXiv cs.NI 1998
Year: 1998

The Asynchronous Transfer Mode (ATM) networks are quickly being adopted as backbones over various parts of the Internet. This paper analyzes the performance of TCP/IP protocols over ATM network's Available Bit Rate (ABR) and Unspecified Bit Rate (UBR) services. It is shown that ABR pushes congestion to the edges of the ATM network while UBR leaves it inside the ATM portion.
On Source Rules for ABR Service on ATM Networks with Satellite Links
Venue: arXiv cs.NI 1998
Year: 1998

During the design of ABR traffic management at the ATM Forum, we performed several analyses to ensure that the ABR service will operate efficiently over satellite links. In the cases where the performance was unacceptable, we suggested modifications to the traffic management specifications. This paper describes one such issue related to the count of missing resource management cells (Crm) parameter of the ABR source behavior. The analysis presented here led to the changes which are now part of the ATM traffic management (TM 4.0) specification. In particular, the size of the transient buffer exposure (TBE) parameter was set to 24 bits, and no size was enforced for the Crm parameter. This simple change improved the throughput over OC-3 satellite links from 45 Mbps to 140 Mbps.
The OSU Scheme for Congestion Avoidance in ATM networks Using Explicit Rate Indication
Venue: arXiv cs.NI 1998
Year: 1998

An explicit rate indication scheme for congestion avoidance in computer and telecommunication networks is proposed. The sources monitor their load and provide the information periodically to the switches. The switches, in turn, compute the load level and ask the sources to adjust their rates up or down. The scheme achieves high link utilization, fair allocation of rates among contending sources and provides quick convergence. A backward congestion notification option is also provided. The conditions under which this option is useful are indicated.
Congestion Control in Computer Networks: Trends and Issues
Venue: arXiv cs.NI 1998
Year: 1998

Popular myths that cheaper memory, high-speed links and high-speed processors will solve the problem of congestion in computer networks are shown to be false. A simple definition for congestion based on supply and demand of resources is proposed and is then used to classify various congestion schemes. The issues that make the congestion problem a difficult one are discussed, and then the architectural decisions that affect the design of a congestion scheme are presented. It is argued that long-, medium- and short-term congestion problems require different solutions. Some of the recent schemes are brifly surveyed, and areas for further research are discussed.
On Caching out-of-order packets in window flow controlled networks
Venue: arXiv cs.NI 1998
Year: 1998

In window flow controlled networks, if a packet is lost the destination has to decide whether to save (cache) subsequent out-of-order packets. Also, the source has to decide whether to send just one packet or to send all packets following it. This leads to four different types of caching schemes. Simulations show, against our immediate intuition, that regardless of whether the destination is caching or not, the source should retransmit only one packet. This paper describes the alternatives to, and provides justification for, schemes used in Digital Network Architecture and ARPAnet TCP.
Hyper-Systolic Matrix Multiplication
Venue: arXiv cs.MS 1998
Year: 1998

A novel parallel algorithm for matrix multiplication is presented. The hyper-systolic algorithm makes use of a one-dimensional processor abstraction. The procedure can be implemented on all types of parallel systems. It can handle matrix-vector multiplications as well as transposed matrix products.
A role of constraint in self-organization
Venue: arXiv cs.NE 1998
Year: 1998

In this paper we introduce a neural network model of self-organization. This model uses a variation of Hebb rule for updating its synaptic weights, and surely converges to the equilibrium status. The key point of the convergence is the update rule that constrains the total synaptic weight and this seems to make the model stable. We investigate the role of the constraint and show that it is the constraint that makes the model stable. For analyzing this setting, we propose a simple probabilistic game that models the neural network and the self-organization process. Then, we investigate the characteristics of this game, namely, the probability that the game becomes stable and the number of the steps it takes.
Security Policy Specification Using a Graphical Approach
Venue: arXiv cs.CR 1998
Year: 1998

A security policy states the acceptable actions of an information system, as the actions bear on security. There is a pressing need for organizations to declare their security policies, even informal statements would be better than the current practice. But, formal policy statements are preferable to support (1) reasoning about policies, e.g., for consistency and completeness, (2) automated enforcement of the policy, e.g., using wrappers around legacy systems or after the fact with an intrusion detection system, and (3) other formal manipulation of policies, e.g., the composition of policies. We present LaSCO, the Language for Security Constraints on Objects, in which a policy consists of two parts: the domain (assumptions about the system) and the requirement (what is allowed assuming the domain is satisfied). Thus policies defined in LaSCO have the appearance of conditional access control statements. LaSCO policies are specified as expressions in logic and as directed graphs, giving a visual view of policy. LaSCO has a simple semantics in first order logic (which we provide), thus permitting policies we write, even for complex policies, to be very perspicuous. LaSCO has syntax to express many of the situations we have found to be useful on policies or, more interesting, the composition of policies. LaSCO has an object-oriented structure, permitting it to be useful to describe policies on the objects and methods of an application written in an object-oriented language, in addition to the traditional policies on operating system objects. A LaSCO specification can be automatically translated into executable code that checks an invocation of a program with respect to a policy. The implementation of LaSCO is in Java, and generates wrappers to check Java programs with respect to a policy.
Pre-fetching tree-structured data in distributed memory
Venue: arXiv cs.DC 1998
Year: 1998

A distributed heap storage manager has been implemented on the Fujitsu AP1000 multicomputer. The performance of various pre-fetching strategies is experimentally compared. Subjective programming benefits and objective performance benefits of up to 10% in pre-fetching are found for certain applications, but not for all. The performance benefits of pre-fetching depend on the specific data structure and access patterns. We suggest that control of pre-fetching strategy be dynamically under the control of the application.
Computational Geometry Column 32
Venue: arXiv cs.CG 1998
Year: 1998

The proof of Dey's new k-set bound is illustrated.
Second Product Line Practice Workshop Report
Venue: arXiv cs.SE 1998
Year: 1998

The second Software Engineering Institute Product Line Practice Workshop was a hands-on meeting held in November 1997 to share industry practices in software product lines and to explore the technical and non-technical issues involved. This report synthesizes the workshop presentations and discussions, which identified factors involved in product line practices and analyzed issues in the areas of software engineering, technical management, and enterprise management.
Translating near-synonyms: Possibilities and preferences in the interlingua
Venue: arXiv cs.CL 1998
Year: 1998

This paper argues that an interlingual representation must explicitly represent some parts of the meaning of a situation as possibilities (or preferences), not as necessary or definite components of meaning (or constraints). Possibilities enable the analysis and generation of nuance, something required for faithful translation. Furthermore, the representation of the meaning of words, especially of near-synonyms, is crucial, because it specifies which nuances words can convey in which contexts.
Choosing the Word Most Typical in Context Using a Lexical Co-occurrence Network
Venue: arXiv cs.CL 1998
Year: 1998

This paper presents a partial solution to a component of the problem of lexical choice: choosing the synonym most typical, or expected, in context. We apply a new statistical approach to representing the context of a word through lexical co-occurrence networks. The implementation was trained and evaluated on a large corpus, and results show that the inclusion of second-order co-occurrence relations improves the performance of our implemented lexical choice program.
Abstract State Machines 1988-1998: Commented ASM Bibliography
Venue: arXiv cs.SE 1998
Year: 1998

An annotated bibliography of papers which deal with or use Abstract State Machines (ASMs), as of January 1998.
Comparing a statistical and a rule-based tagger for German
Venue: arXiv cs.CL 1998
Year: 1998

In this paper we present the results of comparing a statistical tagger for German based on decision trees and a rule-based Brill-Tagger for German. We used the same training corpus (and therefore the same tag-set) to train both taggers. We then applied the taggers to the same test corpus and compared their respective behavior and in particular their error rates. Both taggers perform similarly with an error rate of around 5%. From the detailed error analysis it can be seen that the rule-based tagger has more problems with unknown words than the statistical tagger. But the results are opposite for tokens that are many-ways ambiguous. If the unknown words are fed into the taggers with the help of an external lexicon (such as the Gertwol system) the error rate of the rule-based tagger drops to 4.7%, and the respective rate of the statistical taggers drops to around 3.7%. Combining the taggers by using the output of one tagger to help the other did not lead to any further improvement.
Complexity limitations on quantum computation
Venue: arXiv cs.CC 1998
Year: 1998

We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation. We show several results for the probabilistic quantum class BQP. 1. BQP is low for PP, i.e., PP^BQP=PP. 2. There exists a relativized world where P=BQP and the polynomial-time hierarchy is infinite. 3. There exists a relativized world where BQP does not have complete sets. 4. There exists a relativized world where P=BQP but P is not equal to UP intersect coUP and one-way functions exist. This gives a relativized answer to an open question of Simon.
Generating Segment Durations in a Text-To-Speech System: A Hybrid Rule-Based/Neural Network Approach
Venue: arXiv cs.NE 1998
Year: 1998

A combination of a neural network with rule firing information from a rule-based system is used to generate segment durations for a text-to-speech system. The system shows a slight improvement in performance over a neural network system without the rule firing information. Synthesized speech using segment durations was accepted by listeners as having about the same quality as speech generated using segment durations extracted from natural speech.
Symmetries and transitions of bounded Turing machines
Venue: arXiv cs.LO 1998
Year: 1998

We consider the structures given by repeatedly generalising the definition of finite state automata by symmetry considerations, and constructing analogues of transition monoids at each step. This approach first gives us non-deterministic automata, then (non-deterministic) two-way automata and bounded Turing machines --- that is, Turing machines where the read / write head is unable to move past the end of the input word. In the case of two-way automata, the transition monoids generalise to endomorphism monoids in compact closed categories. These use Girard's resolution formula (from the Geometry of Interaction representation of linear logic) to construct the images of singleton words. In the case of bounded Turing machines, the transition homomorphism generalises to a monoid homomorphism from the natural numbers to a monoid constructed from the union of endomorphism monoids of a compact closed category, together with an appropriate composition. These use Girard's execution formula (also from the Geometry of Interaction representation of linear logic) to construct images of singletons.
Object Oriented and Functional Programming for Symbolic Manipulation
Venue: arXiv cs.SC 1999
Year: 1999

The advantages of mixed approach with using different kinds of programming techniques for symbolic manipulation are discussed. The main purpose of approach offered is merge the methods of object oriented programming that convenient for presentation data and algorithms for user with advantages of functional languages for data manipulation, internal presentation, and portability of software.
Analysis of approximate nearest neighbor searching with clustered point sets
Venue: arXiv cs.CG 1999
Year: 1999

We present an empirical analysis of data structures for approximate nearest neighbor searching. We compare the well-known optimized kd-tree splitting method against two alternative splitting methods. The first, called the sliding-midpoint method, which attempts to balance the goals of producing subdivision cells of bounded aspect ratio, while not producing any empty cells. The second, called the minimum-ambiguity method is a query-based approach. In addition to the data points, it is also given a training set of query points for preprocessing. It employs a simple greedy algorithm to select the splitting plane that minimizes the average amount of ambiguity in the choice of the nearest neighbor for the training points. We provide an empirical analysis comparing these two methods against the optimized kd-tree construction for a number of synthetically generated data and query sets. We demonstrate that for clustered data and query sets, these algorithms can provide significant improvements over the standard kd-tree construction for approximate nearest neighbor searching.
A Discipline of Evolutionary Programming
Venue: arXiv cs.NE 1999
Year: 1999

Genetic fitness optimization using small populations or small population updates across generations generally suffers from randomly diverging evolutions. We propose a notion of highly probable fitness optimization through feasible evolutionary computing runs on small size populations. Based on rapidly mixing Markov chains, the approach pertains to most types of evolutionary genetic algorithms, genetic programming and the like. We establish that for systems having associated rapidly mixing Markov chains and appropriate stationary distributions the new method finds optimal programs (individuals) with probability almost 1. To make the method useful would require a structured design methodology where the development of the program and the guarantee of the rapidly mixing property go hand in hand. We analyze a simple example to show that the method is implementable. More significant examples require theoretical advances, for example with respect to the Metropolis filter.
Is Word Sense Disambiguation just one more NLP task?
Venue: arXiv cs.CL 1999
Year: 1999

This paper compares the tasks of part-of-speech (POS) tagging and word-sense-tagging or disambiguation (WSD), and argues that the tasks are not related by fineness of grain or anything like that, but are quite different kinds of task, particularly becuase there is nothing in POS corresponding to sense novelty. The paper also argues for the reintegration of sub-tasks that are being separated for evaluation