The Use of Normal Forms in Solving Word Problems

Funding:

EPSRC Standard Research Grant GR/M86347/01, GPB 46,717

Duration:

October 2000 - February 2004

Summary:

We propose to carry out theoretical and practical research in the computational aspects of finitely presented groups. (particularly combable groups, automatic groups, and word-hyerbolic groups), and in the associated formal language theory. This work involves the development, implementation and, where possible, the complexity analysis of mathamatical algorithms. Some specific examples are mentioned in the objectives section. The software that we write will be available as standalone code, but will also be implemented in and made available form the GAP, magma and Magnus computation algebra systems. The theoretical side of the proposal involves studying combings of groups. We shall by analysing the complexity and formal language class of known combings, such as those of Gromov mentioned above. At the same time, we shall be trying to find new combings for more general classes of groups, such as non-nilpotent soluble groups. In addition we shall be studying the formal language class of the word problem of further classes of groups, which will involve considering language classes higher up the Chomsky hierarchy (such as context sensitive languages) than have been studied in this context to date.

People:

R Thomas (Principal Investigator) and I Stewart

Other Information:

Joint project with GR/M86194/01 (S. E. Rees, University of Newcastle, GBP 146,994) and GR/M86972/01 (D. F. Holt, University of Warwick, GBP 20,670)

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.