clarke@csri.toronto.edu (Jim Clarke) (10/15/88)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
AI SEMINAR - Thursday, November 3, 11 a.m. in SF1105 -- Wiktor Marek:
"On the Semantics of Default Logic"
THEORY SEMINAR - Thursday, November 3, 3 p.m. in GB 221 -- Prabhakar Raghavan:
"Searching a graph with bounded space"
COMBINATORICS SEMINAR - Monday, Nov. 7, 3 p.m. in GB119 -- N. Chandrasekharan:
"Fast Parallel Algorithms for Tree Decomposing and Parsing
Partial k-Trees"
COLLOQUIUM - Tuesday, November 8, 11 a.m. in SF1105 -- T.H. Merrett:
"Aldat - Towards a Relational Programming Language"
THEORY SEMINAR - Thursday, November 10, 3 p.m. in GB 221 -- Neil Immerman:
"Descriptive and Computational Complexity"
--------------------
AI SEMINAR - Thursday, November 3, 11 a.m. in SF1105
Wiktor Marek
Department of Computer Science
University of Kentucky
"On the Semantics of Default Logic"
Abstract. At least two different types of structures are proposed as
correct semantics for logic of defaults: Minimal sets of formulas closed
under defaults and fixed points of Reiter's operator GAMMA. In some cases
these notions coincide, but generally it is not the case. In addition Kono-
lige identified Reiter's fixed points (so called extensions) with certain
class of autoepistemic expansions of Moore.
We identify another class of structures for defaults, called weak
expansions and show one to one correspondence between Moore's autoepistemic
expansions and weak extensions. This functor extends Konolige's correspon-
dence. We show that expressibility power of autoepistemic logic (with
expansions as intended structures) is precisely same as default logic with
weak expansions.
THEORY SEMINAR - Thursday, November 3, 3 p.m. in GB 221
Prabhakar Raghavan
IBM Research, Yorktown Heights
"Searching a graph with bounded space"
Abstract. We are interested in space-bounded computation for determining
s-t connectivity in an undirected graph on n nodes; our results here
pertain to bounded-degree graphs. We are given space P = P(n) registers
each of which can hold a log n-bit number (say a node name). Thus
P = 0(1) would correspond to logspace, for which AKLLR's algorithm would
run it time O(n ** (2 log n)). At the other extreme, P = c . n would
permit us to do depth-first search in time O(n). We give an algorithm to
bridge the gap in between.
Results:
1. Let G be a connected graph, and log 2 n < P < n/log 2n.
For Prandom walks each starting from the stationary distribution,
each walk of length (c . (n ** 2) log 3n)/P ** 2, every
vertex in G is visited by some walk with probability exceeding
1 - n ** -c'. Thus we have a total number of steps of
(c . n ** 2 log 3n)/P for ``covering'' the graph. Unlike AKLLR, covering
here doesn't immediately yield ustcon (the P walks start from
different vertices).
2. There is an algorithm that will almost surely decide ustcon with one-
sided error; i.e., if s and t are in the same connected component,
it will fail to recognize this with probability O(1/n ** c1) in
running time (c2 . n ** 2 log 4n)/P.
Joint work with A. Broder, A. Karlin, E. Upfal.
COMBINATORICS SEMINAR - Monday, November 7, 3 p.m. in GB119
N. Chandrasekharan
Clemson University
"Fast Parallel Algorithms for Tree Decomposing and Parsing
Partial k-Trees"
Abstract. We present parallel algorithms for constructing a tree decompo-
sition (as introduced by Robertson and Seymour) and a parse-tree (as intro-
duced by Wimer) for partial k-trees. We show that a tree decomposition can
be constructed in 0(log n) time on a CRCW PRAM using 0(n ** (2k+6) )
processors and a parse-tree in 0((log n) ** 2) time on a CREW PRAM
using the same number of processors. The technique we use involves a
recursive decomposition on feasible centroids of a graph. Our results
improve on a recent result of Bodlaender for constructing a tree decomposi-
tion in 0(log n) time using 0(n ** (3k+4)) processors on a CRCW PRAM.
This reflects joint work with Professor S.T. Hedetniemi.
COLLOQUIUM - Tuesday, November 8, 11 a.m. in SF1105
T.H. Merrett
School of Computer Science
McGill University
"Aldat - Towards a Relational Programming Language"
Abstract. The goal of the Aldat Project at McGill University is to produce
a high level structured programming language using the database relation as
primary data type. Operators have been devised which are useful for a wide
variety of applications, from commercial and administrative data processing
through representing, searching and managing pictures and text to expert
systems and their knowledge bases.
The talk will give a brief overview of the fundamentals of Aldat, and
then go on to describe our present work in identifying and generalizing
concepts common to the relational model of data and to structured program-
ming languages. Language notions such as loops, recursive data structures,
scopes, types, metadata and functions all acquire new dimensions when
approached from the perspective of relational databases.
THEORY SEMINAR - Thursday, November 10, 3 p.m. in GB 221
Neil Immerman
Yale University
"Descriptive and Computational Complexity"
Abstract. Computational complexity began with the natural physical notions
of time and space. Given a property, S, an important issue is the complex-
ity of checking whether or not an input satisfies S. For a long time, com-
plexity referred to the time or space used in the computation. A mathema-
tician might ask, "What is the complexity of expressing the property S" It
should not be surprising that these two questions -- that of checking and
that of expressing -- are related. It is startling how closely tied they
are when the second question refers to expressing the property in first-
order logic. Many complexity classes originally defined in terms of time
or space resources have precise definitions as classes in first-order
logic.
In 1974 Fagin gave a characterization of nondeterministic polynomial
time as the set of properties expressible in second-order existential
logic. We will begin with this result and then survey some more recent
work relating first-order expressibility to computational complexity. Some
of the results arising from this approach include characterizing polynomial
time as the set of properties expressible in first-order logic plus a least
fixed point operator, and showing that the set of first-order inductive
definitions for finite structures is closed under complementation. We will
end with an unexpected result that was derived using this approach: For all
s(n) greater than or equal to log n, nondeterministic space s(n) is closed
under complementation.
--
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