The Complexity of Problems in Infinite Groups

Funding:

EPSRC Standard Research Grant GR/L37175/01, GPB 120,531

Duration:

October 1997 - September 2000

Summary:

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.

People:

R Thomas (Principal Investigator) and I Stewart

Share this page:

Contact Us

Admissions Enquiries:
BSc: +44 (0) 116 252 5280
MSc: +44 (0) 116 252 2265
E: BSc  seadmissions@le.ac.uk
E: MSc  pgadmissions@le.ac.uk

Departmental Enquiries:
T: +44 (0) 116 252 2129/3887
F: +44 (0) 116 252 3604
E: csadmin@mcs.le.ac.uk

Dept of Informatics
University of Leicester
Leicester, LE1 7RH
United Kingdom

Accessibility

DisabledGo logo

The University of Leicester is committed to equal access to our facilities. DisabledGo has a detailed accessibility guide for the Informatics Building.