EPSRC logo

Details of Grant 

EPSRC Reference: GR/L37175/01
Title: THE COMPLEXITY OF PROBLEMS IN INFINITE GROUPS
Principal Investigator: Thomas, Professor RM
Other Investigators:
Stewart, Professor IA
Researcher Co-Investigators:
Project Partners:
Department: Mathematics
Organisation: University of Leicester
Scheme: Standard Research (Pre-FEC)
Starts: 01 October 1997 Ends: 30 September 2000 Value (£): 120,531
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
Related Grants:
Panel History:  
Summary on Grant Application Form
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 sub-classes 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 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. Such a thorough and concerted consideration of computation in classes of infinite groups has not before been undertaken. We envisage that our research programme will use techniques and methods from formal language theory, complexity theory and finite model theory.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.le.ac.uk