clarke@utcsri.UUCP (Jim Clarke) (03/24/86)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
(RS = Rosebrugh Building, Taddlecreek Road)
SYSTEMS SEMINAR, Tuesday, April 1, 11 am, GB 221
Professor Thanasis Hadzilacos
Technical University of Patra, Greece
"When can a schedule forget about a transaction?"
We examine the issue of when a conflict graph-based database scheduler
can "forget about" transactions that have terminated. We give a necessary
and sufficient condition on when it is safe to remove a transaction from
the conflict graph without impairing the scheduler's ability to detect
cycles in any possible future. The condition can be tested in polynomial
time and be applied repeatedly. A counter-intuitive phenomenon is that
there may be two transactions each of which can be safely removed but
removing both engenders the possibility of future scheduling errors. When
several transactions are eligible for removal, we can determine in polyno-
mial time whether a given subset of them can be (simultaneously) removed.
However, finding a maximum cardinality set of such transactins is NP-
complete. (This is joint work with Mihalis Yannakakis of AT&T Bell Labs.)
AI SEMINAR, Tuesday, April 1, 3 pm, SF 1105
Rayan Zachariassen
DCS, University of Toronto
"A Hypothesis Management System for Krypton"
This talk describes a proposed set of tools for manipulating
hypotheses in the framework of the knowledge representation language Kryp-
ton. The objective is to provide a user with consistent default mechanisms
for creating, evaluating, reasoning with, and maintaining, hypotheses. The
premises are the features of Krypton, and a desire to employ hypothesis
goodness measures that are based in Dempster-Shafer Belief Theory. The
mechanisms described are intended to be layered on top of Krypton, though
the ideas are applicable to other KR languages.
SYSTEMS SEMINAR, Thursday, April 3, 11 am, GB 220
Allen Stoughton
University of Goteborg
"Fully Abstract Models of Programming Languages"
THEORY SEMINAR, Thursday, April 3, 3 pm, SF 1101
Professor S. Goldwasser
M.I.T.
"Interactive Proof Systems versus Arthur-Merlin Games"
THEORY SEMINAR, Friday, April 4, 11 am, RS 211
Professor Silvio Micali
M.I.T.
"Byzantine Agreement in Constant Expected Time"
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,ihnp4,linus,utzoo}!utcsri!clarke