is an enumeration of the areas covered by researchers in the CL
group. It serves as a general overview of current work being pursued
in the lab.
My research centres on formal aspects of Knowledge Representation and
Reasoning in Artificial Intelligence.
The overall objective of this work is the development of logical formalisms
for representing and reasoning about commonsense knowledge, as well as
the hopefully-efficient implementation of such formalisms.
Specific areas include the following:
This work has centred on, first, using conditional logics for nonmonotonic
reasoning, and second investigating the foundations of default logic.
More recently I have also been working in the area of belief change.
This includes the development of formal models for belief change, in
particular an interpretation of belief revision in which the formula
for revision carries a "Gricean" interpretation in that the formula
expresses all that is known concerning a particular subject matter.
On the other hand, I have been developing a specific computational model
for belief change which would allow the specification of general,
concurrent revision, contraction, and merging operations in the presence
of integrity constraints.
Reasoning with Preferences:
This work began with the addition of preferences in approaches including
default logic and answer set programming.
More recently I have been working on an approach to adding preferences
to approaches to reasoning about action and planning.
||Combinatorics: A large number of combinatorial
theorems claim the existance of a structure yet the proof
does not explicitly exhibit this structure. One example is
the work of Robertson and Seymour on graph minors which establishes
the existence of polynomial algorithms for a large number
of problems yet there seems to be no direct method of obtaining
these algorithms from the proof of existence. I am looking
at a number of aspects of the graph minors work to gauge its
Optimization: In operations research, scheduling problems
arise from both theoretical and practical considerations.
Past work has concentrated on finding exact solutions to
such problems. I am interested in applying the theory of
randomized algorithms to deliver very fast solutions which
exhibit good performance ratios.
Complexity Theory: One of the most fundamental questions
in computer science deals with the resources required to
solve a problem. The goal is to obtain tight upper and lower
bounds on these resources. However, because algorithms can
work in novel ways, computing good lower bounds had turned
out to be difficult for most problems. More recent work
has focused on the study of parallel complexity theory.
From a theoretical point of view the trade-off between the
number of processors and execution time seems to depend
on the problem being solved. For some problems, parallel
computation does not seem to yield algorithms significantly
faster than sequential computation. I am interested in trying
to determine which problems have fast parallel algorithms
with respect to a number of different models of parallel
- Propositional satisfiability and finite domain constraint
satisfaction (and variants and generalizations),
- results on the complexity of these problems,
- aspects of design of practical algorithm for SAT and
- application to formal verification and related tasks.
I'm especially interested in the applications of results
in propositional proof complexity to the design and analysis
of search algorithms for SAT and CSP, and in particular
for attacking challenging families of application instances.
||Most of my work is on machine learning. On
the theoretical side, I research computational learning theory,
the part of theoretical computer science that deals with the
design of optimal learning algorithms. On the applications
side, I'm currently implementing an algorithm for inferring
conservation principles in elementary particle physics from
reaction data, an application of computational learning theory
to automated scientific discovery. (Funding provided by the
Canadian Natural Sciences and Engineering Research Council.)
Some of my past work has been in decision theory and von
Neumann-Morgernstern game theory. Another research interest
of mine is to represent decision-theoretic models and concepts
in a logical formalism that is computationally tractable.
The aim is to apply computational logic to decision-theoretic
planning and multi-agent interactions.
I have also worked on belief revision and computation (recursion)
||I am interested in the general area of logic
and computation, with an emphasis on efficient reasoning.
In particular, I am interested in efficient reasoning about
dynamic systems. Such reasoning are necessary, e.g., for
the verification of reactive programs and for solving one
of the most challenging problems in Artificial Intelligence
Currently, I am working on the developement of a Logic
for Non-Monotone Inductive Definitions. This logic is an
attractive tool for efficient reasoning.
Another project is formal verification of reactive programs.