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.