MS-CIS-93-01 (LOGIC & COMPUTATION 54)

On the Correspondence Between Proofs and l-Terms

Jean Gallier

The correspondence between natural deduction proofs and l-terms is presented and discussed. A variant of the reducibility method is presented, and a general theorem for establishing properties of typed (first-order) l-terms is proved. As a corollary, we obtain a simple proof of the Church-rosser property, and of the strong normalization property, for the typed l-calculus associated with the systenm of (intuitionistic) first-order natural deduction, including all the connectors ®, x, +, ",$ and ^ (falsity) (with or without h-like rules).

MS-CIS-93-02 (GRASP LAB 341)

Minimax Estimation Of A Bounded Location Parameter Using Multilevel Loss (Dissertation)

Robert F. Kennedy

This dissertation considers minimax estimation under multilevel loss of a bounded location parameter qÎ Q for an arbitrary symmetric distribution F(z-q) with monotone likelihood ratio. The parameter space is restricted to a symmetric interval Q = [-d,d]. The multilevel loss function is a generalization of the zero-one loss function, and can be represented by a linear combination of component zero-one loss functions. The problem is considered using two multilevel loss functions: zero-alpha-one loss; and n-level loss. Minimax solutions under multilevel loss are shown the be restricted to a class of monotone, antisymmetric decision rules with range |d| £ [0, d - e₁]. The geometry of the zero-alpha-one problems is analyzed to present the overall picture and categorize the possible cases. From this analysis, the complete problem is divided into three cases.

A solution technique is developed which allows the problem to be represented by a finite-dimensional linear-algegraic expression. The complete solution to the n-level loss problem is presented for the simplest case (Case 1), which is defined by d/2 £ e₁ < e_n < d. The truncated MLE is shown to be a global minimax rule for a nondegenerate symmetric Case 1 problem when sufficient conditions are satisfied. The solution is obtained by showing that the truncated MLE is an almost equalizer rule which is Bayes with respect to a least favorable peior. Thge truncated MLE is a member of class \cal C of continuous peicewise-linear decision rules with regions of either zero or unit slope. Rules from this class are Bayes with respect to a corresponding class of priors which have piecewise constnat densities. the equations which determine a least favorable peior are derived and presented. These results are shown to be valid for any symmetric distribution with monotone likelihood ration.

The Case 2 problem, which is constrained by d/2 £ e₁ < d £ e₂ < 2d- e₁, is analyzed using zero-alpha-one loss. A solution is obtained for a nominal Case 2 problem by modifying the technique used for the Case 1 problem. A minimax rule is shown to be discontinuous Bayes rule which equalizes the risk on a subset ofQ. The Case 3 problem is analyzed using a simplified form of multilevel loss which has minimax solution in the class \cal C when certain constraints on the loss function and distribution are satisfied. A method to approximate a minimax rule for an arbitrary continuous bowl-shaped loss function is developed using this same simplified form of multilevel loss.

Finally, the behavior of minimax rules and least favorable priors is examined for various shapes of loss functions and sampling distributions. Evidence is presented which suggest that when the scale parameter of the distribution approaches zero, the minimax rules approach the truncated MLE, and the envelope of theleast favorable priors approach the minimal Fisher information prior independent of the shape of the loss function and shope of the distribution.

MS-CIS-93-03 (GRAPHICS LAB 52)

A Gathering and Shooting Progressive Refinement Radiosity Method

Min-Zhi Shao, Norman I. Badler

This paper presents a gathering and shooting progressive refinement radiosity method. Our method integrates the iterative process of light energy gathering used in the standard full matrix method and the iterative process of light energy shooting used in the conventional progressive refinement method. As usual, in each iteration, the algorithm first selects the patch which holds the maximum unprocessed light energy in the environment as the shooting patch. But before the shooting process is activated, a light energy gathering process takes place. In this gathering process, the amount of the unprocessed light energy which is supposed to be shot to the current shooting patch from the rest of the environment in later iterations is pre-accumulated. In general, this extra amount of gathered light energy is far from trivial since it comes from every patch in the environment from which the current shooting patch can be seen. However, with the reciprocity relationship for form-factors, still only one hemi-cube of the form-factors is needed in each iteration step. Based on a concise record of the history of the unprocessed light energy distribution in the environment, a new progressive refinement algorithm with revised gathering and shooting procedures is then proposed. With little additional computation and memory usage compared to the conventional progressive refinement radiosity method, a solid convergence speedup is achieved. This gathering and shooting approach extends the capability of the radiosity method in accurate and efficient simulation of the global illuminations of complex environments.

MS-CIS-93-04 (LINC LAB 243)

VP Ellipsis and Semantic Identity

Daniel Hardt

While it is generally agreed that an elliptical Verb Phrase must be identitical to its antecedent, the precise formulation of the identity condition is controversial. I present a semantic identity condition on VP ellipsis: the elided VP must have the same meaning as its antecedent. I argue that a semantic identity condition is superior to a syntactic condition on both empirical and theoretical grounds. In addition, I show that the proposed condition differs significantly from previously proposed semantic conditions, in that other approaches do not take into account the dynamic nature of semantic representation.

MS-CIS-93-05 (LINC 244)

An Algorithm for VP Ellipsis

Daniel Hardt

An algorithm is proposed to determine antecedents for VP ellipsis. The algorithm eliminates impossible antecedents, and then imposes a preference ordering on possible antecedents. The algorithm performs with 94% accuracy on a set of 304 examples of VP ellipsis collected from the Brown Corpus. The problem of determining antecedents for VP ellipsis has received little attention in the literature, and it is shown that the current proposal is a significant improvement over alternative approaches.

MS-CIS-93-06 (LINC LAB 245)

VP Ellipsis and Contextual Interpretation

Daniel Hardt

A computational account of VP ellipsis is described, in which VP's are represented in the discourse model as contextually dependent semantic objects. It is argued that this approach can handle examples that are not allowed by alternative accounts. An implementation is defined in terms of extensions to the Incremental Interpretation System. The treatment of VP ellipsis is analogous to that of pronominal anaphora. It is suggested that the recency and salience constraints commonly thought to apply to pronominal anaphora might apply in a similar way to VP ellipsis.

MS-CIS-93-07 (LOGIC & COMPUTATION 55) (DISTRIBUTED SYSTEMS LAB 13)

A State Minimization Algorithm for Communicating State Machines with Arbitrary Data Space

Inhye Kang, Insup Lee

A fundamental issue in the automated analysis of communicating systems is the efficient generation of the reachable state space. Since it is not possible to generate all the reachable states of a system with an infinite number of states, we need a way to combine sets of states. In this paper, we describe communicating state machines with data variables, which we use to specify concurrent systems. We then present an algorithm that constructs the minimal reachability graph of a labeled transition system with infinite data values. Our algorithm clusters a set of states that are bisimilar into an equivalent class. We include an example to illustrate our algorithm and identify a set of sufficient conditions that guarantees the termination of the algorithm.

MS-CIS-93-08 (LOGIC & COMPUTATION 56) (DISTRIBUTED SYSTEMS LAB 14)

A Process Algebraic Approach To The Specification and Analysis of Resource-Bound Real-time Systems

Insup Lee (University of Pennsylvania), Patrice Br ^'e mond-Gr^'e goire (University of Pennsylvania), Richard Gerber (University of Maryland)

There has recently been significant progress in the development of timed process algebras for the specification and analysis of real-time systems. This paper describes a timed process algebra called ACSR. ACSR supports synchronous timed actions and asynchronous instantaneous events. Timed actions are used to represent the usage of resources and to model the passage of time. Events are used to capture synchronization between processes. To be able to accurately specify real systems, ACSR supports a notion of priority that can be used to arbitrate among timed actions competing for the use of resources and among events that are ready for synchronization. The paper also includes a brief overview of other timed process algebras and discusses similarities and differences between them and ACSR.

MS-CIS-93-09 (GRASP LAB 342)

Fast Parallel Deterministic and Randomized Algorithms for Model Checking

Insup Lee, Sanguthevar Rajasekaran

Model checking is a powerful technique for verification of concurrent systems. One of the potential problems with this technique is state space explosion. There are two ways in which one could cope with state explosion: reducing the search space and searching less space. Most of the existing algorithms are based on the first approach.

One of the sccuessful approach for reducing search space uses Binary Decision Diagrames (BDDs) to represent the system. Systems with a large number of states (of the order of 5 x 10²⁰) have been thus verified. But there are limitations to this heuristic approach. Even systems of reasonable complexity have many more states. Also, the BDD apprach might fail even on some simple systems. In this paper we propose the use of parallelism to extend the applicability of BDDs in model checking. In particular we present very fast algorithms for model checking the employ BDDs. The algorithms presented are much faster than the best known previous algorithms. We also describe searching less space as an attractive approach to model checking. In this paper we demonstrate the power of this approach. We also suggest the use of randomization in the design of model checking algorithms.

MS-CIS-93-10 (GRASP LAB 343)

Selection, Routing and Sorting On The Star Graph

Sanguthevar Rajasekaran, David S.L. Wei

We consider the problems of selection, routing and sorting on an $n$-star graph (with n! nodes), an interconnection network which has been proven to possess many special properties. We identify a tree like subgraphc (which we call as a '(k, 1, k) chain network') of the star graph which enables us to design efficient algorithms for the above mentioned problems.

We present an algorithm that performs a sequence of n prefix computations in O(n²) time. This algorithm is used as a subroutine in our other algorithms. In additonal we offer an efficient deterministic sorting algorithm that runs in O(n³ log n)/2 steps. Though an algorithm with the same time bound has been proposed before, our algorithm is very simple and is based on a different approach. We also show that sorting can be performed on the n star graph in time O(n³) and that selection of a set of uniformaly distributed n keys can be performed in O(n²) time with high probability. Finally, we also present a deterministic (non oblivious) routing algorithm that realizes any permutation in O(n³) steps on the n-star graph.

There exists an algorithm in the literature that can perform a single prefix computation in O(n logn) time. The best known previous algorithm for sorting has a run time of O(n³ lg n) and is deterministic. To our knowledge, the problem of selection has not been considered before on the star graph.

MS-CIS-93-11 (GRASP LAB 344) (DISTRIBUTED SYSTEMS LAB 15)

Gigabit Telerobitcis: Applying Advanced Information Infrastructure

Ruzena Bajcsy, David J. Farber, Richard P. Paul, Jonathan M. Smith

Advanced manufacturing concepts such as ``Virtual Factories'' use an information infrastructure to tie together changing groups of specialized facilites to agile manufacturing systems. A necessary element of such systems is the ability to teleoperate machines, for example telerobotic systems with full-capability sensory feeback loops. We have identified three network advances needed for splitting robotic control from robotic function: increased bandwidth, decreased error rates, and support for isochronous traffic. These features are available in the Gigabit networks under the development at Penn and elsewhere.

A number of key research questions are posed by gigabity telerobotics. There are issues in network topology, robot control and distributed system software, packaging and transport of sensory data (including wide-area transport), and performance implications of architectural choices using measures such as cost, response time, and network utilization.

We propose the explore these question experimentally in a joint research effort combining the Distributed Systems Laboratory and the General Robotics and Sensory Perception (GRASP) Laboratory at the University of Pennsylvania. The proposed experiments should provide important early results. A detailed research program is described.

MS-CIS-93-12 (GRAPHICS LAB 54)

A Kinematic Generalization of Rotoscoped Human Walking

Hyeongseok Ko, Norman I. Badler

The most prominent problems in utilizing the rotoscopy data for human walking animation can be summarized as preservation of the original motion characteristics in the generalization process and constraint satisfaction. Generalization is the process of producing the step of an arbitrary body and step length from the original measured step of one particular subject and step length. If we lose much of the original style in the generalization, it would be meaningless to use the measured data. We present a generalization technique that keeps the original spatial motion characteristics as much as possible. Two types of generalization are considered. One is the anthropometry generalization, which handles the non-uniform segment length ratio differences between the two bodies. The other is the step length generalization, which changes the steps to different step lengths of the same subject. These two generalizations are combined together to generate a step of arbitrary subject and step length. The constraint satisfaction is enforced within the generalization process.

MS-CIS-93-13 (GRAPHICS LAB 53)

Curved Path Human Locomotion that Handles Anthropometrical Variety

Hyeongseok Ko, Norman I. Badler

Human locomotion simulation along a curved path is presented. The process adds a small constant cost (O(1)) to any pre-existing straight line walking algorithm. The input curve is processed by the foot print generator to produce a foot print sequence. The resulting sequence is scanned by the walking motion generator that actually generates the poses of the walking that realizes such foot prints. The two primitives INITIALISE_STEP and ADVANCE_STEP are used for walking motion generation. INITIALIZE_STEP is activated with the input parameters walker, next_foot_print , left_or_right, and step_duration, just before each step to precompute the trajectories of the center of the body and the ankles. ADVANCE_STEP is called with a normalized time to generate the actual pose at that moment. The normalized time is a logical time, covering zero to one during a complete step.

MS-CIS-93-14 (LOGIC & COMPUTATION 57)

Inductive, Projective and Retractive Types

Brian T. Howard

We give an analysis of classes of recursive types by presenting two extensions of the simply-typed lambda calculus. The first language only allows recursive types with built-in principles of well-founded induction, while the second allows more general recursive types which permit non-terminating computations. We discuss the expressive power of the languages, examine the properties of reduction-based operational semantics for them, and give examples of their use in expressing iteration over large ordinals and in simulating both call-by-name and call-by-value versions of the untyped lambda calculus. The motivations for this work come from category theoretic models.

MS-CIS-93-15 (GRASP LAB 344)

Operator Interaction and Teleprogramming for Subsea Manipulation

Craig Sayers, Richard Paul, Max Mintz

The teleprogramming paradigm has been proposed as a means to efficiently perform teleoperation in the subsea environment via an acoustical link. In such a system the effects of both limited bandwidth channels and delayed communications are overcome by transmitting not Cartesian or joint level information but rather symbolic, error-tolerant, program instructions to the remote site. The operator interacts with a virtual reality of the remote site which provides immediate visual and kinesthetic feedback. The uncertainty in this model can be reduced based on information received from the slave manipulator's tactile contact with the environment. It is suggested that the current state of the model be made available to the operator via a graphical display which shows not only the position of objects at the remote site but also, through the use of color clues, the uncertainty associated with those positions. The provision of uncertainty information is important since it allows the operator to compromise between speed and accuracy. An additional operator aid, which we term synthetic fixturing, is proposed. Synthetic fixtures provide the operator of the teleprogramming system with the teleoperation equivalent of the ``snap'' commands common in computer aided design programs. By guiding the position and/or orientation of the master manipulator toward specific points, lines or planes the system is able to increase both the speed and precision with which the operator can control the slave arm without requiring sophisticated hardware.

MS-CIS-93-16 (LINC LAB 246)

The Relatedness and Comparative Utility of Various Approaches To Operational Semantics

Raymond C. McDowell

We examine three approaches to operational semantics: transition semantics, natural semantics, and reduction semantics. First we compare the style and expressive power of the three forms of semantics by using them to construct semantics for various language features. Program abortion, interleaving, and block structure particularly distinguish the three. Natural semantics was very good at specifying ``large granularity'' features such as blocks, but is apparently unable to capture interleaving because of its ``small granularity''. On the other hand, transition semantics and reduction semantics easily express ``small granularity'' features but have difficulty with ``large granularity'' features. Reduction semantics provide especially concise specifications of non-sequential control constructs such as abortion and interleaving. We also analyze the utility of the different approaches for two application areas: implementation correctness and type soundness. For these two applications, natural semantics seems to allow simpler proofs, although we do not generalize this conclusion to other areas.

MS-CIS-93-17 (GRAPHICS LAB 54)

Intermittent Non-Rhythmic Human Stepping and Locomotion

Hyeongseok Ko, Norman I. Badler

There are many occasions where non-rhythmic stepping (NRS) is more desirable than normal walking. This can be observed in performing tasks in a narrow work space. For this purpose NRS is considered as a variation of curved path walking. Four types of local adjustment are dealt with: forward, backward, lateral stepping, and turnaround. In the lower body motion, the trajectory of the hip, angular trajectory of the feet, and the trajectory of the swing ankle during the swing phase determine the basic outline of an NRS. These trajectories are precomputed in INITIALIZE_NRS before each NRS begins. ADVANCE_NRS is called with a normalized time to generate the actual pose of the NRS at that moment. The normalized time is a logical time, covering zero to one during a complete step.

MS-CIS-93-18 (DISTRIBUTED SYSTEMS LAB 16)

Experimental Evaluation of an ATM Host Interface

C. Brendan S. Traw, Jonathan M. Smith

We have previously reported a design for a host interface board intended to connect workstations to ATM networks, and an implementation that was underway. Since then, we have made some modifications to the hardware implementation, and implemented software support. Our prototype connects an IBM RS/6000 to a SONET-based ATM network carrying data at the OC-3c rate of 155Mbps.

In this paper, we discuss an experimental evaluation of the interface and supporting software. Our experiments uncovered an unexpected bottleneck in providing high bandwidth to application processes, and we suggest a number of possible improvements to workstation architectures to address this bottleneck.

MS-CIS-93-19 (DISTRIBUTED SYSTEMS LAB 17)

Cryptographic Support in A Gigabit Network

Jonathan M. Smith, C. Brendan S. Traw, David J. Farber

Many applications envisioned for ultra-high-speed networks require cryptographic transformations for data in transit. Security has often been an afterthought, and cryptographic support has generally not kept pace with performance increases in other network components. Two distinct experimental prototypes of high-speed DES boards were built to understand architectural issues in providing cryptographic support for the AURORA gigabit testbed. Combining cryptographic support with the host/network interface is indicated.

MS-CIS-93-20 (DISTRIBUTED SYSTEMS LAB 18)

An Overview of the Aurora Gigabit Testbed

David D. Clark, Bruce S. Davie, David J. Farber, Inder S. Gopal, Bharath K. Kadaba, W. David Sincoskie, Jonathan M. Smith, David L. Tennenhouse

AURORA is one of five U.S. testbeds charged with exploring applications of, and technologies necessary for, networks operating at gigabit per second or higher bandwidths. AURORA is also an experiment in collaboration, where government support (through the Corporation for National Research Initiatives, which is in turn funded by DARPA and the NSF) has spurred interaction among centers of excellence in industry, academia, and government.

The emphasis of the AURORA testbed, distinct from the other four testbeds, is research into the supporting technologies for gigabit networking. Our targets include new software architectures, network abstractions, hardware technologies, and applications. This paper provides an overview of the goals and methodologies employed in AURORA, and reports preliminary results from our first year of research.

MS-CIS-93-21 (DISTRIBUTED SYSTEMS LAB 19)

The Software Design Laboratory

Jonathan M. Smith

Software Design Laboratory is an undergraduate practicum in software design, which focuses on principles and practices of large-scale software design. Concepts and examples borrowed from elsewhere in Computer Science are applied to the construction of a significant project, namely a command interpreter resembling the Bourne shell. The course focus is on long-lived software systems of a size requiring group effort. We therefore address maintenance, testing, documentation, code readability, version control, and group dynamics.

MS-CIS-93-22 (DISTRIBUTED SYSTEMS LAB 20)

Exploiting Parallelism in Hardware Implementation of the DES

Albert G. Broscius, Jonathan M. Smith

The Data Encryption Standard algorithm has features which may be used to advantage in parallelizing an implementation. The kernel of the algorithm, a single round, may be decomposed into several parallel computations resulting in a structure with minimal delay. These rounds may also be computed in a pipelined parallel structure for operations modes which do not require cryptext feedback. Finally, system I/O may be performed in parallel with the encryption computation for further gain. Although several of these ideas have been discussed before separately, the composite presentation is novel.

MS-CIS-93-23 (DISTRIBUTED SYSTEMS LAB 21)

Reducing Host Load, Network Load, and Latency in a Distributed Shared Memory

Ronald G. Minnich, David J. Farber

Mether is a Distributed Shared Memory (DSM) that runs on Sun workstations under the SunOS 4.0 operating system. User programs access the Mether address space in a way indistinguishable from other memory. Mether had a number of performance problems which we had also seen on a distributed shared memory called Memnet. In this paper we discuss changes we made to Mether and protocols we developed to use Mether that minimize host load, network load, and latency. An interesting (and unexpected) result was that for one problem we studied the same "best" protocol for Mether is identical to the "best" protocol for MemNet.

The changes to Mether involve exposing an inconsistent store to the application and making acdcess to the consistent and inconsistent versions very convenient; providing both demand-driven and data-driven semantics for updating pages; and allowing the user to specify that only a small subset of a page need be transferred. All of these operations are encoded in a few address bits in the Mether virtual address.

MS-CIS-93-24 (DISTRIBUTED SYSTEMS LAB 22)

The Mether System: Distributed Shared Memory for SunOS 4.0

Ronald G. Minnich, David J. Farber

Mether is a Distributed Shared memory (DSM) that runs on Sun workstations under the SunOS 4.0 operating system. User programs access the Mether address space in a way indistinguishable from other memory. Mether was inspired by the MemNet DSM, but unlike MemNet Mether consists of software communicating over a conventional Ethernet. The kernel part of Mether actually does no data transmission over the network. Data transmission is accomplished by a user-level server. The kernel driver has no preference for a server, and indeed does not know that servers exist. The kernel driver has been made very safe, and in fact panic is not in its dictionary.

MS-CIS-93-25 (DISTRIBUTED SYSTEMS LAB 23)

Traffic Characteristics of A Distributed Memory System

Jonathan M. Smith, David J. Farber

We believe that many distributed computing systems of the future will use distributed shared memory as a technique for interprocess communication. Thus, traffic generated by memory requests will be a major component of the traffic for any networks which connect nodes in such a system. In this paper, we study memory reference strings gathered with a tracing program we devised. We study several models. First, we look at raw reference data, as would be seen if the network were a backplane. Second, we examine references in units of "blocks", first using a one-block cache model and then with an infinite cache. Finally, we study the effect of predictive prepaging of these "blocks" on the traffic. We provide a novel representation of memory reference data which can be used to calculate interarrival distributions directly. Integrating communication with computation can be used to control both traffic and performance.

MS-CIS-93-26 (DISTRIBUTED SYSTEMS LAB 24)

Implementation and Performance of An ATM Host Interface for Workstations

C. Brendan S. Traw, Jonathan M. Smith

This brief paper outlines our strategies for providing a hardware and software solution to interfacing host to high-performance networks. Our prototype implementation connects an IBM RS/6000 to a SONET-based ATM network carrying data at the OC-3c rate of 155Mbps. We have measured application-to- network data rates of up to 130 Mbps.

MS-CIS-93-27 (DISTRIBUTED SYSTEMS LAB 25)

Hardware/Software Organization of A High Performance ATM Host Interface

C. Brendan S. Traw, Jonathan M. Smith

Concurrent increases in network bandwidths and processor speeds have created a performance bottleneck at the workstation-to-network host interface. This is especially true for BISDN networks where the fixed length ATM cell is mismatched with application requirements for data transfer; a successful hardware/software architecture will resolve such differences and offer high end-to-end performance.

The solution we report carefully splits protocol processing functions into hardware and software implementations. The interface hardware is highly parallel and performs all per-cell functions with dedicated logic to maximize performance. Software provides support for the transfer of data between the interface and application memory, as well as the state management necessary for virtual circuit setup and maintenance. In addition, all higher level protocol processing is implemented with host software.

The prototype connects an IBM RISC System/6000 to a SONET-based ATM network carrying data at the OC-3c rate of 155 Mbps. An experimental evaluation of the interface hardware and software has been performed. Several conclusions about this host interface architecture and the workstations it is connected to are made.

MS-CIS-93-28 (DISTRIBUTED SYSTEMS LAB 26)

The AURORA Gigabit Testbed

David D. Clark, Bruce S. Davie, David J. Farber, Inder S. Gopal, Bharath K. Kadaba, W. David Sincoskie, Jonathan M. Smith, David L. Tennenhouse

AURORA is one of five U.S. networking testbeds charged with exploring applications of, and technologies necessary for, networks operating at gigabit per second or higher bandwidths. The emphasis of the AURORA testbed, distinct from the other four testbeds, BLANCA, CASA, NECTAR, and VISTANET, is research into the supporting technologies for gigabit networking.

Like the other testbeds, AURORA itself is an experiment in collaboration, where government initiative (in the form of the Corporation for National Research Initiatives, which is funded by DARPA and the National Science Foundation) has spurred interaction among pre-existing centers of excellence in industry, academia, and government.

AURORA has been charged with research into networking technologies that will underpin future high-speed networks. This paper provides an overview of the goals and methodologies employed in AURORA, and points to some preliminary results from our first year of research, ranging from analytic results to experimental prototype hardware. This paper enunciates our targets, which include new software architectures, network abstractions, and hardware technologies, as well as applications for our work.

MS-CIS-93-29 (DISTRIBUTED SYSTEMS LAB 27)

Developing Device Drivers for Character-Class MCA Adapters in AIX, Version 3

Michael Massa

The purpose of this paper is to introduce the reader to the concepts and techniques required to write a device driver for a character class device on the Micro Channel Architecture (MCA) bus in Version 3.xx of IBM's AIX operating system (denoted by just AIX in this document). It attempts to tie together the major pieces of development information dispersed throughout the AIX manuals. It also includes some information not found in the manuals which is crucial to the development of a working device driver. This document by no means provides complete coverage of the topic, and references for further information will be made liberally throughout. It may best be regarded as a road map to AIX device driver development. The reader is assumed to be proficient in UNIX/AIX applications programming and the C programming language.

MS-CIS-93-30 (DISTRIBUTED SYSTEMS LAB 28)

A Host Interface Architecture and Implementation For ATM Networks

Chandler Brendan Stanton Traw

The advent of high speed networks has increased demands on processor architectures. These architectural demands are due to the increase in network bandwidth relative to the speeds of processor components. One important component for a high-performance system is the workstation-to- network "host interface". The solution presented in this thesis migrates a carefully selected set of protocol processing functions into hardware. The host interface is highly parallel and all per cell functions are performed by dedicated logic to maximize performance. There is a clean separation between the interface functions, such as segmentation and reassembly, and the interface/host communication. This architecture has been realized in a prototype which connects an IBM RISC System/6000 workstation to a SONET-based ATM network carrying data at the OC-3c rate of 155 Mbps.

MS-CIS-93-31 (DISTRIUBTED SYSTEMS LAB 29)

Experimental Evaluation Of A Video Capture Board For Networked Workstations

Sanjay Kumar Udani

This thesis examines the architectural issues in the design of a video capture board intended for use in multimedia videoconferencing. The major issues examined are:

• Control of reception and transmission of multimedia video streams
• Quality of service and service provision
• Compression requirements and solutions
• Data buffering and card connection strategies
• Handling multiple video streams

Results of measurements for prototype boards designed and constructed at Penn are also given.

MS-CIS-93-32 (LOGIC & COMPUTATION 58)

Fixpoints and Bounded Fixpoints for Complex Objects

Dan Suciu

We investigate a query language for complex-object databases, which is designed to (1) express only tractable queries, and (2) be as expressive over flat relations as first order logic with fixpoints. The language is obtained by extending the nested relational algebra \cal NRA with a ``bounded fixpoint'' operator. As in the flat case, all PTime computable queries over ordered databases are expressible in this language. The main result consists in proving that this language is a conservative extension of the first order logic with fixpoints, or of the while-queries (depending on the interpretation of the bounded fixpoint: inflationary or partial). The proof technique uses indexes, to encode complex objects into flat relations, and is strong enough to allow for the encoding of \cal NRA with unbounded fixpoints into flat relations. We also define a logic based language with fixpoints, the ``nested relational calculus'', and prove that its range restricted version is equivalent to \cal NRA with bounded fixpoints.

MS-CIS-93-33 (DISTRIBUTED SYSTEMS LAB 30)

Operating Systems Support for End-to-End Gbps Networking

Jonathan M. Smith, C. Brendan S. Traw

This paper argues that workstation host interfaces and operating systems are a crucial element in achieving end-to-end Gbps bandwidths for applications in distributed environments. We describe several host interface architectures,discuss the interaction between the interface and host operating system, and report on an ATM host interface built at the University of Pennsylvania.

Concurrently designing a host interface and software support allows careful balancing of hardware and software functions. Key ideas include use of buffer management techniques to reduce copying and scheduling data transfers using clocked interrupts. Clocked interrupts also aid with bandwidth allocation. Our interface can deliver a sustained 130 Mbps bandwidth to applications, roughly OC-3c link speed. Ninety-three percent of the host hardware subsystem throughput is delivered to the application with a small measured impact on other applications processing.

MS-CIS-93-34 (DISTRIBUTED SYSTEMS LAB 31)

Revision of QoS Guarantees at the Application/Network Interface

Klara Nahrstedt, Jonathan M. Smith

Connection management based on Quality of Service (QoS) offers opportunities for better resource allocation in networks providing service classes. "Negotiation" describes the process of cooperatively configuring application and network resources for an application's use. Complexx and long-running applications can reduce the inefficiencies of static allocations by splitting resource use into "eras" bounded by renegotiation of QoS parameters. Renegotiation can be driven by either the application or the network in order to best match application and network dynamics. A key element in this process is a translation between differing perspectives on QoS maintained by applications and network service provision. We model translation with an entity called a "broker".

MS-CIS-93-35 (DISTRIBUTED SYSTEMS LAB 32)

The Integrated Media Approach To Networked Multimedia Systems

Klara Nahrstedt, Jonathan M. Smith

Applications which require real-time multimedia services[13] face a number of difficult problems in the transmission of multimedia information. Among the most difficult problems are the heterogeneity of end nodes and the heterogeneity of media Quality of Service (QoS) requirements. End nodes typically consist of a computer and number of sensory input and output devices, such as displays, microphones, and cameras. QoS requirements[18] include degrees of reliability, jitter, and delay.

We propose an intergrated approach to address these problems. Multimedia input data comprise a sensory environment which an application will make available; these data are packaged together into an Integrated Multimedia Message (IMM). From a received IMM, output data are selectively reproduced to create another sensory environment. We propose an IMM format and protocol behaviors for generation, presentation, and synchronization of these messages.

While IMM's are aesthetically pleasing, well-suited to proposed high- speed networks, and ease intramessage synchronization, they are potentially plagued by the need to deliver QoS which meets the worst-case requirements of all of their components[6]. We believe that this problem can be addressed, and are testing that belief experimentally with the U. Penn Experimental Multimedia Conferencing System, which will be embedded in the AURORA Gigabit Testbed.

MS-CIS-93-36 (LOGIC & COMPUTATION 59)

Query Languages for Bags

Leonid Libkin, Limsoon Wong

MS-CIS-93-37 (LOGIC & COMPUTATION 60)

The Fast Fourier Transforms As A Database Query

Peter Buneman

By casting the discrete Fourier transform in comprehension syntax and adding some primitives for ``array comprehensions'', the fast Fourier transform may be derived by direct manipulation of source code.

MS-CIS-93-38 (LOGIC & COMPUTATION 61)

DNA Workbench

James Tisdall

DNA WorkBench is a program for working with DNA, RNA, and protein sequences. It is designed to solve several problems that arise in two domains. The first domain is that of the algorithm designer and implementor who is working in the emerging field of computational biology. The second domain is that of the worker in a genetics laboratory, who needs frequently to turn to the computer to perform analysis on existing or newly acquired nucleotide or protein sequences. The problems encountered in these two domains overlap to a considerable extent. The problems, and how they are addressed by DNA WorkBench , are discussed within.

DNA WorkBench addresses both of these groups with one program. In this way, new problems that require new algorithms can be quickly brought from a theoretical solution to an implementation and to the laboratory workbench. This rapid transfer from research to development to the field is essential in a fast moving area such as biotechnology, by which term I mean to encompass such specialties as molecular biology, genetics, human gene therapy, and the current large-scale international sequencing and mapping of human DNA which has been organized as the Human Genome Project in the United States.

MS-CIS-93-39 (LINC LAB 247)

Generating Contextually Appropriate Intonation

Scott Prevost, Mark Steedman

One source of unnaturalness in the output of text-to-speech systems stems from the involvement of algorithmically generated default intonation contours, applied under minimal control from syntax and semantics. It is a tribute both to the resilience of human language understanding and to the ingenuity of the inventors of these algorithms that the results are as intelligible as they are. However, the result is very frequently unnatural, and may on occasion mislead the hearer. This paper extends earlier work on the relation between syntax and intonation in language understanding in Combinatory Categorial Grammar (CCG). A generator with a simple and domain-independent discourse model can be used to direct synthesis of intonation contours for responses to data-base queries, to convey distinctions of contrast and emphasis determined by the discourse model.

MS-CIS-93-40 (GRASP LAB 345)

Model Based Teleoperation To Eliminate Feedback Delay NSF Grant BCS89-01352 - 3rd Report

Richard P. Paul, Thomas Lindsay, Craig Sayers, Matthew Stein, Desikachar Venkatesh

We are conducting research in the area of teleoperation with feedback delay. Significant delays occur when performaing space teleoperation from the earth as well as in subsea teleoperation where the operator is typically on a surface vellel and communication is via acoustic links. These delays make teleoperation extremely difficult and lead to very low operator productivity.

We have combined computer graphics with manipulator programming to provide a solution to the delay problem. A teleoperator master arm is interfaced to a graphical simulation of the remote environment. Synthetic fixtures are used to guid the operators motions and to provide kinesthetic feedback. The operator's actions are monitored and used to generate symbolic motion commands for transmission to, and execution by, the remote slave robot. While much of a task proceeds error free, when an error does occur, the slave system transmits data back to the master environment where the opertor can then experience the motion of the slave manipulator in actural task execution. We have also provided for the use of tools such as an impact wrench and a winch at the slave site. In all cases the tools are unencumbered by sensors; the slave uses a compliant instrumented wrist to monitor tool operation in terms of resulting motions and reaction forces.

MS-CIS-93-42 (LINC LAB 248)

An SE-tree based Characterization of the Induction Problem

Ron Rymon

Many induction programs use decision trees both as the basis for their search, and as a representation of their classifier solution. In this paper we propose a new structure, called SE-tree, as a more general alternative.

MS-CIS-93-43 (DISTRIBUTED SYSTEMS LAB 33)

Host Interfacing at a Gigabit

C. Brendan S. Traw

A major goal of the host interface architecture which has been developed at UPenn is to be sufficiently flexible as to allow implementation using a range of technologies. These technologies can provide the performace necessary for operation in the emerging high bandwidth ATM networking environments. This paper examines the feasibility of reimplementing the current instantiation of the architecture which operates at 160 Mbps to allow for operation in the 600+ Mbps domain.

MS-CIS-93-44 (LOGIC & COMPUTATION 63)

Sequentiality

Dan Suciu

This report contains an overview of concrete data structures, sequential functions and sequential algorithms. We define the notions of {\em concrete data structures} and prove the representation theorem. Next, we present the notions of sequential functions and of sequential algorithms, and show how the latter can serve as a model for PCF. Finally, we present the language CDS0, designed as a syntax for concrete data structures and sequential algorithms

MS-CIS-93-45 (GRASP LAB 346)

Physics-Based Modeling, Analysis and Animation

Ioannis A. Kakadiaris

The idea of using physics-based models has received considerable interest in computer graphics and computer vision research the last ten years. The interest arises from the fact that simple geometric primitives cannot accurately represent natural objects. In computer graphics physics-based models are used to generate and visualize constrained shapes, motions of rigid and nonrigid objects and object interactions with the environment for the purposes of animation. On the other hand, in computer vision, the method applies to complex 3-D shape representation, shape reconstruction and motion estimation.

In this paper we review two models that have been used in computer graphics and two models that apply to both areas. In the area of computer graphics, Miller uses a mass-spring model to animate three forms of locomotion of snakes and worms. To overcome the problem of the multitude of degrees of freedom associated with the mass-spring lattices, Witkin and Welch present a geometric method to model global deformations. To achieve the same result Pentland and Horowitz in delineate the object motion into rigid and nonrigid deformation modes. To overcome problems of these two last approaches, Metaxas and Terzopoulos in successfully combine local deformations with global ones.

Modeling based on physical principles is a potent technique for computer graphics and computer vision. It is a rich and fruitful area for research in terms of both theory and applications. It is important, though, to develop concepts, methodologies, and techniques which will be widely applicable to many types of applications.

MS-CIS-93-46 (LOGIC & COMPUTATION 64)

Realizability, Covers, and Sheaves I. Application to the Simply-typed l -Calculus

Jean Gallier

We present a general method for proving properties of typed l-terms. This method is obtained by introducing a semantic notion of realizability which uses the notion of a cover algebra (as in abstract sheaf theory, a cover algebra being a Grothendieck topology in the case of a preorder). For this, we introduce a new class of semantic structures equipped with preorders, called pre-applicative structures. These structures need not be extensional. In this framework, a general realizability theorem can be shown. Kleene's recursive realizability and a variant of Kreisel's modified realizability both fit into this framework. Applying this theorem to the special case of the term model, yields a general theorem for proving properties of typed l, in particular, strong normalization and confluence. This approach clarifies the reducibility method by showing that the closure conditions on candidates of reducibility can be viewed as sheaf conditions. Part I of this paper applies the above approach to the simply-typed l-calculus (with types ®, ×, +, and ^). Part II of this paper deals with the second-order (polymorphic) l-calculus (with types ® and ").

MS-CIS-93-47 (LOGIC & COMPUTATION 65)

Realizability, Covers and Sheaves II. Applications to the Second-Order Typed $\lambda$-Calculus

Jean Gallier

We present a general method for proving properties of typed l-terms. This method is obtained by introducing a semantic notion of realizability which uses the notion of a cover algebra (as in abstract sheaf theory, a cover algebra being a Grothendieck topology in the case of a preorder). For this, we introduce a new class of semantic structures equipped with preorders, called pre-applicative structures. These structures need not be extensional. In this framework, a general realizability theorem can be shown. Applying this theorem to the special case of the term model, yields a general theorem for proving properties of typed l-terms, in particular, strong normalization and confluence. This approach clarifies the reducibility method by showing that the closure conditions on candidates of reducibility can be viewed as sheaf conditions. Part II of this paper applies the above approach to the second-order (polymorphic) l-calculus l^®,"2 (with types ® and ").

MS-CIS-93-48 (LOGIC & COMPUTATION 66)

Kripke Models for the Second-Orderl-Calculus

Jean Gallier

We define a new class of Kripke structures for the second-order l -calculus, and investigate the soundness and completeness of some proof systems for proving inequalities (rewrite rules) or equations. The Kripke structures under consideration are equipped with preorders that correspond to an abstract form of reduction, and they are not necessarily extensional. A novelty of our approach is that we define these structures directly as functors A\colon\cal W® Preor equipped with certain natural transformations corresponding to application and abstraction (where \cal W is a preorder, the set of worlds, and Preor is the category of preorders). We make use of an explicit construction of the exponential of functors in the Cartesian-closed category Preor^{\cal W}, and we also define a kind of exponential Õ_F(A^s)_{s Î T} to take care of type abstraction. We obtain soundness and completeness theorems that generalize some results of Mitchell and Moggi to the second-orderl -calculus, and to sets of inequalities (rewrite rules).

MS-CIS-93-49 (LOGIC & COMPUTATION 67)

Reducibility Strikes Again, I!

Jean Gallier

In these notes, we prove some general theorems for establishing properties of untyped l-terms, using a variant of the reducibility method. These theorems apply to (pure) l-terms typable in the systems of conjunctive types \cal DO and \cal D. As applications, we give simple proofs of the characterizations of the terms having head-normal forms, of the normalizable terms, and of the strongly normalizing terms. We also give a characterization of the terms having weak head-normal forms. This last result appears to be new.

MS-CIS-93-50 (GRASP LAB 347)

An Active Approach to Characterization and Recognition of Functionality and Functional Properties

Luca Bogoni, Ruzena Bajcsy

Functionality in an object can be defined as its applicability toward the accomplishment of a task. We emphasize and develop an interactive and performatory approach to functionality recovery from sensor data in the context of robotic manipulatory tasks. By analyzing interaction of tool and target object and manipulation tasks as goal--oriented recognition processes we propose to identify and characterize functionalities of objects. This interaction is not only a means of verification of the hypothesized presence of functionality in objects but also a way to actively and purposively recognize the object. The representation of functionality allows us to extend the recovery process to a hierarchy of functionalities allowing complex ones to be composed from simpler ones.

A formal model, based on Discrete Event Dynamic System Theory (DEDS), is introduced to define an interactive task for recovering and describing functionality. To observe and control the recovery process we introduce the notion of piecewise observability of a task by different sensors. This allows the description of a dynamic system in which not all events nor the time of their occurrence may be predicted in advance. An experimental system, with both vision and force sensors, for carrying out the interactive functional recognition is described.

MS-CIS-93-51 (LOGIC & COMPUTATION 68)

Feasible Computation Through Model Theory (Dissertation)

Anuj Dawar

The computational complexity of a problem is usually defined in terms of the resources required on some machine model of computation. An alternative view looks at the complexity of describing the problem (seen as a collection of relational structures) in a logic, measuring logical resources such as the number of variables, quantifiers, operators, etc . A close correspondence has been observed between these two, with many natural logics corresponding exactly to independently defined complexity classes. For the complexity classes that are generally identified with feasible computation, such characterizations require the presence of a linear order on the domain of every structure, in which case the class PTIME is characterized by an extension of first-order logic by means of an inductive operator. No logical characterization of feasible computation is known for unordered structures. We approach this question from two directions. On the one hand, we seek to accurately characterize the expressive power of inductive logics over classes of structures where no linear order is present. On the other hand, we study extensions of inductive logic by means of generalized quantifiers to determine if such extensions might exactly express the PTIME properties. For the two investigations, we develop a common set of tools and techniques, based on notions from model theory. Basic notions, such as those of elementary equivalence and element type are adapted to the context of finite relational structures, in particular, by restricting the number of distinct variables that can appear in any formula. We use these tools to show that there is no extension of the inductive logic be means of a finite number of generalized quantifiers that exactly expresses the PTIME properties of finite relational structures. We also show that, if there is any descriptive characterization of the PTIME properties, indeed if the PTIME properties are recursively indexable, then there is a characterization by means of an extension of first-order logic by a uniform, infinite sequence of generalized quantifiers. This is established through a general result linking the recursive indexability of a complexity class with the existence of complete problems via weak logical reductions.

MS-CIS-93-52 (LINC LAB 249)

CLiff Notes: Research in the Language Information and Computation Laboratory Annual Report--Spring 1993, No. 3

Faculty & Graduate Students

MS-CIS-93-53 (GRASP LAB 348)

Elastically Deforming A Three-Dimensional Atlas To Match Anatomical Brain Images

Jim C. Gee, Martin Reivich, Ruzena Bajcsy

To evaluate our system for elastically deforming a three-dimensional atlas to match anatomical brain images, six deformed versions of an atlas were generated. The deformed atlases were created by elastically mapping an anatomical brain atlas onto different MRI brain image volumes. The mapping matches the edges of the ventricles and the surface of the brain; the resultant deformations are propagated through the atlas volume, deforming the remainder of the structures in the process. The atlas was then elastically matched to its deformed versions. The accuracy of the resultant matches was evaluated by determining the correspondence of 32 cortical and subcortical structures. The system on average matched the centroid of a structure to within 1 mm of its true position and fit a structure to within 11% of its true volume. The overlap between the matched and true structures, defined by the ratio between the volume of their intersection and the volume of their union, averaged 66%. When the gray-white interface was included for matching, the mean overlap improved to 78%; each structure was matched to within 0.6 mm of its true position and fit to within 6% of its true volume. Preliminary studies were also made to determine the effect of the compliance of the atlas on the resultant match.

MS-CIS-93-54 (GRAPHICS LAB 55)

Modeling Articulated Figure Motion With Physically-and Physiologically-Based Constraints (Dissertation)

Philip L.Y. Lee

A methodology and algorithm are presented that generate motions imitating the way humans complete a task under various loading conditions. The path taken depends on ``natural'' parameters: the figure geometry, the given load, the final destination, and, especially, the strength model of the agent. Additional user controllable parameters of the motion are the comfort of the action and the perceived exertion of the agent. The algorithm uses this information to incrementally compute a motion path of the end-effector moving the load. It is therefore instantaneously adaptable to changing force, loading, and strength conditions. Various strategies are used to model human behavior (such as available torque, reducing moment and pull back) that direct the trajectories. The strength model dictates acceptable kinematic postures. The resulting algorithm also offers torque control without the tedious user expression of driving forces under a dynamics model. The algorithm runs in near-real-time and offers an agent-dependent toolkit for fast path prediction. Examples are presented for various lifting tasks, including one- and two-handed lifts, and raising the body from a seated posture.

MS-CIS-93-55 (GRAPHICS LAB 56)

Intermittent Non-Rhythmic Human Stepping and Locomotion

Hyeongseok Ko

When humans need to get from one location to another, there are many occasions where non-rhythmic stepping (NRS) is more desirable than normal walking. This can be observed in performing tasks in a constricted work space. For the purpose NRS is considered as a variation of curved path walking. Four types of local adjustment are dealt with: forward, backward, lateral stepping, and turnaround. Combined with curved path walking, NRS provides a very useful tool for animating human locomotion behaviors. In the lower body motion, the trajectory of the hip, angular trajectory of the feet, and the trajectory of the swing ankle during the swing phase determine the basic outline of an NRS. These trajectories are precomputed at the start of each step. The stepping process is called with a {\em normalized time} to generate the actual pose of the NRS at that moment. the normalized time is a logical time, covering zero to one during a complete step.

MS-CIS-93-56 (LINC LAB 250)

Search Plans (Dissertation Proposal)

Michael Moore

People often do not know where things are and have to look for them. This thesis presents a formal model suitable for reasoning about how to find things and acting to find them, which I will call ``search behavior''. Since not knowing location of something can prevent an agent from reaching its desired goal, the ability to plan and conduct a search will be argued to increase the variety of situations in which an agent can succeed at its chosen task.

Searching for things is a natural problem that arises when the blocks world assumptions (which have been the problem setting for most planning research) are modified by providing the agent only partial knowledge of its environment. Since the agent does not know the total world state, actions may appear to have nondeterministic effects. The significant aspects of the search problem which differ from previously studied planning problems are the acquisition of information and iteration of similar actions while exploring a search space.

Since introduction of the situation calculus [McCarthy69], various systems have been proposed for representing and reasoning about actions which involve knowledge acquisition and iteration, including Moore's work on the interaction between knowledge and action [Moore80]. My concern with searching has to do with a sense that Moore's knowledge preconditions are overly restrictive. Morgenstern [Morgenstern88] examined ways to weaken knowledge preconditions for an individual agent by relying on the knowledge and abilities of other agents. Lesperance's research [Lesperance91] on indexical knowledge is another way of weakening the knowledge preconditions. I am trying to reduce the {\em amount} of information an agent must know (provided they can search a known search space). If you dial the right combination to a safe it will open, whether or not you knew in advance that it was the right combination. Search is a way to guarantee you will eventually dial the right combination. So what I am exploring is how to systematically construct a search that will use available knowledge to accomplish something the agent does not currently know enough to do directly. Such systems can be used to infer properties of plans which have already been constructed, but do not themselves construct plans for complex actions.

I claim it is possible for automated agents to engage in search behavior. Engaging in search behavior consists in recognizing the need for a search, constructing an effective plan, and then carrying out that plan. Expressing such a plan and reasoning about its effectiveness requires a representation language. I will select a representation language based on criteria derived from analyzing the search planning problem. Each of the three components of a system for engaging in search behavior will be designed and implemented to demonstrate that an automated agent can find things when it needs to.

MS-CIS-93-57 (LINC LAB 251)

Goal-Directed Diagnosis-Diagnostic Reasoning in Exploratory-Corrective Domains

Ron Rymon

In many diagnosis-and-repair domains, diagnostic reasoning cannot be abstracted from repair actions, nor from actions necessary to obtain diagnostic information. We call these exploratory-corrective domains. In TraumAID 2.0, a consultation system for multiple trauma management, we have developed and implemented a framework for reasoning in such domains which integrates diagnostic reasoning with planning and action. In this paper, we present Goal-Directed Diagnosis (GDD), the diagnostic reasoning component of this framework. Taking the view that a diagnosis is only worthwhile to the extent that it can affect subsequent decisions, GDD focuses on the formation of appropriate goals for its complementary planner.

MS-CIS-93-58 (GRASP LAB 349)

GRASP NEWS: Volume 9, Number 1

Faculty & Graduate Students

The past year at the GRASP Lab has been exciting and productive period. As always, innovation and technical advancement arising from past research has lead to unexpedcted questions and fertile areas for new research. New robots, new mobile platforsm, new sensors and cameras, and new personnel have all contributed to the breathtaking pace of the change. Perhaps the most significant change is the trend towards multi-disciplinary projects, most notable the multi-agent project (see inside for details on this, and all the other new and on-going project). This issue of GRASP News covers the developments for the year 1992 and the first quarter of 1993.

MS-CIS-93-59 (GRASP LAB 350)

The Soundness and Completeness of ACSR (Algebra of Communicating Shared Resources)

Patrice Brémond-Grégoire

Recently, significant progress has been made in the development of timed process algebras for the specification and analysis of real-time systems; one of which is a timed process algebra called ACSR supports synchronous timed actions and asynchronous instantaneous events. Timed actions are used to represent the usage of resources and to model the passage of time. Events are used to capture synchronization between processes. The be able to specify real systems accurately, ACSR supports a notion of priority that can be used to arbitrate among timed actions competing for the use of resources and among events that are ready for synchronization. Equivalence between ACSR terms is defined in terms of strong bisimulation. The paper contains a set of algebraic laws that are proven sound and complete for finite ACSR agents. This paper contains the soundness and completeness proofs of the ACSR laws reported in an earlier report (MS-CIS-93-08)

MS-CIS-93-60 (LOGIC & COMPUTATION 69)

Conservativity of Nested Relational Calculi with Internal Generic Functions

Leonid Libkin, Limsoon Wong

It is known that queries in nexted relational calculus are independent of the depth of set nesting in the intermediate data and this remains true in the presence of aggregate functions. We prove that this continues to be true if the calculus is augmented with any internal generic family of functions.

MS-CIS-93-61 (LINC LAB 252)

Instructions, Intentions and Expectations

Bonnie Webber, Norman Badler, Barbara DiEugenio, Christopher Geib, Libby Levison, Michael Moore

This is a short position paper on what we have learned about the relationship between language and behavior from an on-going attempt to enable people to use Natural Language instructions to tell animated human figures what to do.

We view instructions as texts intended to be understood in context, produced by an instructor who knows more than the agent. (The latter means that instructions are worth trusting, even if the world initially provides no corroborating evidence.) With this view underlying the architecture of our Animation from Natural Language ( AnimNL) system, the paper discusses two main things we have learned about the complex relationship between language and behavior:

1. Intentions formed in response to instructions influence agents' behavior at every level of decision-making, from language understanding to motor control.
2. Expectations formed in response to instructions influence agents' behavior --- what they do and what they look for --- over and beyond their current perceptions. As such, expectations from instructions complement information from the world in guiding an agent's behavior.

MS-CIS-93-62 (LOGIC & COMPUTATION 70)

Queries on Databases with User-Defined Functions

Dan Suciu

The notion of a database query is generalized for databases with user-defined functions. Then, we can prove that the computable queries coincide with those expressible by an extension of the relational machine, with oracles ([4]). This implies that any complete query language, extended with user-defined function symbols in a ``reasonable'' way, is still complete. We give an example of a complete query language with user-defined functions, and discuss its connections with object inventions.

MS-CIS-93-63 (GRAPHICS LAB 57)

SASS v.2.1: Anthropometric Spreadsheet and Database for the IRIS

Francisco Azuola, Teo Kok Hoon, Sussana Wei

It describes the usage of SASS , a spreadsheet-like system which allows flexible interactive access to all anthropometric variables needed to size a computer-based human figure, described structurally by a PEABODY file.

Data that may be accessed is organized into the following ``groups'': segment dimension (``girth''), joint limits, center of mass, and strength, all of which work based on statistical population data. SASS creates generic computer-based human figures based on this data.

SASS also is an anthropometric database and interactive query system that works upon anthropometric data of real individuals. Scaled computer-based human figures created by SASS can be displayed directly, and interactively changed, within the Jack software.

MS-CIS-93-64 (LINC LAB 253)

A Model of Redundant Information in Dialogue: The Role of Resource Bounds (Dissertation Proposal)

Marilyn A. Walker

The proposed thesis aims to contribute to current research on cognitively and computationally accurate models of dialogue. It investigates the use of informationally redundant utterances (IRUs) in a corpus of problem-solving task-oriented dialogues. An IRU is an utterance whose propositional content was already added to the representation of the dialogue by the IRU's antecedent, a previous utterance that realizes the same propositional content as the IRU.

IRUs are clearly of linguistic interest since they appear to be counter examples to the Gricean Maxim of Quantity. Furthermore since communication is a subcase of action, the existence of IRUs is a paradox because IRUs appear to be actions whose effects have already been achieved.

An essential part of the proposed thesis is a distributional analysis of IRUs in a large corpus of naturally occurring problem solving dialogues. About 12% of the utterances in the corpus are IRUs. The distributional analysis examines the logical type of IRUs, the prosody of IRUs, and the co-occurrence of IRUs with other indicators of discourse structure such as cue words, and the location of the IRUS with respect to its antecedent. IRUs include cases of presupposition affirmation, and implicature reinforcement when the implicata is not said by the same speaker in the same utterance.

I argue that IRUs can only be explained by a processing model of dialogue that reflects agents' autonomy and limited attentional and inferential capacity. IRUs can be classified into three communicative functions and each of these functions can be related to either agents' autonomy or limited processing capacity:

• Attitude: to address the assumptions underlying the inference of beliefs about mutual understanding and acceptance
• Consequence: to change the status of a belief from an implicature to an entailment, or from an implicit belief to an explicit one
• Attention: to manipulate the locus of attention of the discourse participants by making or keeping a proposition salient

Attitude is related to agent's autonomy. The treatment of attitude has required the development of a model of mutual beliefs based on Lewis's shared environment model of common knowledge. The treatment of the communicative function of Attention is based the interaction of this model of mutual belief with Prince's taxonomy of information status and notions such as given-s or salient. Finally the treatment of Consequence also relies on developing the shared environment model of mutual beliefs to capture aspects of agents' limited reasoning ability. It isn't possible to use most existing semantics models, based on possible world semantics, because they make the simplifying assumption that agents are logically omniscient.

MS-CIS-93-65 (GRASP LAB 351)

Wide Bandwidth, Distributed, Digital Teleoperation

Venkatesh Desikachar, Matthew Stein, Richard Paul

Teleoperation means to perform a task at a distance. The task is performed by a manipulator located at a remote site, controlled by the master manipulator located in the control room. The loop between the master and the slave manipulator is closed by the human operator. the dexterity and manipulability of the overall system has to be high such that the actions can be easily carried out by the operator. A visual display provides the operator a view of the slave arm and the task environment, kinesthetic feedback provides a sense of physically performing the task. Kinesthetic feedback is direct feedback to the operator, while visual, audio, and other feedback are indirect in nature. The displays generated from the video data are very useful even when the quality of the image is degraded. Changes in the camera position and orientation can cause severe strain on the operator when interpreting the viewed image. The corrections are applied to the position and force transformations to reduce the strain on the operator. The position and force data are communicated over a communication channel from one station to the other. The use of communication channel basically not designed for real time processes can introduce significant delays leading to operator induced instability of the teleoperator system. IN the presence of such delays the force reflection as a non-reactive feedback can help in maintaining the stability of the system. The forces encountered by the slave manipulator is transformed into audio range signals. The audio signal to the operator is a reflection of force in a non-reactive manner. Advances in high speed networks with increased bandwidth and decreased error rates provide an opportunity to implement teleoperator systems for long distance and distributed teleoperation. A single operator from a control station can interact physically with a system situated anywhere in the world and perform the tasks as though he or she was present at the remote site. A step by step implementation procedure of a direct teleoperator system with communication between master and slave stations through a computer network is described. the corrections to the transforms to nullify the effect of change in viewing parameters are discussed. The experimental results showing the effectiveness of the change in camera orientations and the comparison of active force reflection to the non-reactive force reflection in the form of auditory signal is presented.

MS-CIS-93-66 (GRASP LAB 352)

Multiple Representation Approach To Geometric Model Construction from Range Data

Visa Koivunen, Jean-Marc Vezien, Ruzena Bajcsy

A method is presented for constructing geometric design data from noisy 3-D sensor measurements of physical parts. In early processing phase, RLTS regression filters stemming from robust estimation theory are used for separating the desired part of the signal in contaminated sensor data from undesired part. Strategies for producing a complete 3-D data set from partial views are studied. Surface triangulation, NURBS, and superellipsoids are employed in model construction to be able to represent efficiently polygonal shapes, free form surfaces and standard primitive solids. Multiple representations are used because there is no single representation that would be most appropriate in all situations. The size of the required control point mesh for spline description is estimated using a surface characterization process. Surfaces of arbitrary topology are modeled using triangulation and trimmed NURBS. A user given tolerance value is driving refinement of the obtained surface model. The resulting model description is a procedural CAD model which can convey structural information in addition to low level geometric primitives. The model is translated to IGES standard product data exchange format to enable data sharing with other processes in concurrent engineering environment. Preliminary results on view registration and integration using simulated data are shown. Examples of model construction using both real and simulated data are also given.

MS-CIS-93-67 (LINC LAB 254)

Provability in TBLL: A Decision Procedure

Jawahar Chirimar (University of Pennsylvania), James Lipton (Wesleyan University)

We prove the decidability of the Tensor-Bang fragment of linear logic and establish upper (doubly exponential) and lower (NP-hard) bounds.

MS-CIS-93-68 (GRASP LAB 353)

Simplifying Tool Usage In Teleoperative Tasks

Thomas Lindsay, Richard P. Paul

Modern robotic research has presented the opportunity for enhanced teleoperative systems. Teleprogramming has been developed for teleoperation in time-delayed environments, but can also lead to increased productivity in non-delayed teleoperation.

Powered tools are used to increase the abilities of the remote manipulator. However, tools add to the complexity of the system, both in terms of control and sensing. Teleprogramming can be used to simplify the operators interaction with the manipulator/tool system. Further, the adaptive sensing algorithm of the remote site system (using an instrumented compliant wrist for feedback) simplifies the sensory requirements of the system. Current remote-site implementation of a teleprogramming tool-usage strategy that simplifies tool use is described in this document.

The use of powered tools in teleoperation tasks is illustrated by two examples, ine using an air-powered impaced wrency, and the other using an electric winch. both of these tools are implemented at our remote site workcell, consisting of a Puma 560 robot working on the task of removing the top of a large box.

MS-CIS-93-69 (LINC LAB 255)

Verb Phrase Ellipsis: Form, Meaning and Processing (Dissertation)

Daniel Hardt

The central claim of this dissertation is that an elliptical VP is a proform. This claim has two primary consequences: first, the elliptical VP can have no internal syntactic structure. Second, the interpretation of VP ellipsis must be governed by the same general conditions governing other proforms, such as pronouns. The basic condition governing the interpretation of a proform is that it must be semantically identified with its antecedent. A computational model is described in which this identification is mediated by store and retrieve operations defined with respect to a discourse model. Because VP ellipsis is treated on a par with other proforms, the ambiguity arising from ``sloppy identity'' becomes epiphenomenal, resulting from the fact that the store and retrieve operations are freely ordered.

A primary argument for the proform theory of VP ellipsis concerns syntactic constraints on variables within the antecedent. I examine many different types of variables, including reflexives, reciprocals, negative polarity items, and wh-traces. In all these cases, syntactic constraints are not respected under ellipsis. This indicates that the relation governing VP ellipsis is semantic rather than syntactic. In further support of the proform theory, I show that there is a striking similarity in the antecedence possibilities for VP ellipsis and those for pronouns.

Two computer programs demonstrate the claims of this dissertation. One program implements the semantic copying required to resolve VP ellipsis, demonstrating the correct set of possible readings for the examples of interest. The second program selects the antecedent for a VP ellipsis occurrence. This program has been tested on several hundred examples of VP ellipsis, automatically collected from corpora.

MS-CIS-93-70 (LOGIC & COMPUTATION 71)

Algebraic Characterization of Edible Powerdomains

Leonid Libkin

Powerdomains like mixes, sandwiches, snacks and scones are typically used to provide semantics of collections of descriptions of partial data. In particular, they were used to give semantics of databases with partial information. In this paper we argue that to be able to put these constructions into the context of a programming languages it is necessary to characterize them as free (ordered) algebras. Two characterizations -- for mixes and snacks -- are already known, and in the first part of the paper we give characterizations for scones and sandwiches and provide an alternative characterization of snacks. The algebras involved have binary and unary operations and relatively simple equational theories. We then define a new construction, which is in essence all others put together (hence called salad and give its algebraic characterization. It is also shown how all algebras considered in the paper are related in a natural way, that is, in a way that corresponds to embeddings of their powerdomains. We also discuss some semantic issues such as relationship between the orderings and the semantics and justification for choosing the orderings. Finally, we outline prospects for further research.

MS-CIS-93-71 (GRASP LAB 354)

Parallel Algorithms for Relational Coarsest Partition Problems

Sanguthevar Rajasekaran, Insup Lee

Relational Coarsest Partition Problems (RCPPs) play a vital role in verifying concurrent systems. It is known that RCPPS are \cal P-complete and hence it may not be possible to design polylog time parallel algorithms for these problems.

In this paper, we present two efficient parallel algorithms for RCPP, in which its associated label transition system is assumed to have m transitions and n states. The first algorithm runs in O(n^1+Î time using [m/(n ^Î )] CREW PRAAM processors, for any fixed Î < 1. This algorithm is analogous and optimal with respect to the sequential algorithm of Kanellakis and Smolka. the second algorithm runs in O(n log n) time using [m/n] log n CREW PRAM processor. this algorithm is analogous and nearly optimal with respect to the sequential algorithm of Paige and Tarjan.

MS-CIS-93-72 (GRASP LAB 355)

Fast Parallel Routing and Computation On Interconnection Networks (Dissertation)

David Shyue Liang Wei

Both parallel processing and artificial intelligence play important roles in computer science. The application of parallel processing in artificial intelligence is one of the possible approaches to realize an efficient and intelligent computer. This is a two-part thesis. The first part of this thesis investigates routing problems, which are central to parallel processing, for a class of interconnection networks called leveled networks, while the second part of the thesis makes use of these results to develop efficient parallel algorithms for some communication intensive artificial intelligence problems. Specifically, we look at the parsing problem for natural language grammars which is a fundamental problem in artificial intelligence. Our work goes beyond theoretical study on routing and parallel algorithms in the we also develop implementations of the algorithms on an actual parallel machine, viz., the Connection Machine(CM). This allows us to verify experimentally the performance predicted by theoretical analysis.

To date, much of the work on routing has virtually centered on constant degree networks with logarithmic (or even larger) diameter. In order to achieve faster communication, we initiate the study of routing on some non-constant degree networks in sublogarithmic diameter. We also give a universal randomized optimal routing algorithm for a large class of interconnection networks, viz., leveled networks. These leveled networks can be of logarithmic, or sublogarithmic diameter. Further, we present algorithms for emulating PRAMs, and ideal shared memory model, on leveled networks. The emulation is optimal.

We also study parallel parsing algorithms. In particular, we consider tree adjoining grammars (TAGs). We give a parallel parsing algorithm on a 5-dimensional systolic array, which achieves optimal speed-up with respect to the best known sequential one. We also present an efficient algorithm for general TAGs on the CM. This implemented algorithm parallelizes the parsing in terms of the grammar size unlike previous parallel parsing algorithms which parallelize the parsing in terms of the input sentence. The former is highly desirable for the natural language processing because of the huge grammar size.

MS-CIS-93-73 (GRASP LAB 356)

A Lower Bound Result For The Common Element Problem and Its Implication For Reflexive Reasoning

Paul Dietz, Danny Krizanc, Sanguthevar Rajasekaran, Lokendra Shastri

In this paper we prove a lower bound of W (n log n) for the common element problem on two sets of size n each. Two interesting consequences of this lower bound are also discussed. In particular, we show that linear space neural network models that admit unbalanced rules cannot draw all inferences in time independent of the knowledge base size. We also show that the join operation in data base applications needsW (log n) time given only n processors.

MS-CIS-93-74 (GRAPHICS LAB 58)

Moving Posture Reconstruction From Perspective Projections of Jointed Figure Motion (Dissertation)

Jianmin Zhao

Our goal is to reproduce a human figure's motion with a computer simulated human figure: Given a sequence of perspective projections of a set of feature joints of the moving figure, we tried to recover the original 3D postures through an accurate human figure model and the continuity requirement (temporal coherence) in the sequence. Our approach follows two clues: Given the human figure model, the responsible posture for a frame is constrained by the projections of all the feature joints and, in this limited set of postures we can choose one based on the postures in the previous frames and the temporal coherence, unless there occurs a critical condition, when the projection ray of a feature is perpendicular to the link of which the feature is the distal end. Owing to the fast inverse kinematics algorithm we developed to solve the spatial constraints, we were able to exploit the temporal coherence in projection sequences of frequencies as high as 100 Hz. We used finite state automata to detect critical conditions, and developed various strategies to overcome special difficulties around critical frames. Furthermore, we investigated the impact of errors in linear measurements of body parts on the reconstruction process. Based on mathematical analysis, we proposed some heuristics to discover and recover from the possible modeling errors. To test the theory, we implemented an experimental system. By imposing the temporal coherence constraint whenever possible, this system responds to the incoming images almost linearly: Since the error-prone critical conditions are detected and handled at the very early stage, the system is able to do away with endless recursive backtracking so that only one level of roll-back is needed to handle a limited number of critical conditions whose chances of occurrence are independent of the sampling rate. The system admits generic human motion. It has been tested on synthesized images from actual 3D human motions. Since we knew the original motion, we were able to evaluate results quantitatively. It turned out that the reconstructed motions agreed with the original ones not only in general but also in fine details.

MS-CIS-93-75 (GRASP LAB 357)

Control of Mechanical Systems With Rolling Contacts: Applications To Robotics (Dissertation)

Nilanjan Sarkar

The problems of modeling and control of mechanical dynamic systems subject to rolling contacts are investigated. There are two important theoretical contributions in this dissertation. First, contact kinematic relationships up to second order are developed for two rigid bodies in point contact. These equations relate gross rigid body motion to the changes in the positions of the points of contact. Second, a unified approach to the control of mechanical systems subject to both holonomic and nonholonomic constraints is proposed. The basic approach is to extend the state-space to include, in the addition to the generalized coordinates and velocities, contact coordinates which describe the displacements of the contact points and their derivatives. This redundant state-space formulation provides a convenient way to specify output equations to control contact motion. The control problem is formulated as an affine nonlinear problem and a differential-geometric, control-theoretic approach is used to decouple and linearize such systems. It is shown that such a system, even though not input-state linearizable, is input-output linearizable. Further, the zero dynamics of such a system is shown to be Lagrange stable.

The proposed methodology is applied to three different robotic systems: (a) wheeled mobile robots, (b) two arms manipulating an object with rolling contact between each arm and the object, and (c) a single robot arm maintaining controlled contact against a moving environment. In each case, a nonlinear controller is designed to achieve the desired performances. For mobile robots, a new control algorithm called dynamic path following is proposed and shown to be quite effective and robust. In the context of two arm manipulation, grasp adaptation through the control of contact motion is demonstrated. Maintaining rolling contact with a moving surface is formulated as an acatastatic system. The proposed scheme involves simultaneously controlling interaction forces as well as the relative (rolling) motion. In all cases, computer simulations results are presented to demonstrate the efficacy of the control schemes.

MS-CIS-93-76 (GRASP LAB 358)

Characterization of Functionality In A Dynamic Environment

Luca Bogoni, Ruzena Bajcsy

Identifying the functionality in objects means to be able to associate a purpose with them in a specific environment. The purpose depends on the intention of the agent and on the applicability of the object in a particular task. In our investigation of functionality we focus on functionalities which involve changes of physical relation and properties between objects in the environment. A formal model, based on Discrete Event Dynamic System Theory (DEDS), is introduced to define an interactive task for recovering and describing functionality. To observe and control the recovery process we introduce the notion of piecewise observability of a task but different sensors. The allows the description of a dynamic system in which neither all events nor the time of their occurrence may be predicted in advance. We have developed an experimental system consisting of actuators and both force and position sensors, for carrying out the interactive recovery of functionality. In particular, we demonstrate how this approach can be used by carrying out some experiments investigating the functionality of piercing. Furthermore, we discuss the importance of a multisensory approach for the observation and interpretation of functionality.

MS-CIS-93-77 (DISTRIBUTED SYSTEMS LAB 34) (GRASP LAB 359)

VERSA: A Tool For The Specification and Analysis of Resource-Bound Real-Time Systems

Duncan Clarke, Insup Lee, Hong-liang Xie

VERSA is a tool that assists in the algebraic analysis of real-time systems. It is based on ACSR, a timed process algebra designed to express resource-bound real-time distributed systems. VERSA is designed to be both a usable and useful tool for the analysis of ACSR specifications. Usability is assured by a flexible user interface that uses ACSR's traditional notation augmented with conventions from programming languages and mathematics that allow concise specification of realistic systems. Usefulness is the result of the breadth of analysis techniques planned and currently implemented, including algebraic terms rewriting and state-spaced exploration based techniques.

MS-CIS-93-78 (GRASP LAB 360)

A Vision-Based Learning Method for Pushing Manipulation

Marcos Salganicoff, Giorgio Metta, Andrea Oddera, Guilio Sandini

We describe an unsupervised on-line method for learning of manipulative actions that allows a robot to push an object connected to it with a rotational point contact to a desired point in image-space. By observing the results of its actions on the object's orientation in image-space, the system forms a predictive forward empirical model. This acquired model is used on-line for manipulation planning and control as it improves. Rather than explicitly inverting for forward model to achieve trajectory control, a stochastic action selection technique [Moore, 1990] is used to select the most informative and promising actions, thereby integrating active perception and learning by combining on-line improvement, task-directed exploration, and model exploitation. Simulation and experimental results of the approach are presented.

MS-CIS-93-79 (GRASP LAB 361)

A Direct Approach to Vision Guided Manipulation

Marcos Salganicoff, Giorgio Metta, Andrea Oddera, Giulio Sandini

This paper describes a method for robotic manipulation that uses direct image-space calculation of optical flow information for continuous real-time control of manipulative actions. State variables derived from optical flow measurements are described. The resulting approach is advantageous since it robustifies the system to changes in optical parameters and also simplifies the implementation needed to succeed in the task execution. Two reference tasks and their corresponding experiments are described: the insertion of a pen into a ``cap'' (the capping experiment) and the rotational point-contact pushing of an object of unknown shape, mass and friction to a specified goal point in the image-space.

MS-CIS-93-80 (GRASP LAB 362)

Explicit Forgetting Algorithms for Memory Based Learning

Marcos Salganicoff

Memory-based learning algorithms lack a mechanism for tracking time-varying associative mappings. To widen their applicability, they must incorporate explicit forgetting algorithms to selectively delete observations. We describe Time-Weighted, Locally-Weighted and Performance-Error Weighted forgetting algorithms. These were evaluated with a Nearest-Neighbor Learner in a simple classification task. Locally-Weighted Forgetting outperformed Time-Weighted Forgetting under time-varying sampling distributions and mappings, and did equally well when only the mapping varied. performance-Error forgetting traced about as well as the other algorithms, but was superior since it permitted the Nearest-Neighbor learner to approach the Bayes' misclassification rate when the input/output mapping became stationary.

MS-CIS-93-81 (LINC LAB 256)

p-calculus: A Unifying Framework for Programming Paradigms

Srinivas Bangalore

p-calculus is a calculus for modeling dynamically changing configurations of a network of communicating agents. this paper studies the suitability of p-calculus as a unifying framework to model the operational semantics of the three paradigms of programming: functional, logic and imperative paradigms. In doing so, the attempt is to demonstrate that p -calculus models a primitive that is pervasive in the three paradigms and to illustrate that the three forms of sequential computing are special instances of concurrent computing.

MS-CIS-93-82 (LOGIC & COMPUTATION 72)

What's So Special About Kruskal's Theorem and The Ordinal G₀? A Survey of Some Results In Proof Theory

Jean H. Gallier

This paper consists primarily of a survey of results of Harvey Friedman about some proof theoretic aspects of various forms of Krusal's tree theorem, and in particular the connection with the ordinal G₀. We also include a fairly extensive treatment of normal functions on the countable ordinals, and we give a glimpse of Veblen Hierarchies, some subsystems of second-order logic, slow-growing and fast-growing hierarchies including Girard's result, and Goodstein sequences. The central theme of this paper is a powerful theorem due to Kruskal, the ``tree theorem'', as well as a ``finite miniaturization'' of Kruskal's theorem due to Harvey Friedman. These versions of Kruskal's theorem are remarkable from a proof-theoretic point of view because they are not provable in relatively strong logical systems. They are examples of so-called ``natural independence phenomena'', which are considered by more logicians as more natural than the mathematical incompleteness results first discovered by Gödel. Kruskal's tree theorem also plays a fundamental role in computer science, because it is one of the main tools for showing that certain orderings on trees are well founded. These orderings play a crucial role in proving the termination of systems of rewrite rules and the correctness of Knuth-Bandix completion procedures. There is also a close connection between a certain infinite countable ordinal called G ₀ and Kruskal's theorem. Previous definitions of the function involved in this connection are known to be incorrect, in that, the function is not monotonic. We offer a repaired definition of this function, and explore briefly the consequences of its existence.

MS-CIS-93-83 (LINC LAB 257)

A Computational Model of Syntactic Processing: Ambiguity Resolution From Interpretation (Dissertation)

Michael Niv

Syntactic ambiguity abounds in natural language, yet humans have not difficulty coping with it. In fact, the process of ambiguity resolution is almost always unconscious. But it is not infallible, however, as example 1 demonstrates.

1. The horse raced past the barn fell.

   This sentence is perfectly grammatical, as is evident when it appears in the following context:

2. Two horses were being shown off to a prospective buyer. One was raced past a meadow and the other was raced past a barn.

Grammatical yet unprocessable sentences such as 1 are called 'garden-path sentences.' Their existence provides an opportunity to investigate the human sentence processing mechanism by studying how and when it fails. The aim of this thesis is to construct a computational model of language understanding which can predict processing difficulty. The data to be modeled are known examples of garden path and non-garden path sentences, and other results from psycholinguistics.

It is widely believed that there are two distinct loci of computation in sentence processing: syntactic parsing and semantic interpretation. One longstanding controversy is which of these two modules bears responsibility for the immediate resolution of ambiguity. My claim is that it is the latter, and that the syntactic processing module is a very simple device which blindly and faithfully constructs all possible analyses for the sentence up to the current point of processing. The interpretive module services as a filter, occasionally discarding certain of these analyses which it deems less appropriate for the ongoing discourse than their competitors.

This document is divided into three parts. The first is introductory, and reviews a selection of proposals from the sentence processing literature. The second part explores a body of data which has been adduced in support of a theory of structural preferences -- one that is inconsistent with the present claim. I show how the current proposal can be specified to account for the available data, and moreover to predict where structural preference theories will go wrong. The third part is a theoretical investigation of how well the proposed architecture can be realized using current conceptions of linguistics competence. In it, I present a parsing algorithm and a meaning-based ambiguity resolution method.

MS-CIS-93-84 (LINC LAB 258)

Diagnostic Reasoning and Planning In Exploratory-Corrective Domains (Dissertation)

Ron Rymon

I have developed a methodology for knowledge representation and reasoning for agents working in exploratory-corrective domains. Working within the field of Artificial Intelligence in Medicine, I used the specific problem of diagnosis-and-repair in multiple trauma management as both motivation and testbed for my work.

A reasoning architecture is proposed in which specialized diagnostic reasoning and planning components are integrated in a cycle of reasoning and action/perception:

1. A Goal-Directed Diagnostic (GDD) reasoner which is predicated on the view that diagnosis is only worthwhile to the extent that it can affect repair decisions and that goals can be used to focus on such. Rather than focusing on a diagnosis object as the primary purpose of the diagnostic process, the GDD reasoner is tasked primarily with generating goals for the planner and with reasoning about whether these goals have been satisfied.
2. A Progressive Horizon Planner (PHP) which works by constructing intermediate plans via a combination of plan sketching and selection/optimization sub-processes, and then adapting these plans to reflect new information and goals. For the plan sketching sub-part, I propose a selection-and-ordering planning/scheduling paradigm, taking advantage of the limited interaction between goals.

I have implemented this architecture and reasoning components in TraumAID 2.0 -- a consultation system for the trauma management domain. In a blinded comparison, out of 97 real trauma cases, three trauma surgeons have judged management plans proposed by TraumAID 2.0 preferable to the actual care by a ratio of 64:17 and to plans generated by its predecessor TraumAID~1.0 by a ratio of 62:9.

MS-CIS-93-85 (GRASP LAB 363)

Deterministic Selection on the Mesh and The Hypercube

Sanguthevar Rajasekaran, Shibu Yooseph

In this paper we present efficient deterministic algorithms for selection on the mesh connected computers (referred to as the mesh from hereon) and the hypercube. Our algorithm on the mesh runs in time O([n/p] log log p + Öp log n) where n is the input size and p is the number of processors. The time bound is significantly better than that of the best existing algorithms when n is large. The run time of our algorithm on the hypercube is O ([n/p] log log p +T^s_p log n), where T^s_p is the time needed to sort p element on a p-node hypercube. In fact, the same algorithm runs on an network in time O([n/p] log log p +T^s_p log), where T^s_p is the time needed for sorting p keys using p processors (assuming that broadcast and prefix computations take time less than or equal to T^s_p.

MS-CIS-93-86 (LINC LAB 259)

A Corpus-Based Approach to Language Learning (Dissertation)

Eric Brill

One goal of computational linguistics is to discover a method for assigning a rich structural annotation to sentences that are presented as simple linear strings of words; meaning can be much more readily extracted from a structurally annotated sentence than from a sentence with no structural information. Also, structure allows for a more in-depth check of the well-formedness of a sentence. There are two phases to assigning these structural annotations: first, a knowledge base is created and second, an algorithm is used to generate a structural annotation for a sentence based upon the facts provided in the knowledge base. Until recently, most knowledge bases were created manually by language experts. These knowledge bases are expensive to create and have not been used effectively in structurally parsing sentences from other than highly restricted domains. The goal of this dissertation is to make significant progress toward designing automate that are able to learn some structural aspects of human language with little human guidance. In particular, we describe a learning algorithm that takes a small structuraally annotated corpus of text and a larger unannotated corpus as input, and automatically learns how to assign accurate structural descriptions to sentences not in the training corpus. The main tool we use to automatically discover structural information about language from corpora is transformation-based error-driven learning. the distribution of errors produced by an imperfect annotator is examined to learn an ordered list of transformations that can be applied to provide an accurate structural annotation. We demonstrate the application of this learning algorithm to part of speech tagging and parsing. Successfully applying this technique to create systems that learn could lead to robust, trainable and accurate natural language processing systems.

MS-CIS-93-87 (LINC LAB 260)

Building A Large Annotated Corpus of English: The Penn Treebank

Mitchell P. Marcus, Beatrice Santorini, Mary Ann Marcinkiewicz

In this paper, we review our experience with constructing one such large annotated corpus--the Penn Treebank, a corpus consisting of over 4.5 million words of American English. During the first three-year phase of the Penn Treebank Project (1989-1992), this corpus has been annotated for part-of-speech (POS) information. In addition, over half of it has been annotated for skeletal syntactic structure.

MS-CIS-93-88 (DISTRIBUTED SYSTEMS LAB 35)

Evaluation of the GLINK Chip Set As A Data Link Layer for Local ATM

Chris Russo

The introduction of the HDMP-1000 Gigabit Rate Transmit/Recieve (GLINK) Chip Set by Hewlett-Packard has provided a hardware device capapble of matching SONET STS-3c up to nearly STS-24c rates over either coaxial cable or optical fiber. The capability enables high speed local communication over a low cost medium, and lends itself well to use as both the physical and the data link layers for ATM in a local (few hundred feet) environment. This paper analyzes the capabilities of the GLINK chip set in terms of link length and data rate trade-offs, and in terms of its usefulness as a physical and DLL for local ATM.

MS-CIS-93-89 (GRASP LAB 364)

A Compiler Project for Translating a C Subset to SPARC Assembly Language

Duncan E. Clarke, Richard P. Paul

We present a complete description of a project for a compiler that translates a subset of the C programming language to SPARC assembler language. The project is suitable for a one semester undergraduate course on compilers and interpreters based on the text of Aho, Sethi, and Ullman, and has been used successfully in that context at the University of Pennsylvania. Output that facilitate scoring, and checkpoints for monitoring the students' progress are integral to the project description.

MS-CIS-93-90 (GRASP LAB 365)

Robust Hypothesis Testing and Statistical Color Classification (Dissertation)

Julie a. Adams

The purpose of this research is twofold: ( i) the development of a mathematical model for statistical color classification; and ( ii ) the testing of this model under controlled conditions.

We consider the following hypothesis testing problem: Let Z = q + V, where the scalar random variable Z denotes the sampling model, qÎ W is a location parameter, W Ì R, and V is additive noise with cumulative distribution function F. We assume F is unacertain, i.e., F Î \cal F, where \cal F denotes a given uncertainty class of absolutely continuous distributions with a parametric or semiparametric description. The null hypothesis is H₀: q Î W,  F Î \cal F and the alternative hypothesis is H₁: q\not Î W, F Î \cal F.

Through controlled testing we show that this model may be used to statistically classify colors. The color spectrum we use in these experiments is the Munsell color system which combines the three qualities of color sensation: Hue, Chroma and Value. The experiments show: ( i ) The statistical model can be used to classify colors in the Munsell color system; ( ii ) more robust results are achieved by using a Chroma-Hue match instead of a Perfect match; ( iii ) additional robustness can be achieved by classifying a color based on measurements averaged over a neighborhood of pixels verses measurements at a single pixel; and ( iv ) a larger color spectrum than the Munsell color system is needed to classify a range of man-made and natural objects.

MS-CIS-93-91 (LOGIC & COMPUTATION 73)

Proving Properties of Typed l-Terms Using Realizability, Covers, and Sheves

Jean Gallier

We present a general method for proving properties of typed l-terms. This method is obtained by introducing a semantic notion of realizability which uses the notion of a cover algebra (as in abstract sheaf theory). For this, we introduce a new class of semantic structures equipped with preorders, called pre-applicative structures. These structures need not be extensional. In this framework, a general reaalizability theorem can be shown. Kleene's recursive realizability and a variant of Kreisel's modified realizability both fit into this framework. Applying this theorem to the special case of the term model, yields a general theorem for proving properties of typed l-terms, in particular, strong normalization and confluence. This approach clarifies the reducibility method by showing that the closure conditions on candidates of reducibility can be viewed as sheaf conditions. The above approach is applied to the simply-typed l-calculus (with types ®, x, +, and ^), and to the second-order (polymorphic l-calculus (with types ® and "²), for which it yields a new theorem.

MS-CIS-93-92 (LINC LAB 261)

Selection and Information: A Class-Based Approach to Lexical Relationships (Dissertation)

Philip S. Resnik

Selectional constraints are limitations on the applicability of predicates to arguments. For example, the statement ``The number two is blue'' may be syntactically well formed, but at some level it is anomalous --- blue is not a predicate that can be applied to numbers.

In this dissertation, I propose a new, information-theoretic account of selectional constraints. Unlike previous approaches, this proposal requires neither the identification of primitive semantic features nor the formalization of complex inferences based on world knowledge. The proposed model assumes instead that lexical items are organized in a conceptual taxonomy according to class membership, where classes are defined simply as sets --- that is, extensionally, rather than in terms of explicit features or properties. Selection is formalized in terms of a probabilistic relationship between predicates and concepts: the selectional behavior of a predicate is modeled as its distributional effect on the conceptual classes of its arguments, expressed using the information-theoretic measure of relative entropy. The use of relative entropy leads to an illuminating interpretation of what selectional constraints are: the strength of a predicate's selection for an argument is identified with the quantity of information it carries about that argument.

In addition to arguing that the model is empirically adequate, I explore its application to two problems. The first concerns a linguistic question: why some transitive verbs permit implicit direct objects (``John ate Æ and others do not (``*John brought Æ"). It has often been observed informally that the omission of objects is connected to the ease with which the object can be inferred. I have made this observation more formal by positing a relationship between inferability and selectional constraints, and have confirmed the connection between selectional constraints and implicit objects in a set of computational experiments.

Second, I have explored the practical applications of the model in resolving syntactic ambiguity. A number of authors have recently begun investigating the use of corpus-based lexical statistics in automatic parsing; the results of computational experiments using the present model suggest that often lexical relationships are better viewed in terms of underlying conceptual relationships such as selectional preference and concept similarity. Thus the information-theoretic measures proposed here can serve not only as components in a theory of selectional constraints, but also as tools for practical natural language processing.

MS-CIS-93-93 (LINC LAB 262)

Understanding Natural Language Instructions: A Computational Approach to Purpose Clauses (Dissertation)

Barbara Di Eugenio

Human agents are extremely flexible in dealing with Natural Language instructions. I argue that most instructions don't exactly mirror the agent's't knowledge, but are understood by accommodating them in the context of the general plan the agent is considering; the accommodation process is guided by the goal(s) that the agent is trying to achieve. Therefore a NL system which interprets instructions must be able to recognize and/or hypothesize goals; it must make use of a flexible knowledge representation system, able to support the specialized inferences necessary to deal with input action description that do not exactly match the stored knowledge.

The data that support my claim are Purpose Clauses (PC's), infinitival constructions as in a to do b, and Negative Imperatives. I present a pragmatic analysis of both PCs and negative Imperatives. Furthermore, I analyze the computational consequences of PCs, in terms of the relations between actions PCs express, and of the inferences an agent has to perform to understand PCs.

I propose an action representation formalism that provides the required flexibility. It has two components. The Terminological Box (TBox) encodes linguistic knowledge about actions, and is expressed by means of the hybrid system CLASSIC [Brachman et al., 1991].

To guarantee that the primitives of the representation are linguistically motivated, I derive them from Jackendoff's work on Conceptual Structures [1983; 1990]. The Action Library encodes planning knowledge about actions. The action terms used in the plans are those defined in the TBox.

Finally, I present an algorithm that implements inferences necessary to understand Do a to do b, and supported by the formalism I propose. In particular, I show how the TBox classifier is used to infer whether a can be assumed to match one of the substeps in the plan for b, and how expectations necessary for the match to hold are computed.

MS-CIS-93-94 (LOGIC & COMPUTATION 74)

Facilitating Transformations in a Human Genome Project Database

S.B. Davidson, A.S. Kosky, B. Eckman

Human Genome Project databases present a confluence of interesting database challenges: rapid schema and data evolution, complex data entry and constraint management, and the need to integrate multiple data sources and software systems which range over a wide variety of models and formats. While these challenges are not necessarily unique to biological databases, their combination, intensity and complexity are unusual and make automated solutions imperative. We illustrate these problems in the context of the Human Genome Database for Chromosome 22 (Chr22DB), and describe a new approach to a solution for these problems, by means of a deductive language for expressing database transformations and constraints.

MS-CIS-93-95 (LOGIC & COMPUTATION 75)

A Bounded Degree Property and Finite-Cofiniteness of Graph Queries

Leonid Libkin, Limsoon Wong

We provide new techniques for the analysis of the expressive power of query languages for nested collections. These languages may use set or bag semantics and may be further complicated by the presence of aggregate functions. We exhibit certain classes of graphics and prove that properties of these graphics that can be tested in such languages are either finite or cofinite. This result settles that conjectures of Grumbach, Milo, and Paredaens that parity test, transitive closure, and balanced binary tree test are not expressible in bah languages like BALG of Grumbach and Milo and \calBQL of Libkin and Wong. Moreover, it implies that many recurisive queries, including simple ones like test for a chain, cannot be expressed in a nested relational language even when aggregate functions are available. In an attempt to generalize the finte-cofiniteness result, we study the bounded degree property which says that the number of distinct in- and out-degrees in the output of a graph query does not depend on the size of the input if the input is ``simple.'' We show that such a property implies a number of inexpressibility results in a uniform fastion. We then prove the bounded degree property for the nested relational language.

MS-CIS-93-96 (GRASP LAB 366)

Extended Intensity Range Imaging

Brian C. Madden

A single composite image with an extended intensive range is generated by combining disjoining regions from different images of the same scene. The set of images is obtained with a charge-couple device (CCD) set for different flux integration times. By limiting differences in the integration times so that the ranges of output pixel values overlap considerably, individual pixels are assigned the value measured at each spatial location that is in the most sensitive range where the values are both below saturation and are most precisely specified. Integration times are lengthened geometricalaly from a minimum where all pixel values are below saturation until all dark regions emerge from the lowest quantization level. the method is applied to an example scene and the effect the composite images have on traditional low-level imaging methods also is examined.

MS-CIS-93-97

Convex Hulls: Complexity and Applications (A Survey)

Suneeta Ramaswami

Computational geometry is, in brief, the study of algorithms for geometric problems. Classical study of geometry and geometric objects, however, is not well-suited to efficient algorithms techniques. thus, for the given geometric problems, it becomes necessary to identify properties and concepts that lend themselves to efficient computation. The primary focus of this paper will be on one such geometric problems, the Convex Hull problem.

MS-CIS-93-98

Algorithmic Motion Planning and Related Geometric Problems on Parallel Machines (Dissertation Proposal)

Suneeta Ramaswami

MS-CIS-93-99

Optimal Parallel Randomized Algorithms for the Boronoi Diagram of Line Segments In The Plane and Related Problems

Sanguthevar Rajasekaran

In this paper, we present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n non-intersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(logn) time with very high probability and uses O(n) processors on a CRCW PRAM. This algorithm is optimal in terms of P.T bounds since the sequential time bound for this problem is W(n logn). Our algorithm improves by an O(logn) factor the previously best known deterministic parallel algorithm which runs in O(log ² n) time using O(n) processors. We obtains this result by using random sampling at ``two stages'' of our algorithm and using efficient randomized search techniques. This technique gives a direct optimal algorithm for the Voronoi diagram of points as well (all other optimal parallel algorithms for this problem use reduction from the 3-d convex hull construction).

MS-CIS-93-100

Network Service Customization: End-Point Perspective (Proposal)

Klara Nahrstedt

An important problem with cell-switched technologies such as Asynchronous Transfer Mode (ATM) is the provision of customized multiplexing behavior to applications. This customization takes the form of setting up processes in the network and end-points to meet application ``Quality of Service'' (QoS) requirements.

The proposed thesis work examines the necessary components of a software architecture to provide QoS in the end-points of a cell-switched network. An architecture has been developed, and the thesis work will refine it using a ``driving'' application of the full-feedback teleoperation of a robotics system.

Preliminary experimental results indicate that such teleoperation is possible using general-purpose workstations and a lightly-loaded ATM link. An important result of the experimental portion of the thesis work will be a study of the domain of applicability for various resource management techniques.

MS-CIS-93-101 (GRASP LAB 367)

Control of Visually Guided Behaviors

Jana Kosecká, Ruzena Bajcsy, Max Mintz

We propose an approach for modeling visually guided behaviors of agents which explore and navigate in unknown and partially known environments. Behaviors are modeled as finite state machines (FSM), where the states of the model correspond to particular continuous control strategies and the transitions between them are caused by events representing qualitative or asynchronous changes in the behavior evolution. In order to prevent conflicts in parallel execution of multiple behaviors we adopt the supervisory control theory of discrete Event System (DES). Modeling the participating processes using the DES framework allows us to capture often complex interactions between components of the system and synthesize the resulting supervisor, guaranteeing the overall controllability of the system at the discrete event level. In the real world agents have multiple options/paths for carrying out their task. Hence there is a need for selecting different control strategies based on efficiency and safety criteria. We have included in our formalism a measure of efficiency as the nominal cost (in our case, the traversal time) and a measure of safety at the risk cost (in our case, the inverse of the distance between the agent and obstacles). Experiments have been carried out testing the described formalism with one agent carrying out the task of avoiding an obstacle in its path while tracking a target.

MS-CIS-93-102 (LINC LAB 263)

Using Context To Specify Intonation In Speech Synthesis

Scott Prevost, Mark Steedman

A generator based on Combinatory Categorial Grammar using a simple and domain-independent discourse model can be used to direct synthesis of intonation contours for responses to data-base queries, conveying distinctions of contrast and emphasis determined by the discourse model and the state of the knowledge-base.