OpenRaiser/Intern-Atlas huggingface dataset:
Scoping Constructs in Logic Programming: Implementation Problems and their Solution
Venue: arXiv cs.PL 1998
Year: 1998

The inclusion of universal quantification and a form of implication in goals in logic programming is considered. These additions provide a logical basis for scoping but they also raise new implementation problems. When universal and existential quantifiers are permitted to appear in mixed order in goals, the devices of logic variables and unification that are employed in solving existential goals must be modified to ensure that constraints arising out of the order of quantification are respected. Suitable modifications that are based on attaching numerical tags to constants and variables and on using these tags in unification are described. The resulting devices are amenable to an efficient implementation and can, in fact, be assimilated easily into the usual machinery of the Warren Abstract Machine (WAM). The provision of implications in goals results in the possibility of program clauses being added to the program for the purpose of solving specific subgoals. A naive scheme based on asserting and retracting program clauses does not suffice for implementing such additions for two reasons. First, it is necessary to also support the resurrection of an earlier existing program in the face of backtracking. Second, the possibility for implication goals to be surrounded by quantifiers requires a consideration of the parameterization of program clauses by bindings for their free variables. Devices for supporting these additional requirements are described as also is the integration of these devices into the WAM. Further extensions to the machine are outlined for handling higher-order additions to the language. The ideas presented here are relevant to the implementation of the higher-order logic programming language lambda Prolog.
The Complexity of Planar Counting Problems
Venue: arXiv cs.CC 1998
Year: 1998

We prove the #P-hardness of the counting problems associated with various satisfiability, graph and combinatorial problems, when restricted to planar instances. These problems include \begin{romannum} \item[{}] {\sc 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set, Minimum Feedback Vertex Set, X3C, Partition Into Triangles, and Clique Cover.} \end{romannum} We also prove the {\sf NP}-completeness of the {\sc Ambiguous Satisfiability} problems \cite{Sa80} and the {\sf D$^P$}-completeness (with respect to random polynomial reducibility) of the unique satisfiability problems \cite{VV85} associated with several of the above problems, when restricted to planar instances. Previously, very few {\sf #P}-hardness results, no {\sf NP}-hardness results, and no {\sf D$^P$}-completeness results were known for counting problems, ambiguous satisfiability problems and unique satisfiability problems, respectively, when restricted to planar instances. Assuming {\sf P $\neq $ NP}, one corollary of the above results is There are no $ε$-approximation algorithms for the problems of maximizing or minimizing a linear objective function subject to a planar system of linear inequality constraints over the integers.
Separating Dependency from Constituency in a Tree Rewriting System
Venue: arXiv cs.CL 1998
Year: 1998

In this paper we present a new tree-rewriting formalism called Link-Sharing Tree Adjoining Grammar (LSTAG) which is a variant of synchronous TAGs. Using LSTAG we define an approach towards coordination where linguistic dependency is distinguished from the notion of constituency. Such an approach towards coordination that explicitly distinguishes dependencies from constituency gives a better formal understanding of its representation when compared to previous approaches that use tree-rewriting systems which conflate the two issues.
Document Archiving, Replication and Migration Container for Mobile Web Users
Venue: arXiv cs.MA 1998
Year: 1998

With the increasing use of mobile workstations for a wide variety of tasks and associated information needs, and with many variations of available networks, access to data becomes a prime consideration. This paper discusses issues of workstation mobility and proposes a solution wherein the data structures are accessed in an encapsulated form - through the Portable File System (PFS) wrapper. The paper discusses an implementation of the Portable File System, highlighting the architecture and commenting upon performance of an experimental system. Although investigations have been focused upon mobile access of WWW documents, this technique could be applied to any mobile data access situation.
Performance of TCP over ABR with Long-Range Dependent VBR Background Traffic over Terrestrial and Satellite ATM networks
Venue: arXiv cs.NI 1998
Year: 1998

Compressed video is well known to be self-similar in nature. We model VBR carrying Long-Range Dependent (LRD), multiplexed MPEG-2 video sources. The actual traffic for the model is generated using fast-fourier transform of generate the fractional gaussian noise (FGN) sequence. Our model of compressed video sources bears similarity to an MPEG-2 Transport Stream carrying video, i.e., it is long-range dependent and generates traffic in a piecewise-CBR fashion. We study the effect of such VBR traffic on ABR carrying TCP traffic. The effect of such VBR traffic is that the ABR capacity is highly variant. We find that a switch algorithm like ERICA+ can tolerate this variance in ABR capacity while maintaining high throughput and low delay. We present simulation results for terrestrial and satellite configurations.
laboratories for Data Communications and Computer Networks
Venue: arXiv cs.NI 1998
Year: 1998

In this paper we describe a hands-on laboratory oriented instructional package that we have developed for data communications and networking. The package consists of a software tool, together with instructional material for a laboratory based networking curriculum. The software is based on a simulation environment that enables the student to experiment with various networking protocols, on an easy to use graphical user interface (GUI). Data message flows, packet losses, control/routing message flows, virtual circuit setups, link failures, bit errors etc., are some of the features that can be visualized in this environment. The student can also modify the networking components provided, as well as add new components using the C programming language. The instructional material consists of a set of laboratory exercises for flow and error control (HDLC), IEEE 802.3 CSMA/CD protocol, the token ring protocol, interconnecting LANs via bridges, TCP congestion avoidance and control, IP fragmentation and reassembly, ATM PNNI routing and ATM policing. The laboratory exercises have facilitated the development of a networking curriculum based on both the traditional computer networking principles, as well as the new technologies in telecommunication networking. The laboratory environment has been used in the networking curriculum at The Ohio State University, and is being piloted at other universities. The entire package is freely available over the Internet.
On Determining the Fair Bandwidth Share for ABR Connections in ATM Networks
Venue: arXiv cs.NI 1998
Year: 1998

The ABR service is designed to fairly allocate the bandwidth unused by higher priority services. The network indicates to the ABR sources the rates at which they should transmit to minimize their cell loss. Switches must constantly measure the demand and available capacity, and divide the capacity fairly among the contending connections. In order to compute the fair and efficient allocation for each connection, a switch needs to determine the effective number of active connections. In this paper, we propose a method for determining the number of active connections and the fair bandwidth share for each. We prove the efficiency and fairness of the proposed method analytically, and simulate it by incorporating it into the ERICA switch algorithm.
The OSU Scheme for Congestion Avoidance in ATM Networks: Lessons Learnt and Extensions
Venue: arXiv cs.NI 1998
Year: 1998

The OSU scheme is a rate-based congestion avoidance scheme for ATM networks using explicit rate indication. This work was one of the first attempts to define explicit rate switch mechanisms and the Resource Management (RM) cell format in Asynchronous Transfer Mode (ATM) networks. The key features of the scheme include explicit rate feedback, congestion avoidance, fair operation while maintaining high utilization, use of input rate as a congestion metric, O(1) complexity. This paper presents an overview of the scheme, presents those features of the scheme that have now become common features of other switch algorithms and discusses three extensions of the scheme.
New Applications of the Incompressibility Method: Part I
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.
Performance of Bursty World Wide Web (WWW) Sources over ABR
Venue: arXiv cs.NI 1998
Year: 1998

We model World Wide Web (WWW) servers and clients running over an ATM network using the ABR (available bit rate) service. The WWW servers are modeled using a variant of the SPECweb96 benchmark, while the WWW clients are based on a model by Mah. The traffic generated by this application is typically bursty, i.e., it has active and idle periods in transmission. A timeout occurs after given amount of idle period. During idle period the underlying TCP congestion windows remain open until a timeout expires. These open windows may be used to send data in a burst when the application becomes active again. This raises the possibility of large switch queues if the source rates are not controlled by ABR. We study this problem and show that ABR scales well with a large number of bursty TCP sources in the system.
Performance Testing Effort at the ATM Forum: An Overview
Venue: arXiv cs.NI 1998
Year: 1998

The testing group at ATM Forum is working on developing a specification for performance testing of ATM switches and networks. The emphasis is on the user perceived frame-level performance. This paper explains what is different about this new effort and gives its status.
Use-it or Lose-it Policies for the Available Bit Rate (ABR) Service in ATM Networks
Venue: arXiv cs.NI 1998
Year: 1998

The Available Bit Rate (ABR) service has been developed to support 21st century data applications over Asynchronous Transfer Mode (ATM). The ABR service uses a closed-loop rate-based traffic management framework where the network divides left-over bandwidth among contending sources. The ATM Forum traffic management group also incorporated open-loop control capabilities to make the ABR service robust to temporary network failures and source inactivity. An important problem addressed was whether rate allocations of sources should be taken away if sources do not use them. The proposed solutions, popularly known as the Use-It-or-Lose-It (UILI) policies, have had significant impact on the ABR service capabilities. In this paper we discuss the design, development, and the final shape of these policies and their impact on the ABR service. We compare the various alternatives through a performance evaluation.
Source Behavior for ATM ABR Traffic Management: An Explanation
Venue: arXiv cs.NI 1998
Year: 1998

The Available Bit Rate (ABR) service has been developed to support data applications over Asynchronous Transfer Mode (ATM) networks. The network continuously monitors its traffic and provides feedback to the source end systems. This paper explains the rules that the sources have to follow to achieve a fair and efficient allocation of network resources.
ATM Networks: Issues and Challenges Ahead
Venue: arXiv cs.NI 1998
Year: 1998

The paper begins with a discussion of current trends in networking and a historical reviews of past networking technologies some of which failed. This leads us to the discussion about what it takes for a new technology to succeed and what challenges we face in making the current dream of a seamless world-wide high-speed ATM network a reality. Issues in using ATM cells for very high speed applications are presented. Ensuring that the users benefit from ATM networks involves several other related disciplines. These are reviewed.
FDDI: Current Issues and Future Trends
Venue: arXiv cs.NI 1998
Year: 1998

Key issues in upcoming FDDI standards including low-cost fiber, twisted-pair, SONET mapping, and FDDI follow-on LAN are discussed after a brief introduction to FDDI and FDDI-II
A Comparison of Hashing Schemes for Address Lookup in Computer Networks
Venue: arXiv cs.NI 1998
Year: 1998

Using a trace of address references, we compared the efficiency of several different hashing functions, such as cyclic redundancy checking (CRC) polynomials, Fletcher checksum, folding of address octets using the exclusive-or operation and bit extraction from the address. Guidelines are provided for determining the size of the hashmark required to achieve a specified level of performance.
Divergence of Timeout Algorithms for Packet Retransmissions
Venue: arXiv cs.NI 1998
Year: 1998

The problem of adaptively setting the timeout interval for retransmitting a packet has been discussed. A layered view of the algorithms has been presented. It is shown that a timeout algorithm consists of essentially five layers or procedures which can be independently chosen and modified. A number of timeout algorithms proposed in the literature have been decomposed into these five layers. One of the key layers not discussed in the literature is that of determining the sample round trip delay for packets that have been transmitted more than once. It is shown that this layer has a significant impact on the network performance. Under repeated packet loss, most timeout algorithms either diverge or converge to a wrong value. A number of alternative schemes have been presented. It is argued that divergence is preferable to false convergence. It is a feature that is helpful in reducing network traffic congestion.
A Quantitative Measure Of Fairness And Discrimination For Resource Allocation In Shared Computer Systems
Venue: arXiv cs.NI 1998
Year: 1998

Fairness is an important performance criterion in all resource allocation schemes, including those in distributed computer systems. However, it is often specified only qualitatively. The quantitative measures proposed in the literature are either too specific to a particular application, or suffer from some undesirable characteristics. In this paper, we have introduced a quantitative measure called Indiex of FRairness. The index is applicable to any resource sharing or allocation problem. It is independent of the amount of the resource. The fairness index always lies between 0 and 1. This boundedness aids intuitive understanding of the fairness index. For example, a distribution algorithm with a fairness of 0.10 means that it is unfair to 90% of the users. Also, the discrimination index can be defined as 1 - fairness index.
Adaptive Multicast of Multi-Layered Video: Rate-Based and Credit-Based Approaches
Venue: arXiv cs.NI 1998
Year: 1998

Network architectures that can efficiently transport high quality, multicast video are rapidly becoming a basic requirement of emerging multimedia applications. The main problem complicating multicast video transport is variation in network bandwidth constraints. An attractive solution to this problem is to use an adaptive, multi-layered video encoding mechanism. In this paper, we consider two such mechanisms for the support of video multicast; one is a rate-based mechanism that relies on explicit rate congestion feedback from the network, and the other is a credit-based mechanism that relies on hop-by-hop congestion feedback. The responsiveness, bandwidth utilization, scalability and fairness of the two mechanisms are evaluated through simulations. Results suggest that while the two mechanisms exhibit performance trade-offs, both are capable of providing a high quality video service in the presence of varying bandwidth constraints.
Similarity-Based Models of Word Cooccurrence Probabilities
Venue: arXiv cs.CL 1998
Year: 1998

In many applications of natural language processing (NLP) it is necessary to determine the likelihood of a given word combination. For example, a speech recognizer may need to determine which of the two word combinations ``eat a peach'' and ``eat a beach'' is more likely. Statistical NLP methods determine the likelihood of a word combination from its frequency in a training corpus. However, the nature of language is such that many word combinations are infrequent and do not occur in any given corpus. In this work we propose a method for estimating the probability of such previously unseen word combinations using available information on ``most similar'' words. We describe probabilistic word association models based on distributional word similarity, and apply them to two tasks, language modeling and pseudo-word disambiguation. In the language modeling task, a similarity-based model is used to improve probability estimates for unseen bigrams in a back-off language model. The similarity-based method yields a 20% perplexity improvement in the prediction of unseen bigrams and statistically significant reductions in speech-recognition error. We also compare four similarity-based estimation methods against back-off and maximum-likelihood estimation methods on a pseudo-word sense disambiguation task in which we controlled for both unigram and bigram frequency to avoid giving too much weight to easy-to-disambiguate high-frequency configurations. The similarity-based methods perform up to 40% better on this particular task.
Improving Tagging Performance by Using Voting Taggers
Venue: arXiv cs.CL 1998
Year: 1998

We present a bootstrapping method to develop an annotated corpus, which is specially useful for languages with few available resources. The method is being applied to develop a corpus of Spanish of over 5Mw. The method consists on taking advantage of the collaboration of two different POS taggers. The cases in which both taggers agree present a higher accuracy and are used to retrain the taggers.
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae
Venue: arXiv cs.CC 1998
Year: 1998

We consider the problems of finding the lexicographically minimal (or maximal) satisfying assignment of propositional formulae for different restricted formula classes. It turns out that for each class from our framework, the above problem is either polynomial time solvable or complete for OptP. We also consider the problem of deciding if in the optimal assignment the largest variable gets value 1. We show that this problem is either in P or P^NP complete.
Distributed Computation, the Twisted Isomorphism, and Auto-Poiesis
Venue: arXiv cs.DC 1998
Year: 1998

This paper presents a synchronization-based, multi-process computational model of anticipatory systems called the Phase Web. It describes a self-organizing paradigm that explicitly recognizes and exploits the existence of a boundary between inside and outside, accepts and exploits intentionality, and uses explicit self-reference to describe eg. auto-poiesis. The model explicitly connects computation to a discrete Clifford algebraic formalization 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 computer program embodying the Phase Web, is available at www.cs.auc.dk/topsy.
A Linear Shift Invariant Multiscale Transform
Venue: arXiv cs.CV 1998
Year: 1998

This paper presents a multiscale decomposition algorithm. Unlike standard wavelet transforms, the proposed operator is both linear and shift invariant. The central idea is to obtain shift invariance by averaging the aligned wavelet transform projections over all circular shifts of the signal. It is shown how the same transform can be obtained by a linear filter bank.
SYNERGY: A Linear Planner Based on Genetic Programming
Venue: arXiv cs.AI 1998
Year: 1998

In this paper we describe SYNERGY, which is a highly parallelizable, linear planning system that is based on the genetic programming paradigm. Rather than reasoning about the world it is planning for, SYNERGY uses artificial selection, recombination and fitness measure to generate linear plans that solve conjunctive goals. We ran SYNERGY on several domains (e.g., the briefcase problem and a few variants of the robot navigation problem), and the experimental results show that our planner is capable of handling problem instances that are one to two orders of magnitude larger than the ones solved by UCPOP. In order to facilitate the search reduction and to enhance the expressive power of SYNERGY, we also propose two major extensions to our planning system: a formalism for using hierarchical planning operators, and a framework for planning in dynamic environments.
General Theory of Image Normalization
Venue: arXiv cs.CV 1998
Year: 1998

We give a systematic, abstract formulation of the image normalization method as applied to a general group of image transformations, and then illustrate the abstract analysis by applying it to the hierarchy of viewing transformations of a planar object.
Linguistic Reflection in Java
Venue: arXiv cs.PL 1998
Year: 1998

Reflective systems allow their own structures to be altered from within. Here we are concerned with a style of reflection, called linguistic reflection, which is the ability of a running program to generate new program fragments and to integrate these into its own execution. In particular we describe how this kind of reflection may be provided in the compiler-based, strongly typed object-oriented programming language Java. The advantages of the programming technique include attaining high levels of genericity and accommodating system evolution. These advantages are illustrated by an example taken from persistent programming which shows how linguistic reflection allows functionality (program code) to be generated on demand (Just-In-Time) from a generic specification and integrated into the evolving running program. The technique is evaluated against alternative implementation approaches with respect to efficiency, safety and ease of use.
Factorization of linear partial differential operators and Darboux integrability of nonlinear PDEs
Venue: arXiv cs.SC 1998
Year: 1998

Using a new definition of generalized divisors we prove that the lattice of such divisors for a given linear partial differential operator is modular and obtain analogues of the well-known theorems of the Loewy-Ore theory of factorization of linear ordinary differential operators. Possible applications to factorized Groebner bases computations in the commutative and non-commutative cases are discussed, an application to finding criterions of Darboux integrability of nonlinear PDEs is given.
Minimum Cuts in Near-Linear Time
Venue: arXiv cs.DS 1998
Year: 1998

We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a ``semi-duality'' between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log^3 n) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O(n^2 log n) time. This variant has an optimal RNC parallelization. Both variants improve on the previous best time bound of O(n^2 log^3 n). Other applications of the tree-packing approach are new, nearly tight bounds on the number of near minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.