Path: utzoo!yunexus!telly!tmsoft!dptcdc!jarvis.csri.toronto.edu!csri.toronto.edu!clarke
From: clarke@csri.toronto.edu (Jim Clarke)
Newsgroups: ont.events
Subject: U of Toronto theory seminars, May 8 and 11
Message-ID: <8905041342.AA00471@yorkville.csri.toronto.edu>
Date: 4 May 89 13:42:20 GMT
Article-I.D.: yorkvill.8905041342.AA00471
Distribution: ont
Organization: University of Toronto, CSRI
Lines: 100


CHANGE OF LOCATION:  The AI seminar by Len Schubert on Thursday, May 11
    at 11 a.m. will be held in >>>> Room SF 1101.
        ___________________________________________________

     (SF = Sandford Fleming Building, 10 King's College Road)
          (GB = Galbraith Building, 35 St. George Street)
        (Events usually begin at 10 minutes past the hour.)

SUMMARY:

THEORY SEMINAR - Monday, May 8, 2 p.m. in Room SF 4102 -- Shai Ben-David
            "All We believe Fails in Impossible Worlds
   A possible-world semantics for a 'knowing at most' operator"

THEORY SEMINAR - Thursday, May 11, 3 p.m.  in  Room  GB 244 -- Nader H. Bshouty
 "Lower bounds for algebraic computation trees of functions with finite domains"

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

THEORY SEMINAR - Monday, May 8, 2 p.m. in Room SF 4102

                          Shai Ben-David
                        Technion University

            "All We believe Fails in Impossible Worlds
   A possible-world semantics for a 'knowing at most' operator"

We extend the familiar possible-world semantics of modal logic by
considering the 'impossible' worlds of a Kripke structure.  We
obtain a simple semantics for Levesque's "All I know" logic.  We
provide a natural proof theory and prove the expected soundness and
completeness theorems.

>From a mathematical point of view we offer a natural
generalization of modal logic that significantly strengthens its
expressive power.  Considered in the context of Knowledge
Representation such a logic is a standard monotonic logic that
allows formal treatment of default reasoning.

THEORY SEMINAR - Thursday, May 11, 3 p.m.  in  Room  GB 244

                         Nader H. Bshouty
                        Technion University

"Lower bounds for algebraic computation trees of functions with finite domains"

[Sorry about the incomplete translation from eqn input; ASCII just can't
handle this stuff.  We've lost some operator precedence, so you'll have
to figure out how far "sub" and "sup" should apply all on your own.
Also, "(" and "(=" mean (proper) subset.  Good luck.  -- the poster ]

Let F be a field. We prove lower bounds on the depth of
computation trees with the operations {+,-,x,/} UE
that computes functions f:A->B, where E is the set of
all the functions g:F sup r ->{YES,NO}, A (  F sup r
finite and B (= F sup s.

For every field F and for every sufficiently large finite domain
A we prove the following

(i)The optimal algorithms that computes a set of rational func-
    tions are straight line algorithms.

(ii)
    Lower bounds for functions with the operations {+,-,x,/,||,max,min}.

(iii)
    A lower bound H ( lambda sub 1 ,..., lambda sub f) n for
    Merge (A sub 1 ,..., A sub f) where A sub i  is a
    sequence of lambda sub i n ordered elements where sum sub
    i=1 sup f lambda sub i eq 1 and H is the entropy function.

(iv)
    A lower bound OMEGA(n log n) for sorting n elements.

(v)
    A lower bound OMEGA(log n) for a mod b where
    a,b member {1,...,n}.

(vi)
    A lower bound OMEGA(n) for a(x) mod b(x) where
    deg a(x),deg b(x) <= n.

(vii)
    A lower bound OMEGA(log n) for gcd(a,b) where
    a,b member {1,...,n}.

(viii)
    A lower bound OMEGA(n) for gcd(a(x),b(x))
    where deg a(x),deg b(x) <= n .

(ix)
    A lower bound OMEGA(n) for a and b and a or b
    where a,b member {0,...,2 sup n - 1}.
-- 
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
              (416) 978-4058
clarke@csri.toronto.edu     or    clarke@csri.utoronto.ca
   or ...!{uunet, pyramid, watmath, ubc-cs}!utai!utcsri!clarke