Descriptive Complexity Theory and Programming Language Design
This node contains slides of a 1995 talk. Much of the content of the slides
is also given in my course notes on inference rules.
However these slides contain more examples and some additional results.
In particular the characterizations of coNP, PSPACE, and EXPTIME appear only
in these slides. These characterizations are unusual in that they associate
well known features of logic programming with complexity classes. First we
get a characterization of P by adding the restriction that every term in the
head of a rules must appear in the body (this is not a standard feature).
Then we get a characteriazation of coNP by intrucing disjunction (a well known feature).
We get a characterization of PSPACE by adding negation by failure (another well known
feature) and a characterization of EXPTIME by adding second order constructs (a less
well known feature).
postscript