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