diana@csri.toronto.edu (Diana Li) (06/10/89)
ACTIVITIES FOR THE PERIOD JUNE 19 - 30, 1989
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Gailbraith Building, 35 St. George Street)
-------------------------------------------------------------
SYSTEMS SEMINAR
SF 4103, at 11:00 a.m., Friday 2 June 1989
Jan Chomicki
University of Maryland
"Every other day": infinite query answers in logic programming
We present here the case for a new approach to database applications of
logic programming. Better computational properties of logic programs can
be achieved if the occurrences of function symbols in rules are restricted.
We define the class of FUNCTIONAL logic programs where function symbols can
only appear in one distinguished position in every predicate.
Additionally, the arity and type of function symbols are restricted. This
class is known to be decidable. Functional logic programs are capable of
representing infinite phenomena like the flow of time and may be used for
the construction of intelligent office tools (e.g. an event scheduler).
We study the problem of processing queries to functional programs. In
particular, query answers may be infinite. We present a method to finitely
represent such answers as relational specifications consisting of a finite
set of tuples and a finitely specified congruence relation. We also discuss
the applications, possible extensions and limitations of our approach, and
relate it to other work on intensional query answers.
-------------------------------------------------------------
THEORY SEMINAR
GB 244, at 3:00 p.m., Thursday 22 June 1989
L. Lovasz
Princeton University & Eotvos University, Budapest
"How to Find Tractable Cases of Hard Combinatorial Problems?"
A typical NP-hard combinatorial problem has many special cases that are
polynomial time solvable. For example, the vertex packing problem has been
known to be polynomial time solvable for line-graphs (this is just the
matching problem), claw-free graphs, perfect graphs, t-perfect graphs etc.
We describe a method to find rather large subclasses of combinatorial
problems which are polynomial time solvable. Applied to the vertex packing
problem, this includes all perfect-like graphs. The method is based on a
technique of "lifting" polyhedra to higher dimensions. (This question has
received much attention lately; it is interesting to point out its
connection to communication complexity, discovered by Yannakakis.)
(_J_o_i_n_t _w_o_r_k _w_i_t_h _A. _S_c_h_r_i_j_v_e_r)
-------------------------------------------------------------
THEORY/AI SEMINAR
SF 4102, at 11:00 a.m., Friday 23 June 1989
Naoki Abe
University of Pennsylvania
"Title: to be announced"
"Topic: Valiant Style Learnability"
-------------------------------------------------------------
SYSTEMS SEMINAR
GB 244, at 2:00 p.m., Tuesday 27 June 1989
Ravi Sandhu
The Ohio state University
"Transaction Control Expressions for Data Integrity"
We describe a model and notation for specifying and enforcing
aspects of integrity policies, particularly separation of duties. The
key idea is to associate a transaction control expression with each
information object. This expression constrains the transactions which can
be applied to that object. As operations are actually executed the
expression is incrementally converted to a history which is used to
enforce separation of duties. We distinguish transient objects with a
short lifetime from long lived persistent objects. Separation of duties
is achieved by maintaining a complete history for transient objects but
only a partial history for persistent objects. This is possible because
of the system enforced rule that transactions are executed on persistent
objects only as a side effect of execution on transient objects.