University of Leicester

informatics

Descriptive Complexity Theory

Source of Funding: Science and Engineering Research Council (SERC)
Amount: 99,280
Duration: October 1992 - September 1995
Principal Investigator: Prof. Iain Stewart
Research Assistants: Dr. Anuj Dawar (University of Wales Swansea), Dr. Henrik Imhof

The general aims of the research were to apply techniques of logic in complexity theory in order to obtain new complexity theoretic results and to characterize well-known complexity classes in a machine-independent manner. Research achievements included results on: the role of monotonicity in descriptive complexity theory; definability in bounded-variable infinitary logic; the logical analogues of questions in complexity theory; generalized Ehrenfeucht-Fraisse games; definability in monadic second-order logic; program schemes, complexity theory and logic; and completeness for complexity classes via logical reductions.

University of Leicester 15th December 2000. Last modified: 8th January 2004, 14:32:44.
Informatics Web Maintainer. This document has been approved by the Head of Department.