Technical Reports and MS Project Reports

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.