clarke@csri.toronto.edu (Jim Clarke) (02/23/88)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
(WB = Wallberg Building, 184 College Street)
SUMMARY:
COMBINATORICS SEMINAR, Monday, February 29, 3 pm, SF1105 -- Teresa Przytzcka:
"Parallel tree contraction"
NUMERICAL ANALYSIS SEMINAR, Tuesday, March 1, 10 am, WB242 -- Michel Verhaegen:
"Interdisciplinary Research Between Numerical Analysis and Systems Theory"
A.I. SEMINAR, Tuesday, March 1, 2 pm, SF1105 -- Daniel Lehmaan:
"Non-monotonic Logics: Models and Proofs"
THEORY SEMINAR, Thursday, March 3, 3 pm, GB244 -- Cynthia Dwork:
"Interactive Proof Systems With Finite State Verifiers"
SYSTEMS SEMINAR, Friday, March 4, 2 pm, GB220 -- W. Bruce Croft:
"Resolving Plan Failures Through Explanations"
--------------------
COMBINATORICS SEMINAR, Monday, February 29, 3 pm, SF1105
Ms. Teresa Przytzcka
University of British Columbia
"Parallel tree contraction"
The tree contraction problem is to reduce a noted tree to its root by a
sequence of independent vertex removal. A simple parallel reduction from
the tree contraction problem to list ranking will be presented. The reduc-
tion leads to an efficient parallel tree contraction algorithm. Tree con-
traction can be viewed as a general technique for scheduling parallel com-
putations on trees. A broad class of parallel tree computations to which
the tree contraction technique apply will be described.
NUMERICAL ANALYSIS SEMINAR, Tuesday, March 1, 10 am, WB242
Dr. Michel Verhaegen
Ames Research Center
"Interdisciplinary Research Between
Numerical Analysis and Systems Theory"
A.I. SEMINAR, Tuesday, March 1, 2 pm, SF1105
Professor Daniel Lehmaan
Hebrew University
"Non-monotonic Logics: Models and Proofs"
A general framework for the study of non monotonic logics is proposed. It
focuses (as proposed by Dov Gabbay) on the notion of a non monotonic deduc-
tion and the derivability of such deductions from others. Inference rules
that should hold in all non monotonic logics are described (essentially
those of Gabbay); additional rules are discussed. A set of non monotonic
deductions provides a general knowledge base from which one, on the basis
of specific information about the world, may draw probable conclusions by
use of the inference rules. The main point of this paper is the definition
of the semantics of non monotonic deduction. The semantics are defined
using possible worlds models in which some worlds are more natural than
others. A soundness and completeness proof shows that the models match
exactly the inference rules proposed. This should be considered a step
towards the general study and the classification of the different non mono-
tonic logics. This paper is restricted to propositional logics.
THEORY SEMINAR, Thursday, March 3, 3 pm, GB244
Dr. Cynthia Dwork
IBM Almaden Research Center
"Interactive Proof Systems With Finite State Verifiers"
An Interactive Proof System (IPS) for a language L is a two-party protocol
whereby a "prover" convinces a "verifier" that members x of L are actually
in L. Both the prover and the verifier can make random moves (flip coins).
An interesting type of IPS is the "zero-knowledge" IPS which has the pro-
perty that no verifier can extract any information from the interactive
proof of membership of x in L, except for the fact that x is in L, i.e.,
nothing extra is learned. To date, almost all research on interactive
proof systems has dealt with the case that the verifier is a probabilistic
Turing machine which runs in polynomial time. Due to the present lack of
understanding of the power of polynomial time computation, many previous
results are based on unproved assumptions, typically that a certain problem
cannot be solved in polynomial time. By restricting the computational
power of the verifier to a model in which we were able to obtain signifi-
cant lower bounds, namely, by restricting the verifier to be a probabilis-
tic finite state automaton, we demonstrated more structure in the class of
languages having interactive proof systems, without using unproved assump-
tions. Results of this type will be discussed. For example, there is a
language L such that L has an IPS, but L has no zero knowledge IPS. There
is a language L', not recognizable by any polynomial time probabilistic
finite state automaton, that has a polynomial time zero-knowledge IPS.
This is joint work with Larry Stockmeyer.
SYSTEMS SEMINAR, Friday, March 4, 2 pm, GB220
Professor W. Bruce Croft
University of Massachusetts
"Resolving Plan Failures Through Explanations"
In an environment where multiple agents cooperate to achieve goals, a
planner can be used to coordinate the actions of these agents and to check
for problems. The knowledge base of such a planner will typically be
incomplete and potentially incorrect. In these circumstances, plan
failures or exceptions to the expected actions will inevitably happen. In
this talk, an approach to resolving these failures will be discussed. The
approach is similar in many respects to explanation-based learning and
incorporates negotiation between agents as an essential part of confirming
explanations and acquiring new knowledge. An example taken from a testbed
system, POLYMER, will be presented.
--
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