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...
Batty, Michael, Casaccino, Andrea, Duncan, Andrew J., Rees, Sarah, Severini, Simone
We adapt the Deutsch-Josza algorithm to the context of formal language theory. Specifically, we use the algorithm to distinguish between trivial and nontrivial words in groups given by finite...
Hairdressing in Groups: A Survey of Combings and Formal Languages (2007)
A group is combable if it can be represented by a language of words satisfying a fellow traveller property; an automatic group has a synchronous combing which is a regular language. This article...
Hairdressing in Groups: A Survey of Combings and Formal Languages (2007)
A group is combable if it can be represented by a language of words satisfying a fellow traveller property; an automatic group has a synchronous combing which is a regular language. This article...
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...
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...
Groups with a context-free co-word problem (2005)
Holt, D.F., Rees, Sarah, Röver, Claas E., Thomas, Richard M.
Cosets and Double Cosets (2005)
Isabel M. Araújo, Robert Arthur, Hans Ulrich Besche, Thomas Bischops, Oliver Bonten, Thomas Breuer, ...
We would like to thank the many people who have made contributions of various kinds to the development of GAP since 1986, in particular:
Quantum algorithms in group theory (2003)
Batty, Michael, Braunstein, Samuel L., Duncan, Andrew J., Rees, Sarah
We present a survey of quantum algorithms, primarily for an intended audience of pure mathematicians. We place an emphasis on algorithms involving group theory.
Congruences of magmas, semigroups and monoids (2002)
Isabel M. Araújo, Robert Arthur, Hans Ulrich Besche, Thomas Bischops, Oliver Bonten, Thomas Breuer, ...
We would like to thank the many people who have made contributions of various kinds to the development of GAP since 1986, in particular:
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...
An Algorithmic Approach to Fundamental Groups and Covers of Combinatorial Cell Complexes (2000)
Sarah Rees, Leonard H. Soicher
. We first develop a construction, originally due to Reidemeister, of the fundamental group and covers of a combinatorial cell complex. Then, we describe a practical algorithmic approach to the...
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...
Hairdressing in groups: a survey of combings and formal languages (1998)
A group is combable if it can be represented by a language of words satisfying a fellow traveller property; an automatic group has a synchronous combing which is a regular language. This article...
Hairdressing in Groups: A Survey of Combings and Formal Languages (1998)
A group is combable if it can be represented by a language of words satisfying a fellow traveller property; an automatic group has a synchronous combing which is a regular language. This article...
A language theoretic analysis of combings (1997)
A group is combable if it can be represented by a language of words satisfying a fellow traveller property; an automatic group has a synchronous combing which is a regular language. This paper gives...
Automatic groups associated with word orders other than shortlex (1997)
The existing algorithm to compute and verify the automata associated with an automatic group deals only with the subclass of shortlex automatic groups. This paper describes the extension of the...
Hairdressing in Groups: A Survey of Combings and Formal Languages (1997)
A group is combable if it can be represented by a language of words satisfying a fellow traveller property; an automatic group has a synchronous combing which is a regular language. This article...
A Language Theoretic Analysis of Combings (1997)
A group is combable if it can be represented by a language of words satisfying a fellow traveller property; an automatic group has a synchronous combing which is a regular language. This paper gives...
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...
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...
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...
Testing Modules for Irreducibility (1994)
A practical method is described for deciding whether or not a finitedimensional module for a group over a finite field is reducible or not. In the reducible case, an explicit submodule is found. The...
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...
Automatic Groups Associated With Word Orders Other Than Shortlex
The existing algorithm to compute and verify the automata associated with an automatic group deals only with the subclass of shortlex automatic groups. This paper describes the extension of the...
A Language Theoretic Analysis of Combings
. A group is combable if it can be represented by a language of words satisfying a fellow traveller property; an automatic group has a synchronous combing which is a regular language. This paper...