All Computer Science and Engineering Research

Synchrony continues to be an important concern in concurrent programming. Existing languages and models have introduced a great variety of constructs for expressing and managing synchronization among sequential processes or atomic actions. This paper puts forth a model in which synchrony is viewed as a relation among atomic actions, a relation which may evolve with time. The model is shown to be convenient for expressing formally the semantics of synchrony as it appears in many of the languages and models proposed to date. Among such models Swarm is singled out... Read More

This paper describes the design of the Axon host-network interface architecture, and performance factors determining its design. The Axon project is investigating an integrated design of the host architecture, operating systems, and communications protocols to allow applications to utilise the high bandwidth provided by the next generation of communications networks. The Axon host architecture and network interface is designed to provide a path directly between the network interface with direct access to host memory, capable of delivering bandwidth in excess of 1 Gbps to applications. This provide the ability to... Read More

ATM switching systems are required to maintain ordering for cells within a given virtual circuit. This is most commonly achieved using a switching system in which cells in a given virtual circuit are routed along a common path through the switching system. This solution has the drawback that it can lead to significant virtual circuit blocking unless the switching network is engineered with a large speed advantage, relative to the external links. Switching systems in which cells are routed independently, on the other hand, can balance the load dynamically and... Read More

This paper describes several improvements to Lee's multicast switch architecture. Our improvements make Lee's architecture practical, allowing it to achieve maximum network throughput under worst-case conditions and drastically reducing the amount of memory required for addressing of multicast cells. These improvements allow multicast to be added to a 256 port switch with 150 Mb/s links at a cost of about two additional chips per port.

Genetic Algorithms have been gaining much interest since the early 1970's and have intrigued people from the fields of machine learning, artificial intelligence, neural networks and operations research. This paper describes the approach of genetic algorithms applied to neural networks. The experiments were conducted using various functions such as XOR,AND,SINE and different network sizes. Based on the experimental data, we concluded that for small network architectures represented by the functions (SINE,ENCODE,etc), genetic algorithms were not effective and the desired results were not achieved within a reasonable period of time.

There have been a number of ATM switching system architectures proposed, but little in the way of comparison to indicate which architectures are preferable from a cost standpoint given specific performance requirements. This paper considers a range of performance requirements and compares various architectures base don the number of pin-limited chips needed to realize a system which can meet the requirements. Our results indicate that certain architectures, for example the Knockout network, are not competitive within the range we considered. Other architectures perform reasonably well in some cases, but less... Read More

Several current DNA mapping projects are based on detection of overlaps between cloned DNA molecules. This thesis places the problem of overlap detection in a probabilistic framework by deriving, for each of the relevant overlap types, expressions for the probability that a postulated overlap is correct. In addition, computationally feasible approximations for the probability expressions are developed. These expressions have been implemented and, using the implementations, the validity of both the original and the approximated probability expressions is verified.

This technical report describes preliminary research investigating the relationship between information theory and Bayes' theory for estimation of the probability of clone overlap for the use in DNA restriction mapping. A number of languages (along with information theoretic metrics) capable of describing a hypothesized overlap are presented. For each language, the MML criterion is applied to the encoded overlaps of a pair of clones to search for that overlap which is most probable. The objective is to order the pair's encoded overlaps, based on the MML criterion, from the most... Read More

In this paper the functionality requirements of a user-network interface for bandwidth allocation are discussed. Such requirements include the capability to provide end users with a variety of non-deteriorating connection types. In addition effective policy enforcement and traffic shaping mechanisms are required to facilitate network management and the efficient utilization of network resources. Based on these requirements, a user-network interface model is proposed, and its performance is studied. Its intrinsic properties are revealed for two cases, a Poisson source and a bursty source.

Troubleshooting measurement equipment can be complex and time consuming task. We developed a system that incorporates model-based diagnosis to troubleshoot measurement instrumentation systems. It consists of a knowledge representation scheme for modeling the structure and behavior of measurement systems and the ability to reason from first principles about these models. It accepts observed values from the user and returns a list of components that are suspected of failing. The current system was developed using the object oriented approach and was designed to be reusable for a variety of measurement systems.... Read More

Visualization is defined as the transformation of information into a graphical form. In recent years, visualization has increasingly been used in a variety of applications. Our work focuses on the visualization of concurrent computations. We wish to collect information about the operational behavior of concurrent computations. We wish to collect information into a graphical representation, and display the resulting image.

This paper describes the underlying model for a visualization environment concerned with exploring, monitoring, and presenting concurrent computations. The model is declarative in the sense that visualization is treated as the composition of several mappings which, as a whole, map computational states into full-color images of a 3-D geometric world. The mappings defining the visualizations are specified using a rule-based notation. The visualization methodology is proof-based, i.e., it captures abstract formal properties of programs (e.g. safety and progress) rather than operational details. An algorithm for termination detection in diffusing computations... Read More

We have implemented a Prolog execution engine for the shared-database language Swarm extended with visualization capabilities. We call this execution engine SwarmExec. SwarmExec runs on a Macintosh Iifx under Advanced A.I. Systems' Prolog (AAIS) and communicates over an Ethernet connection with a Silicon Graphics Personal Iris which serves as a graphical engine and renders the visualizations. This paper describes the major design elements of SwarmExec. A basic familiarity with Swarm and its visualization extensions is assumed; the interested reader is referred to the referenced papers.

The term shared dataspace refers to the general class of programming languages in which the principal means of communication among the concurrent components of programs is a common, content-addressable data structure called a dataspace. In the programming language and artificial intelligence communities, there is considerable interest in such languages, e.g. logic-based languages, production rule systems, and the Linda language. However, these languages have not been the subject of extensive program verification research. This paper specifies a proof system for a shared dataspace programming notation called Swarm-- a program logic similar... Read More

This document summarizes usage and activities associated with the NCUBE computer system. The system is located within the Computer and Communications Research Center on the 3rd floor of Bryan Hall, School of Engineering and Applied Science, Washington University, St. Louis, Missouri. We begin with a brief review of the machine's hardware characteristics and then proceed to reviewing user activities.

In this paper z-transform theory is used to develop the discrete orthonormal wavelet transform for multidimensional signals. The tone is tutorial and expository. Some rudimentary knowledge of z-transforms and vector spaces is assumed. The wavelet transform of a signal consists of a sequence of inner products of a signal computed against the elements of a complete orthonormal set of basis vectors. the signal is recovered as a weighted sum of a basis vectors. This paper addresses the necessary and sufficient conditions that such a basis must respect. An algorithm for... Read More

This paper describes the modification made to the design of the Broadcast Translation Circuit based on test results from the first fabrication run. The document updates WUCS-89-52, which outlines the design of the BTC in full detail.

This paper describes the testing methodology for the Broadcast Translation Circuit. It covers logic simulation, timing simulation, and a single push-button test for the device. The document is intended to be a supplement to documents WUCS-89-52 and WUCS-90-19, which outline the design of the BTC in full details. The intent of a push-button test is to have a single test that causes the device to process every type of packets that it could receive. This would include various combination of RC and OP fields, a test that examines every table... Read More

This report documents the intent and use of a suite of programs for simulating the production of DNA restriction fragment data, as might come from the biological laboratory doing work in DNA mapping. This suite includes programs for (a) creating a random strand of DNA, (b) creating random clones given a strand of DNA, (c) taking a clone and applying a restriction enzyme to create restriction fragments, and (d) creating a nucleotide map of how the clones relate to one another within the original DNA strand. Besides this fundamental software,... Read More

We define the logically synchronous multicast problem, which imposes a natural and useful structure on message delivery order in an asynchronous system. In this problem, a computation proceeds by a sequence of multicasts, in which a process sends a message to some arbitrary subset of the processes, including itself. A logically synchronously multicast protocol must make it appear to every process as if each multicast occurs simultaneously at all participants of that multicast (sender plus receivers). Furthermore, if a process continually wishes to sends a message, it must eventually be... Read More

The importance of scientific visualization for both science and engineering endeavors has been well recognized. Televisualization becomes necessary because of the physical distribution of data, computation resources, and users involved in the visualization process. However, televisualization poses a number of challenges to the designers of communication protocols. A pipelined televisualization (PTV) model is proposed for efficient implementation of a class of visualization applications. Central to the proposed research is the development of a segment of streaming IPC (interprocess communication) mechanism in support of efficient pipelining across very high speed internetworks.... Read More

The problem of determining which events occur "between" two bounding events A and B in partially-ordered logical time is equivalent to being able to list, for a directed acyclic graph, the vertices on all paths with origin a and terminus b. We present four approaches to this problem, each progressively less memory-intensive. The two most promising of these approaches are examined in depth.

The problem of determining which events occur "between" two bounding events A and B in partially-ordered logical time is equivalent to being able to list, for a directed acyclic graph, the vertices on all paths with origin a and terminus b. Four approaches to this problem are presented, each exploiting more knowledge about this work's application domain and hence becoming progressively less memory intensive. The two most promising of these approaches are examined in depth.

A novel process algebra is presented; algebraic expressions specify delay-insensitive circuits in terms of voltage-level transitions on wires. The approach appears to have several advantages over traditional state-graph and production-rule based methods. The wealth of algebraic laws makes it possible to specify circuits concisely and facilitates the verification of designs. Individual components can be composed into circuits in which signals along internal wires are hidden from the environment.

The important feature of this work is the combination of minimizing a function with desirable properties, using the conjugate gradient method (cgm). The method has resulted in significant improvements for both easy and difficult training tasks. Two major problems slow the rate at which large back propagation neural networks (bpnns) can be taught. First is the linear convergence of gradient descent used by modified steepest descent method (msdm). Second is the abundance of saddle points which occur because of the minimization of the sum of squared errors. This work offers... Read More

This paper describes the Psi-decomposition of a signal, in which the signal is written as a weighted sum of certain elementary synthesizing functions. The set S of synthesizing functions consists of dilated and translated versions of two parent functions, which are concentrated in both the time and frequency domains. The weighting constant in the Psi-decomposition define a transform called the Phi-transform. The Phi-Transform of a signal captures both the frequency content and the temporal evolution of a non stationary signal. The Phil-transform is linear, continuous, and continuously invertible. The set... Read More

This report details research plans to extend work on hybrid deterministic parsing. The approach is hybrid in its combination of symbolic and sub-symbolic (connectionist) approaches. The research is investigating (1) new and more robust architectures for deterministic parsing which are hybrid mixtures of symbolic and sub-symbolic components, (2) combinations of syntax with lexical access and other components of natural language processing in order to determine how the distributed patterns of connectionism may enable better interfaces among these components, and (3) properties of the rules in the rule-based deterministic processing of... Read More

In the last two decades, mathematical theories have been helping computer scientists see, in a fresh light, problems in the area of programming methodology and solve these problems more efficiently and reliably than before. In this series of seminars we demonstrate the application of mathematics in parallel languages and programming.

In this paper we present a mathematical model for CSP-like language. This model handles both safety and liveness properties of "purely parallel" CSP processes, as well as CSP processes with internal machine states. A refinement order is defined in this model which is a combination of the refinement order in CSP's failure model and the refinement order for sequential programs. Finally, related work and applications are discussed.

This paper presents an overview of the design and development of a real-time (30 frames/sec) simulation testbed for evaluating and comparing image compression algorithms. The system was motivated by the need to visualize the performance of a novel compression algorithm when operating on moving pictures originating from "live" video sources. The simulation utilities are designed to exploit the parallelism of a Pixar Image Computer and high-throughput of a parallel disk assembly. The design of two key utilities are discussed: (1) A program to format precomputed four channel (RGBA) 256 X... Read More

This paper describes a novel method of character recognition targeted for extracting complex annotations found in engineering documents. The results of this work will make it possible to capture the information contained in documents used to support facilities management and manufacturing. The recognition problem is made difficult in part because characters and text may be expressed in arbitrary fonts and orientations. Our approach includes a novel incremental strategy based on the multi-scale representation of wavelet decompositions. Our approach is motivated by biological mechanisms of the human visual systems. Using wavelets... Read More

Previous matching algorithms have achieved high speeds through algorithm simplification and/or relied on custom hardware. The objective of our work has been the development a robust high-speed stereo matcher by exploiting parallel algorithms executing on general purpose SIMD machines. Our approach is based on several existing techniques dealing with the classification and evaluation of matches, the application of ordering constraints, and relaxation-based matching. The techniques have been integrated and reformulated in terms of parallel execution on the theoretical SIMD machine. Feasibility is demonstrated by implementation on a commercially available SIMD... Read More

A workshop on defeasible reasoning with specificity was held in under the Arch in St. Louis during April 1989, with support fro AAAI and McDonnell Douglas, and the assistance of Rockwell Science Center Palo Alto and the Department of Computer Science of Washington University. The document includes a report on the proceedings and parts of the workshop notes that can be distributed. These include the schedule, lists of participants, synopses of systems, and benchmark problems.

This project provides a good case study of expert system development with untrained experts over a short period of time. We describe the development of a working medical screening and diagnosis expert system for use at the Women, Infants and Children (WIC) clinics in Madison County, Illinois. The system was designed and implemented over the period of four months. A large number of knowledge acquisition techniques were employed, some of them customized in ways that greatly increased their effectiveness. This paper explores the development of THE WIC Advisor, from problem... Read More

A high-level area model of Benes and crossbar networks in a VLSI environment is presented. The areas of both networks are then compared for different design parameters. The results are also compared to those obtained by Franklin [Fr81] for banyan and crossbar networks. The geometric chip layout employs two metal layers for the interconnection paths. It is show that both Benes and crossbar grow in area as O(N)2, where N is the network size.

Quadratic energy minimization is the essence of certain connectionist models. We define high order connectionist models to support the minimization of high order energy functions and we prove that high order energy functions are equivalent to quadratic ones. We show that the standard quadratic models can minimize high order functions using additional hidden units and we demonstrate trade-offs of size (number of hidden units), order of the model, and fan-out. We prove an equivalence between the problem of satisfiability in propositional calculus and the problem of minimization of energy functions.... Read More

The arguments against centralized solutions focus on the performance bottleneck associated with a single central uniprocessor having a limited throughput and, possibly, a small number of ports. These limitations can be overcome to a large extent if the central processor is replaced by a modem SIMD (Single Instruction Multiple Data) machine. Several order of magnitude gains in parallelism are thus achievable while maintaining the logical simplicity of a centralized control. We call such a scheme parallel synchronous control (PSC). In this paper, we explore this approach by presenting a PSC... Read More

The Advanced Micro Devices TAXI chip set was chosen as the serial interface for the Fast Packet Switch. In order to fully understand the operation of the chip set, and in order to fully characterize the chip set's operation, several tests were performed using actual TAXI components. These tests included TAXI-to-TAXI tests and tests with optical data links. The operation of the asynchronous transmitter handshake was also investigated in detail. The results of these tests indicate that the TAXI chip set is well built and very reliable.

Technical reviews are an integral part of the software development process for any company concerned with software quality. This paper is neither a survey nor a comparative study of existing approaches but an attempt to reexamine the technical review process from a new perspective, the corporate culture. It is the contention of this paper that technically sound methods are effective only in a climate where (1) reviews are an integral part of the local culture and (2) there is no clear understanding of the kinds of technical and organizational needs... Read More

The term shared dataspace refers to the general class of models and languages in which the principal means of communication is a common, content-addressable data structure called a dataspace. Swarm is a simple language we have used as a vehicle for the investigation of the shared dataspace approach to concurrent computation. It is the first shared dataspace language to have an associated assertional-style proof system. An important feature of Swarm is its ability to bring a variety of programming paradigms under a single, unified model. In a series of related... Read More

Swarm is a computational model which extends UNITY in three important ways: (1) UNITY's fixed set of variables is replaced by an unbounded set of tuples which are addressed by content rather than by name; (2) UNITY's static set of statements is replaced by a dynamic set of transactions; and (3) UNITY's static II-composition is augmented by dynamic coupling of transactions into synchronic groups. This paper overviews the Swarm model, introduced the synchronic group concept, and illustrates their use in the expression of dynamically structured programs. A UNITY-style programming logic... Read More

This paper describes the Axon host-network interface architecture. The Axon project is investigating an integrated design of host architecture, operating systems, and communications protocols to allow applications to utilize the high bandwidth provided by the next generation of communications networks. The Axon host architecture and network interface is designed to provide a high bandwidth low latency path directly between the network and host memory. A pipelined communications processor (CMP) serves as a network interface with direct access to host memory, capable of delivering bandwidth in excess of 1 Gbps to... Read More

This paper provides a method of analyzing the queueing behavior of switching networks constructed from switches that employ shared buffering or parallel bypass input buffering. It extends that queuing models first introduced by Jenq and later generalized by Szymanski and Shaikh to handle these classes of networks. Our analysis explicitly models the state of an entire switch and infers information about the distribution of packets associated with particular inputs or outputs when needed. Earlier analyses of networks constructed from switches using input buffering attempt to infer the state of a... Read More

Asynchronous Transfer Mode (ATM) has been expected to be the basis for the next generation communication networks. The point of queuing analysis for ATM networks is to evaluate the behavior of bursty traffic. Periodicity of the traffic is another significant characteristic of some applications, and is difficult to treat by means of evaluating the queuing theories. This report describes between arriving and departing traffic. The results obtained by this method include packet loss rate and queue length distribution. And it is shown that periodic bursty traffic has, in general, moderate... Read More

This paper describes the design of the PP3 packet processor chip. PP3 is one of the four component chips in a packet processor used in the high speed broadcast packet switching network [Tu88]. Together with the other three component chips, PP3 provides the interface between the fiber optic links and the switch fabric. PP3 in currently being fabricated in 2 μm CMOS technology.

The performance of a network subject to either state dependent or state independent flow control is investigated. In the state dependent case, the flow control policy is a function of the total number of packets for which the controller has not yet received an acknowledgment. In this case it is shown that the optimal flow control is a sliding window mechanism. The effect of the delayed feedback on the network performance as well as the size of the window are studied. The state independent optimal rate is also derived. The... Read More

We investigate the dynamical behavior of a decentralized network that is shared by users, each trying to achieve its own objectives.

In this paper a resource allocation algorithm is presented for Markovian queueing networks operating under state dependent routing and flow control. The state of the network is described by the total number of packets in the network. In addition, in this paper, a new proof based on feasible direction techniques is presented for a classical result concerning Jacksonian networks. Specifically, the result states that for a Jacksonian network whose Norton equivalent is a concave increasing function with respect to the number of packets in the network, the optimal flow control... Read More

The decentralized flow control problem for an open multiclass BCMP network is studied. The power based optimization criterion is employed for the derivation of the optimal flow control for each of the network's users. It is shown that that optimal arrival rates correspond to the unique Nash equilibrium point of a noncooperative game problem. Asynchronous algorithms are presented for the computation of the Nash equilibrium point of the network. Among them, the nonlinear Gauss-Seidel algorithms is distinguished for its robustness and speed of convergence.

In this paper, the problem of finding the decentralized flow control of a BCMP network is investigated. The packets of each of the users correspond to different classes of customers. The servers in the network are exponential and serve packets with FIFO policy. Each network user operates with either a state-dependent arrival rate (i.e. an arrival rate which depends upon the number of the user's packets that have not yet been acknowledged) or a state-dependent arrival rate (which the user chooses). The decentralized flow control problem is formulated udder two... Read More

Load balancing algorithms for Jacksonian networks are derived. The state of the network is represented by the total number of packets for which the source has not yet received an acknowledgement, The networks studied are subject to the state independent routing and, state dependent and state independent flow control. The objective is to maximize the throughput of the network so that the end-to-end expected packet time delay does not exceed an upper bound. The optimal flow control is shown to be a window type, while the routing policy balances the... Read More

The problem of finding the optimal routing and flow control of a single-class Markovian network under a suitable optimization criterion is analyzed. It is proven that, if complete information about the state of the network is made available to the network controller, the optimal state dependent routing is essentially deterministic, and the optimal flow control is of a generalized window type. An iterative linear programming algorithm is given for the derivation of the optimal routing and flow control policy.

In this paper, we present a rigorous treatment of so-called logical constants, which are used to relate the values of program variables between the precondition and the postcondition of a program. In order to do so, we generalize the latest proof rule for procedures and give a new definition for the specification statement. We show that the specification statement with this definition is the greatest lower bound of all its implementations under the usual refinement ordering and that it is A-distributive. We also demonstrate that a previous treatment of logical... Read More

Because medical data have complex temporal features, special techniques are required for storing, retrieving, and displaying clinical data from electronic databases. One significant problem caused by the temporal nature of medical data has been called the temporal granularity problem. The temporal granularity problem is said to occur when the set of facts relevant to a specific problem changes as the time scale changes. We argue that what is needed to deal with changes in the relevant time scale are temporal granularity heuristics. One heuristic that we have explored is that,... Read More

Two current research projects within the Medical Informatics Group are described. The first, the Diabetes Data Management Project, has as its major goal the effective analysis, display, and summarization of information relevant to the care of insulin-dependent diabetics. These goals are achieved through the use of quantitative and qualitative modeling techniques, object-oriented graphical display methods, and natural language generation programs. The second research activity, the Hypertext Medical Handbook Project, emphasizes many aspects of electronic publishing and biomedical communication. In particular, the project explores machine-assisted information retrieval by combining user feedback... Read More

The practice of medicine is an information rich activity, yet information systems have had melancholy history as aids to decision making physicians. Some of the reasons for this lack of acceptance are examined along with the potential that emerging technology may have for the acceptance of a future physician’s workstation. The use of information technology in the practice of medicine seems inevitable, but social impediments to its use may delay its widespread introduction for a decade or more. In the meantime experiments which document the existence or absence of the... Read More

An "electronic viewbox" is described that has been designed to meet the demand for a modestly priced soft-copy display for radiology. Issues associated with spatial resolution, intensity resolution, image magnification, user interface, digital communications and possible applications are discussed.

Visualization, defined as the graphical representation of symbolic objects and processes, is recognized as an important tool to aid human understanding. This is particularly true in the area of program visualization, which uses images to illustrate the execution of programs. This proposal describes research to investigate the visualization of concurrent computations. The research has two major goals: the development of a model of visualization suitable for concurrent computations, and the development of methodology for constructing visualizations. The proposed visualization model treats visualization as a function from the state of the... Read More

The term shared dataspace refers to the general class of programming languages in which the principal means of communication among the concurrent components of programs is a common, content-addressable data structure called a dataspace. In the programming language and artificial intelligence communities, there is considerable interest in such languages, e.g., logic-based languages, production rule systems, and the Linda language. However, these languages have not been the subject extensive program verification research. This paper specifies a proof system for the shared dataspace language Swarm - a proof system similar in style... Read More

Rule-based programs used in mission- and safety-critical applications need to be shown to be free of hazards. This paper discusses formal proof-techniques which promise to assist designers in this task. In this paper we show that the shared dataspace language Swarm has many key features in common with rule-based languages. We outline an assertional programming logic for Swarm programs and use the logic to reason about the correctness of a simple program. This logic is a suitable foundation for the development of techniques specific to present and future rule-based languages.

We propose to address problems related to the problem of Natural Language Processing. Neural networks approach will be used in attaching these problems. In this proposal a number of problems are considered: parsing of ill-formed sentences in addition to well-formed sentences, resolutions of some lexical ambiguities using syntactic context, and parsing of sentences sequentially over an input stream which is unbounded in length. Two network training approaches will be examined. Deductive training, based on grammar rules, and inductive training, based on sentence processing will be fully investigated. Comparisons with each... Read More

This paper attempts to provide a perspective from which to develop a more complete theory of information retrieval from hypertext documents. Viewing hypertexts as large information spaces, we compare two general classes of navigation methods, classes we call local and global. We argue that global methods necessitate some form of “index space” conceptually separate from the hypertext “document space”. We note that the architectures of both spaces effect the ease with which one can apply various information retrieval algorithms. We identify a number of different index space and document space... Read More

This paper represents a beginning development of a parallel truth maintenance system to interact with a parallel inference engine. We present a solution which performs status assignments in parallel to belief nodes in the Reason Maintenance System (RMS) presented by [3],[4]. We examine a previously described algorithms by [7] which fails to correctly detect termination of the status assignments. Under Petrie's algorithm, termination may go undetected an in certain circumstances (namely the existence of an unsatisfiable circularity) a false detection may occur. We present an algorithm that corrects these problems.

A truth maintenance system (TMS) is an AI system used to monitor consistency of information in a knowledge base. A TMS may be necessary when non-monotonic reasoning is used since incorrect assumptions can lead to contradictory conclusions. The Reason Maintenance System (RMS), a specific TMS first described by Doyle [5],[6], is used along with an inference engine (IE), or problem solver, to maintain a consistent set of beliefs and inferences. We have developed a parallel version of the RMS for correctly assigning IN or OUT states to each believe node... Read More

Production systems, also called rule-based systems, are very useful in automating certain human expert tasks, but the current technology exhibits many problems. We believe that parallelism is difficult to exploit in production system programs for two reasons. First, the original serial programs are designed with a priori knowledge of an explicit global control mechanism which must be simulated for correct execution in parallel. The second reason for the difficulty is that no formal language exists in which to express these programs and no verification techniques are utilized to prove properties... Read More

This paper describes the design of a Broadcast Translation Circuit chip. The Broadcast Translation Circuit (BTC) provides unique addresses for each of the copies of a broadcast packet replicated by the copy network in a Broadcast Packet Switch [Tu85], [Tu86]. During a packet cycle or epoch, a packet is then passed on to the routing or distribution network. This chip has been fabricated in 2.0 μm CMOS technology.

This report describes my implementation of a parallel iterative-deepening A* search algorithm on a NCUBE parallel computer. I present a detailed description of the algorithm, followed by a discussion of its theoretical performance. The actual performance of my implementation is compared to the theoretical model, and a summary of the results is presented.

Tax law is a particular application well-suited for an expert system because of the large among of knowledge and the many variables involved. The following presents the results of implementing a small portion of tax code, with a brief look at whether or not it can be fully recreated in an accurate system with an acceptable response time. The actual prototype implementation has been done using the expert shell NEXPERT, making use of the IF/THEN rule construct which seems to fall naturally from the tax code.

This paper proposes a new problem, which we call the Dynamic Steiner Tree Problem. This is related to multipoint connection routing in communications networks, where the set of nodes to be connected changes over time. This problem can be divided into two cases, one in which rearrangement of existing routes is not allowed and a second in which rearrangement is allowed. In the first case, we show that there is no algorithm whose worst error ratio is less than 1/2 log n where n is the number of nodes to... Read More

Temporal concepts are critical is medical therapy-planning. If given early enough, specific therapeutic choices may abort or suppress evolving undesired changes in a patient’s clinical status. Effective medical decision making demands recognition and interpretation of complex temporal changes that permeate the medical record. This paper presents a methodology for representing and using medical knowledge about temporal relationships to infer the presence of clinically relevant events, and describes a program, called TOPAZ, that uses this methodology to generate a narrative summary of such events. A unique feature of TOPAZ is the... Read More

Backpropagation as learning rule is often confining to multi-layer Perceptions or layered feedforward networks, in which there are no lateral connections among the units of the same layer nor any connections bypassing intermediate layers. We prove algebraically that these restrictions are not necessary, i.e. backpropagation is applicable to any acyclic neural network. Our proof is based on a new formulation of backpropagation called an Acyclic Neural Network (ANN). In ANN, a net is defined as a partially ordered set of processing units where every unit may receive an input value... Read More

The present work investigates the significance of arithmetic precision in neural network simulation. Noting that a biological brain consists of a large number of cells of low precision, we try to answer the question: With a fixed size of memory and CPU cycles available for simulation, does a larger sized net with less precision perform better than smaller sized one with higher precision? We evaluate the merits and demerits of using low precision integer arithmetic in simulating backpropagation networks. Two identical backpropagation simulators, ibp and fbp, were constructed on Mac... Read More

This paper describes how a signal can be written as a weighted sum of certain "elementary" synthesizing functions, which are the dilated and translated versions of a single parent function. The weighting constants in this sum define a transform of the signal. This is much like Fourier analysis except that a wide choice is permitted in the selection of a set of synthesizing functions. Moreover, the permitted sets of synthesizing functions are not orthogonal. It is shown that the transform described here captures both the frequency content, and the temporal... Read More

The processing of Natural Language is, at the same time, natural symbolic and naturally symbolic and naturally sub-symbolic. It is symbolic because ultimately symbols play a critical role. Writing systems, for example, owe their existence to the symbolic nature of language. It is also sub-symbolic because of the nature of speech, the fuzziness of concepts, and the high degree of parallelism that is difficult to explain as a purely symbolic phenomenon. This report details a set of experiments which support the claim that Natural Language can be syntactically processed in... Read More

The goal of stereo vision is the recovery of depth information from the relative lateral displacements in the positions of objects within a pair of images taken from slightly differing viewpoints. While recent stereo matching techniques have yielded improvements in reliability and speed, most of these algorithms fall short of the real-time stereo matching requirements for navigation systems, robot vision, machine inspection, and other areas computer vision where rapid response is critical. Traditionally, matching algorithms have achieved high speeds through algorithm simplification and/or relied on custom hardware. The objective of... Read More

There are three theses here: • Non-computationally conceived inference merely expands notation. This includes induction as well as deduction, and thus both deserve the adjective non-ampliative. Deriving entailments merely expands shorthand. All of the familiar formalisms for reasoning do just this. • There now exist examples of formalism for reasoning that do something else. They are deliberative, and to say in what way they are deliberative requires reference to the process through which they compute their entailments. • The original ampliative/non-ampliative terminology best survives as referring to this new distinction.... Read More

This paper attempts four things. It demonstrates the possibility of accounting for Russell-style and Clark-style analogical reasoning in an existing framework for statistical reasoning. It critically reviews the proposals made by Clark for defeasible analogical reasoning and shows how they can be understood better simply as defeasible reasoning. It argues that generalization from the single case is not as desirable as projection from the single case; the difference has to do with the defeasibility control strategy for statistical reasoning limited to a small number of cases.

In two recent papers, I have proposed a description of decision analysis that differs from the Bayesian picture painted by Savage, Jeffrey and other classic authors. Response to this view have been either overly enthusiastic or unduly pessimistic. In this paper I try to place the idea in its proper place, which must be somewhere in between. Looking at decision analysis as defeasible reasoning produces a framework in which planning and decision theory can be integrated, but work on the details has barely begun. It also produces a framework in... Read More

This technical report consists of three chapters from a larger manuscript that was a finalist in the 1988 Journal of Philosophy Johnsonian competition. These three chapters together represent a revised version of a paper that has been circulating under the title "Defeat Among Arguments II" since January 1988. "Defeat Among Arguments" updates my Computational Intelligence paper of 1987, which represented a novel way of formalizing defeasible reasoning, based on resolving competing arguments. "The Yale Shooting Problem" updates my Cognitive Science paper of 1987, and attempts a rebuttal of Hanks and... Read More

This paper investigates a different foundation for decision theory in which successive model refinement is central. The idea is to modify utility so that it can sometimes be calculated for an outcome without considering all the relevant properties that can be proved of the outcome, and without considering the utilities of its children. We build partially ordered heuristic utility functions. We treat the analysis of personal decision trees like heuristic search of game trees (taking expectations instead of doing minimax). Analysis of decision then becomes a process of constructing and... Read More

CCRC implements a subset of Kyburg's rules for statistical inference. The system states from 1961 and is briefly described in "The Reference Class," (H. Kyburg Philosophy of Science 50, 1982). Consult the paper "Computing Reference Classes" (R. Loui, in Kanal, L. and Lemmer, J., Uncertainty in AI, v.1, North-Holland 1987) for a precis of the ideas underlying this program. This document is only the skeleton of a manual. It is designed to get the novice on the program as quickly as possible, and to provide some guidance for advanced questions.... Read More

We have proposed a very high speed internet (VHSI) abstraction that can provide a variable grade service with performance guarantees on top of diverse networks. An important component of the VHSI abstraction is a novel Multipoint Congram-oriented High Performance Internet Protocol (MCHIP). Features of this protocol include support for multipoint communication, the congram as the service primitive which incorporates strengths of both connection and datagram approaches, ability to provide variable grade of service with performance guarantees, and suitability for high speed implementation. This document introduces the VHSI abstraction and then... Read More

This paper generalized known results for nonblocking distribution networks (also known as generalized connection networks) to the multirate environment, where different user connections share a switch's internal data paths in arbitrary fractions of the total capacity. In particular, we derived conditions under which networks due to Ofman and Thompson, Pippenger, and Turner lead to multirate distribution networks. Our results include both rearrangeable multirate networks exceeds that of the corresponding space division network by a log log factor while the complexity of the wide sense nonblocking networks in within a factor... Read More

This paper describes a research effort concerned with the design of the next generation of internet architecture, which has been necessitated by two emerging trends. First, there will be at least a few orders of magnitude increase in data rates of communication networks in the next few years. For example, researchers are already prototyping networks with data rates of up to a few hundred Mbps, and are planning networks with data rates up to a few Gbps. Second, researchers from all disciplines of science, engineering, and humanities plan to use... Read More

The video link concept is a proposed method for providing video codec service to the customer base in a manner similar to the way phone service is provided today. Three possible implementations are low volume solutions that could be used to test market the video link concepts. The third method, which is technically superior to the first two, would only be economically feasible in a high volume implementation.

Swarm is a computational model which extends the UNITY-model in three important ways: (1) UNITY's fixed set of variables is replaced by an unbounded set of tuples which are addressed by content rather than by name; (2) UNITY's static set of statements is replaced by a dynamic set of transactions; and (3) UNITY's static ||-composition is augmented by dynamic coupling of transactions into synchronic groups. Taking advantage of the similarities of the Swarm and UNITY computational models, we have developed a programming logic for Swarm and UNITY computational models, we... Read More

The technical report presents a succinct description of the Justification Finder (if). The system if is a practical implementation of the theoretical ideas introduced elsewhere (see the technical report "On the Logic of Defeasible Reasoning", G Simari, WUCS-89-12). It is used to explore and validate those ideas. The system provides support for defeasible reasoning in a Prolog environment. The complete Prolog language is available and only a few new predicates are introduced extending the reserved words of the language. We will present the theoretical underpinnings of the system in a... Read More

We present a mathematical approach to defeasible reasoning. This approach is based on the notion of specificity introduced by Poole and the theory of warrant presented by Pollock. We combine the ideas of the two. This main contribution of this paper is a precise well-defined system which exhibits correct behavior when applied to the benchmark examples in the literature. We prove that an order relation can be introduced among equivalence classes under the equi-specificity relation. We also prove a theorem that ensures the termination of the process of finding the... Read More

There are two complementary trends in the computer and communications fields. Increasing processor power and memory availability allow more demanding applications, such as scientific visualizations and imaging. Advances in network performance and functionality have the potential for supporting applications requiring high bandwidth communications. However, the bottleneck is increasingly in the host-network interface, and thus the ability to deliver high performance communications capability to applications has not kept up with the advance in computer and network speed. We have proposed a new architecture that meets these challenges, called Axon. The Axon... Read More

There are two complementary trends in the computer and communication fields. Increasing processor power and memory availability allow more demanding applications, such as scientific visualization and imaging. Advances in network performance and functionality have the potential for supporting programs requiring high bandwidth and predictable performance. However, the bottleneck in increasingly in the host-network interface, and thus the ability to deliver high performance communication capability to applications has not kept up with the advances in computer and network speed. We have proposed a new architecture that meets these challenges called Axon,... Read More

This paper describes the application-oriented lightweight transport protocol for object transfer (ALTP-OT) in the Axon host communication architecture for distributed applications. The Axon Project is investigating an integrated design of host architecture, operating systems, and communication protocols to allow the utilization of the high band-width provided by the next generation of communication networks. ALTP-OT provides the end-to-end transport of segment and message objects for interprocess communication across a very high speed internetwork, supporting demanding applications such as scientific visualization and imaging. ALTP-OT uses rate-based flow control specifically oriented to the... Read More

This paper describes the design of network virtual storage (NVS) in the Axon host communications architecture for distributed applications. The Axon project is investigating an integrated design of host architecture, operating systems, and communications protocols to allow applications to utilize the high bandwidth provided by the next generation of communications networks. NVS extends segmented paged virtual storage management and address translation mechanisms to include segments located across an internetwork. This provides the ability to efficiently use the shared memory paradigm in non-local environments, as well as the support for a... Read More

The Mitsubishi XT-1000 is a flat visual terminal which has a transparent touch tablet with a 640x400 dot liquid crystal display (LCD). The XT-1000 is touch-sensitive, having the capability of selecting a single pixel through any blunt, pointed object. SiliconPaint is a graphics program for the XT-1000. Many of its features are similar to the features of MacPaint for Macintosh. These features include drawing figures, manipulating files, editing, entering text, and filling shapes with patterns. Many operations are executed using a pen on the surface of the XT-1000, though some,... Read More

In this paper we consider several approximation algorithms for the Steiner tree problem in an attempt to find one whose worst case performance is better than two times optimal. We first examine Rayward-Smith's algorithm to gain insight into why it has worst case performance no better than two. Based on these ideas we propose several new algorithms (approximation schemes). We eliminate from further consideration those which we have bene able to showed have worst case performance that is still no better than two. Then we conjecture that one of these... Read More

Adaptive histogram equalization (ahe) is a method for adaptive contrast enhancement of digital images propped by Pizer et. Al.. It has the properties that it is an automatic, reproducible method for the simultaneous viewing of contrast within a digital image with a large dynamic range. Recent experiments have show that in specific cases, there is no significant difference in the ability of ahe and linear intensity windowing to display grey-scale contrast. More recently, Pizer et al. have proposed a variant of ahe which limits the allowed contrast enhancement of the... Read More

This paper describes the design of the Packet Buffer Chip. Packet Buffers are FIFO queues used for buffering packets and synchronizing a Switch Fabric (SF) and its associated Fiber Optic Links (FOLS) in the Broadcast Packet Switching Network. This chip will be fabricated in 2.0 UM CMOS technology.

Over the last few years, a number of research groups have made considerable progress on the design of high speed networks- on the order of a few hundred Mbps to the few Gbps. The emphasis of this work has been on the design of packet switches and on the design of network access protocols. However, this work has not yet addressed the internetworking and transport level issues in the high speed internet. As part of our effort on the design of VHSI model, we considered the appropriateness of recently proposed... Read More