University of Leicester

informatics

The Complexity of Problems in Infinite Group Theory

Source of Funding: Engineering and Physical Sciences Research Council (EPSRC)
Amount: 116,247
Duration: April 1997 - March 2000
Principal Investigator: Prof. Rick Thomas
Other Investigators: Prof. Iain Stewart
Research Assistant: Dr. Volodya Shavrukov

Our intention is to systematically investigate the complexity of word and related problems in different classes of infinite groups where by complexity we mean both computational complexity and complexity as a formal language. In more detail, we intend to: examine proper subclasses of the class of context-free languages with respect to the (reduced) word problem; examine the algebraic structure of groups whose word problem is a proper subclass of the class of context-sensitive languages; and examine potential classes of groups for which some natural problems might be P or NP complete. We also intend to investigate the notion of an automatic group when the associated automata are replaced by other models of computation. We envisage that our research programme will use techniques and methods from group theory, formal language theory, complexity theory and finite model theory.

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