[ont.events] U of Toronto Computer Science seminars, Oct. 10-21

clarke@csri.toronto.edu (Jim Clarke) (09/30/88)

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

SUMMARY:

SYSTEMS SEMINAR - Oct.13, Thursday, 3 p.m. in GB221 -- Didier Plateau:
     "02: An Object-oriented Multilanguage Distributed Database System"

COMBINATORICS/THEORY SEMINAR - Oct.14, Friday, 11 a.m. in GB220 -- Michel Habib:
     "Comparability Invariance and Related Notions"

COMBINATORICS/THEORY SEMINAR - Oct. 17, Monday, 3 a.m. in GB119
     Michael A. Langston:
          "On Algorithmic Applications of Well-Partial-Order Theory
                    and Constructive Search Complexity"

COLLOQUIUM - October 18, Tuesday, 11 a.m. in SF 1105 -- E.C.R. Hehner:
     "Formalist Heresy: Mathematics is based on Programming"

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

SYSTEMS SEMINAR - Oct.13, Thursday, 3 p.m. in GB221

                              Didier Plateau
                         GIP Altair, INRIA, France

    "02: An Object-oriented Multilanguage Distributed Database System"

The Altair group is prototyping a full database system.
Hardware configuration consists in a bunch of workstations connected to a
database server through a local network.

     The main components of the system are:

-    an object manager in charge of object persistancy, disk and network
     management, concurrency control and recovery.

-    a multilanguage object oriented programming interface.  An object
     oriented layer has been added to existing programming languages.

-    a full programming environment, including browsing, programming, docu-
     menting facilities.  The environment also includes powerful tols to
     build user interfaces.

The talk will give an overview of the system.

COMBINATORICS/THEORY SEMINAR - Oct.14, Friday, 11 a.m. in GB220

                               Michel Habib
                     Universite de Montpellier, France

              "Comparability Invariance and Related Notions"

This talk will present some recent results of Kelly, Mohring and
myself about non trivial comparability invariants.

     First we prove the comparability invariance of interval dimension of
partially ordered sets, i.e. all the partial orders that have the same
underlying comparability graph have the same interval dimension.  This
solves a problem of Dagan, Golumbic and Pinter (1987).

     Some extensions and related problems are also presented.

     As an application, a polynomial time algorithm for the recognition of
trapezoid graphs and orders is presented.  This algorithm solves a problem
of Dagan, Golumbic and Pinter (1987) and also of Yannakakis (1982), since
trapezoid orders are exactly the partial orders with interval dimension 2.

COMBINATORICS/THEORY SEMINAR - Oct. 17, Monday, 3 a.m. in GB119

                            Michael A. Langston
                      Department of Computer Science
                        Washington State University

         "On Algorithmic Applications of Well-Partial-Order Theory
                    and Constructive Search Complexity"

I shall demonstrate how recent advances in the theory of well-
partially-ordered sets can be employed to prove the existence of decision
algorithms with low-degree polynomial running times for a number of seem-
ingly difficult combinatorial problems.  Some of these problems were not
previously known to be in P at all; others were only known to be in P
by way of brute force or dynamic programming formulations with unboundedly
high-degree polynomial running times.  The methods I shall describe include
the application of the powerful Robertson-Seymour theorems on the well-
partial-ordering of graphs under both the minor and immersion orders.

     I shall also discuss the complexity of associated search problems,
presenting a general line of attack that interleaves self-reduction with
obstruction testing to identify correct algorithms.  Curiously, this
approach can be extended, using a novel idea originally suggested by Levin,
so that (in principle) one can write down an algorithm that is guaranteed
to run in asymptotically-optimal time even though its time complexity can-
not be deduced from its description or its behavior.  An interesting corol-
lary of all this is that if the inherently non-constructive tools from
well-partial-order theory should be used to prove P not= NP (admittedly an
unlikely event, but one with the potential to render NP-completeness
proofs useless as polynomial-time algorithms), then the aforementioned
approach insures a constructive proof as well.  This talk reflects work
performed jointly with Michael R. Fellows.

COLLOQUIUM - October 18, Tuesday, 11 a.m. in SF 1105

                               E.C.R. Hehner
           Department of Computer Science, University of Toronto

          "Formalist Heresy: Mathematics is based on Programming"

We argue the merits of a formalist approach to mathematics, with
a semantics based on programming.  We examine the challenges to the formal-
ist position posed by Cantor's diagonal argument, by G"oedel's incomplete-
ness theorem, and by Turing's halting problem.
-- 
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
              (416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu     CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke