Groups and semigroups with a one-counter word problem (2008)
Holt, Derek F., Owens, Matthew D.
We prove that a finitely generated semigroup whose word problem is a one-counter language has a linear growth function. This provides us with a very strong restriction on the structure of such a...
Derek F. Holt, Sarah Rees, Claas E. Röver, Richard M. Thomas
We study the class of co-context-free groups. We define a co-context-free group to be one whose co-word problem (the complement of its word problem) is context-free. This class is larger than the...
GROUPS WHOSE GEODESICS ARE LOCALLY TESTABLE (2008)
Susan Hermiller, Derek F. Holt, Sarah Rees
Abstract. A regular set of words is (k-)locally testable if membership of a word in the set is determined by the nature of its subwords of some bounded length k. In this article we study groups for...
A characterisation of virtually free groups (2008)
Robert H. Gilman, Susan Hermiller, Derek F. Holt, Sarah Rees
Abstract. We prove that a finitely generated group G is virtually free if and only if there exists a generating set for G and k> 0 such that all k-locally geodesic words with respect to that...
GROUPS WHOSE GEODESICS ARE LOCALLY TESTABLE (2008)
Susan Hermiller, Derek F. Holt, Sarah Rees
Abstract. A regular set of words is (k-)locally testable if membership of a word in the set is determined by the nature of its subwords of some bounded length k. In this article we study groups in...
Groups that do and do not have context-sensitive word problem (2008)
Holt, Derek F., Rees, Sarah, Shapiro, Michael
We prove that a group has word problem that is a growing context-sensitive language precisely if its word problem can be solved using a non-deterministic Cannon's algorithm (the deterministic...
Computing a chief series and the soluble radical of a matrix group over a finite field (2008)
Derek F. Holt, Mark J. Stather
We describe an algorithm for computing a chief series, the soluble radical, and two other characteristic subgroups of a matrix group over a finite field, which is intended for matrix groups that are...
Computing With Abelian Sections of Finitely Presented Groups. (2007)
Sarah Rees, Sarah Rees, Derek F. Holt, Derek F. Holt, Derek F. Holt, Coventry Cv Al
Let G be a finitely presented group. This paper describes the theory and practice of a method for obtaining information about the finite and abelian-by-finite quotients of G, which often allows...
An Alternative Proof That the Fibonacci Group F(2, 9) Is Infinite (2007)
This note contains a report of a proof by computer that the Fibonacci group F(2, 9) is automatic...
Groups with context-free co-word problem (2005)
Holt, Derek F., Rees, Sarah, Röver, Claas E., Thomas, Richard M.
The class of co-context-free groups is studied. A co-context-free group is defined as one whose coword problem (the complement of its word problem) is context-free. This class is larger than the...
On real-time word problems (2003)
Holt, Derek F., Röver, Claas E.
It is proved that the word problem of the direct product of two free groups of rank 2 can be recognised by a 2-tape real-time but not by a 1-tape real-time Turing machine. It is also proved that the...
Solving the word problem in real time (2001)
The paper is devoted to the study of groups whose word problem can be solved by a Turing machine which operates in real time. A recent result of the first author for word hyperbolic groups is...
Combing nilpotent and polycyclic groups (1999)
Gilman, Robert H., Holt, Derek F., Rees, Sarah
A combing is a set of normal forms for a finitely generated group. This article investigates the language-theoretic and geometric properties of combings for nilpotent and polycyclic groups. It is...
Solving the Word Problem in Real Time (1999)
this paper is to study groups with real-time word problem, that is for which the word problem can be solved with a deterministic, multitape Turing machine which reads its input at constant speed and...
Some Challenging Group Presentations (1999)
George Havas, Derek F. Holt, P. E. Kenne, Sarah Rees
We study some challenging presentations which arise as groups of deficiency zero. In four cases we settle finiteness: we show that two presentations are for finite groups while two are for infinite...
Computation in word-hyperbolic groups (1998)
Epstein, David B. A., Holt, Derek F.
We describe a procedure which verifies that a group given by generators and relators is word-hyperbolic. This procedure always works with a group which is word-hyperbolic, provided there is...
Automatic groups, subgroups and cosets (1998)
The history, definition and principal properties of automatic groups and their generalisations to subgroups and cosets are reviewed briefly, mainly from a computational perspective. A result about...
Rewriting Techniques in Finitely Presented Groups and Monoids (1997)
This document contains an amplified version of the five talks given by the author at the 22nd Holiday Mathematics Symposium at the New Mexico State University, January 3-7 1997, on the topic...
Free quotients of finitely presented groups (1996)
We describe a computational, heuristic approach to the problem of deciding whether or not a given finitely presented group has a free quotient of rank two or more. Our strategy is to construct a...
The Warwick automatic groups software (1996)
Abstract. This paper provides a description of the algorithms employed by the Warwick Automata package for calculating the finite state automata associated with a short-lex automatic group. The aim...
An alternative proof that the Fibonacci group F(2,9) is infinite (1995)
This note contains a report of a proof by computer that the Fibonacci group F(2,9) is automatic. The automatic structure can be used to solve the word problem in the group. Furthermore, it can be...
The Warwick Automatic Groups Software (1995)
This paper provides a description of the algorithms employed by the Warwick AUTOMATA package for calculating the finite state automata associated with a short-lex automatic group. The aim is to...
An alternative proof that the Fibonacci group {$F(2,9)$} is infinite (1995)
This note contains a report of a proof by computer that the Fibonacci group $F(2,9)$ is automatic. The automatic structure can be used to solve the word problem in the group. Furthermore, it can be...
Star-free geodesic languages for groups (1995)
Susan Hermiller, Derek F. Holt, Sarah Rees
Abstract. In this article we show that every group with a finite presentation satisfying one or both of the small cancellation conditions C ′ (1/6) and C ′ (1/4) − T(4) has the property that...
An Alternative Proof That the Fibonacci Group F(2, 9) Is Infinite (1995)
This note contains a report of a proof by computer that the Fibonacci group F(2; 9) is automatic. The automatic structure can be used to solve the word problem in the group. Furthermore, it can be...
Star-free geodesic languages for groups (1995)
Susan Hermiller, Derek F. Holt, Sarah Rees
Abstract. In this article we show that every group with a finite presentation satisfying one or both of the small cancellation conditions C ′ (1/6) and C ′ (1/4) − T(4) has the property that...
Recognizing badly presented Z-modules (1994)
Havas, George, Holt, Derek F., Rees, Sarah
Finitely generated Z-modules have canonical decompositions. When such modules are given in a finitely presented form there is a classical algorithm for computing a canonical decomposition. This is...
We report on our implementation of an algorithm due to Neumann and Praeger for deciding whether or not a matrix group over a finite field contains the special linear group. This is a Monte Carlo...
Some topics in the theory of finite permutation groups / (1973)
Work carried out in the Mathematical Institute.