Groups, Graphs, Languages, and Rewriting
Lead Research Organisation:
Newcastle University
Department Name: Sch of Maths, Statistics and Physics
Abstract
Geometric group theory is the study of the algebraic properties of groups and how they relate to their geometric properties using technology from theoretical computer science, low dimensional topology, hyperbolic geometry and algebra. Properties of interest include those that don't depend on the presentation, including the word problem, the conjugacy problem, the isomorphism problem, and the property of being automatic. The project will investigate decision problems in groups using a combination of methods from rewriting of strings, cycles, trees, terms, (hyper)graphs, simplicial complexes and the theory of formal languages and automata.
We relate to previous work of the doctoral student in theoretical computer science on the subject of algebraic graph transformation. We connect this to recent work of Delgado, Ventura, Beeker, Margolis, and Weil that builds on Stallings' theory of folding which has application to problems relating to subgroups, automorphisms of free groups; the more recent work extends this to a larger class of groups, and we will take it much further.
Our key objectives are to:
1. To investigate the relationship between various classes of formal languages in relation to the word problem in groups: context-free, multiple context-free, Church-Rosser, indexed, context-sensitive, growing context-sensitive, tree-adjoining languages.
2. To develop methods to construct subgroup automata and develop algorithms relating to subgroups, using techniques from rewriting theory and coset automata.
3. Cyclic rewriting has applications to the conjugacy problem in group theory. It was a recent result of Zantema, Konig, Bruggink that termination of cyclic rewriting systems is undecidable in general, however it is unknown if confluence is undecidable in general, even given a finite, terminating system as input (the equivalent property for strings is decidable via critical pair analysis). This is to be investigated.
4. To investigate confluence up to garbage in string rewriting building on the student's previous results for graph rewriting. The student conjectures that local confluence up to garbage of terminating string rewriting systems is decidable on a language class with decidable substring closure, but confluence is not decidable in general, even on regular languages due to a result of Caron. Applications include establishing efficient language recognition, such as the word problem for groups.
Development of new technologies in rewriting theory, formal languages, and (coset) automata are novel, allowing new applications in (geometric) group theory to obtain new results and algorithms for solving group theoretic problems.
We relate to previous work of the doctoral student in theoretical computer science on the subject of algebraic graph transformation. We connect this to recent work of Delgado, Ventura, Beeker, Margolis, and Weil that builds on Stallings' theory of folding which has application to problems relating to subgroups, automorphisms of free groups; the more recent work extends this to a larger class of groups, and we will take it much further.
Our key objectives are to:
1. To investigate the relationship between various classes of formal languages in relation to the word problem in groups: context-free, multiple context-free, Church-Rosser, indexed, context-sensitive, growing context-sensitive, tree-adjoining languages.
2. To develop methods to construct subgroup automata and develop algorithms relating to subgroups, using techniques from rewriting theory and coset automata.
3. Cyclic rewriting has applications to the conjugacy problem in group theory. It was a recent result of Zantema, Konig, Bruggink that termination of cyclic rewriting systems is undecidable in general, however it is unknown if confluence is undecidable in general, even given a finite, terminating system as input (the equivalent property for strings is decidable via critical pair analysis). This is to be investigated.
4. To investigate confluence up to garbage in string rewriting building on the student's previous results for graph rewriting. The student conjectures that local confluence up to garbage of terminating string rewriting systems is decidable on a language class with decidable substring closure, but confluence is not decidable in general, even on regular languages due to a result of Caron. Applications include establishing efficient language recognition, such as the word problem for groups.
Development of new technologies in rewriting theory, formal languages, and (coset) automata are novel, allowing new applications in (geometric) group theory to obtain new results and algorithms for solving group theoretic problems.
Organisations
People |
ORCID iD |
| Sarah Rees (Primary Supervisor) | |
| Graham Campbell (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/R51309X/1 | 01/10/2018 | 30/09/2023 | |||
| 2281162 | Studentship | EP/R51309X/1 | 01/10/2019 | 22/08/2023 | Graham Campbell |