Research

The following 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.

Jim Delgrande
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:

Nonmonotonic reasoning: This work has centred on, first, using conditional logics for nonmonotonic reasoning, and second investigating the foundations of default logic.

Belief Change: 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.

 

Arvind Gupta
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 constructive content.

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 machines.

 

David Mitchell
  • 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 CSP,
  • 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.

 

Oliver Schulte
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) theory.

 

Eugenia Ternovska
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 - planning.

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.