[ont.events] U of Toronto Computer Science activities, Oct. 26-30

clarke@utcsri.UUCP (10/16/87)

         (SF = Sandford Fleming Building, 10 King's College Road)
              (GB = Galbraith Building, 35 St. George Street)

SUMMARY:

A.I. SEMINAR, Tuesday, October 27, 2 pm, GB244 -- Alan Mackworth:
     "The Logic of Depiction"

SYSTEMS SEMINAR, Thursday, October 29, 11 am,  SF1101 -- Rob Pike:
     "A Distributable Architecture"

THEORY SEMINAR, Thursday, October 29,  3 pm, GB244 -- Arnold L. Rosenberg:
     "On Evaluating Parallel Architectures via Graph Embeddings"

---------------------------------

              A.I. SEMINAR, Tuesday, October 27, 2 pm, GB244

                         Professor Alan Mackworth
                 Canadian Institute for Advanced Research
                                    and
                      University of British Columbia

                         "The Logic of Depiction"
        (This talk describes work done jointly with Raymond Reiter)

     We propose a theory of depiction and interpretation that formalizes
image domain knowledge, scene domain knowledge and the depiction mapping
between the image and scene domains.  This theory is illustrated by speci-
fying some general knowledge about maps, geographic objects and their dep-
iction relationships in first order logic with equality. An interpretation
of an image is defined to be a logical model of the general knowledge and a
description of that image.  For the simple map world we show how the task
level specification may be refined to a provably correct implementation by
invoking model preserving transformations on the logical representation. In
addition, we sketch logical treatments for querying an image, incorporating
contingent scene knowledge into the interpretation process, occlusion,
ambiguous image descriptions, and composition.  This approach provides a
formal framework for analyzing existing systems such as Mapsee, and for
understanding the use of constraint satisfaction techniques.  It also can
be used to design and implement vision and graphics systems that are
correct with respect to the task and algorithm levels.

           SYSTEMS SEMINAR, Thursday, October 29, 11 am,  SF1101

                            Professor Rob Pike
                              AT&T Bell Labs

                      "A Distributable Architecture"
        (the work described is in collaboration with Ken Thompson).

     This talk will describe and defend a new distributable
hardware/software system currently under experimental development at Bell
Labs.  The new architecture is a compromise between classical centralized
timesharing and autonomous workstations.

            THEORY SEMINAR, Thursday, October 29,  3 pm, GB244

                       Professor Arnold L. Rosenberg
                        University of Massachusetts

                   "On Evaluating Parallel Architectures
                           via Graph Embeddings"

     We study a genre of parallel architecture that is well suited for
implementation using integrated circuit technology, namely, arrays of
identical processing elements.  A central problem in the design of proces-
sor arrays is to evaluate the viability of a proposed architecture.  One
vehicle for such evaluation is the theory of graph embeddings:  One views
the proposed array as an undirected graph, whose structure represents the
interprocessor communication structure of the array.  One then tries to
embed in this architecture-graph a algorithmics paradigms; for instance,
binary trees abstract the dependencies of divide-and- conquer algorithms,
FFT graphs abstract the dependencies of convolution-based algorithms,
meshes abstract the dependencies of grid-based algorithms, and so on.  The
efficiency of an embedding is measured in terms of its dilation, which
quantifies the delay incurred by implementing the "guest" algorithm on the
"host" architecture, and of tis expansion, which quantifies the efficiency
of resource utilization in the implementation.  We illustrate the relevant
ideas by surveying recent (dilation- and expansion-) optimal embeddings of
grids, binary trees, and FFT graphs in Boolean hypercubes.  These studies
were done jointly with subsets of Sandeep Bhatt (Yale), Fan Chung
(BellCoRe), Lenny Heath (MIT), and Tom Leighton (MIT).
-- 

Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
              (416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke