Formal Languages and the Word Problem in Groups

Duncan Parkes.

We consider some interactions between the theory of groups and the theory of formal languages.

For any group G and generating set X we shall be primarily concerned with three sets of words over X: the word problem, the reduced word problem and the irreducible word problem.

We explain the relationships between these three sets of words and give necessary and sufficient conditions for a language to be the word problem (or the reduced word problem) of a group.

We prove that the groups which have context-free reduced word problem with respect to some finite monoid generating set are exactly the context-free groups, thus proving a conjecture of Haring-Smith.

We also show that, if a group G has finite irreducible word problem with respect to a monoid generating set X, then the reduced word problem of G with respect to X is simple. In addition, we show that the reduced word problem is recursive (or recursively enumerable) precisely when the word problem is recursive. The irreducible word problem corresponds to the set of words on the left hand side of a special rewriting system which is confluent on the equivalence class containing the identity.

We show that the class of groups which have monoid presentations by means of finite special lambda-confluent string-rewriting systems strictly contains the class of plain groups (the groups which are free products of a finitely generated free group and finitely many finite groups), and that any group which has an infinite cyclic central subgroup can be presented by such a string-rewriting system if and only if it is the direct product of an infinite cyclic group and a finite cyclic group.

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


AccessAble logo

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