clarke@csri.toronto.edu (Jim Clarke) (05/04/89)
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