Murray Elder

Search for another author

Author Description

Ask a Question About This Mathematician

All published works (118)

Finite Groups with Geodetic Cayley Graphs

2025-05-07

Murray Elder , Adam Piggott , Florian Stober +2 more

On the complexity of epimorphism testing with virtually abelian targets

2025-01-09

Murray Elder , Jerry Shen , A. Weiss

Friedl and L\"oh (2021, Confl. Math.) prove that testing whether or not there is an epimorphism from a finitely presented group to a virtually cyclic group, or to the direct … Friedl and L\"oh (2021, Confl. Math.) prove that testing whether or not there is an epimorphism from a finitely presented group to a virtually cyclic group, or to the direct product of an abelian and a finite group, is decidable. Here we prove that these problems are $\mathsf{NP}$-complete. We also show that testing epimorphism is $\mathsf{NP}$-complete when the target is a restricted type of semi-direct product of a finitely generated free abelian group and a finite group, thus extending the class of virtually abelian target groups for which decidability of epimorphism is known. Lastly, we consider epimorphism onto a fixed finite group. We show the problem is $\mathsf{NP}$-complete when the target is a dihedral groups of order that is not a power of 2, complementing the work on Kuperberg and Samperton (2018, Geom. Topol.) who showed the same result when the target is non-abelian finite simple.

Chat View PDF

Finite groups with geodetic Cayley graphs

2024-05-31

Murray Elder , Adam Piggott , Florian Stober +2 more

A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the … A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the only geodetic Cayley graphs which occur are odd cycles and complete graphs. In this article we present a series of theoretical results which contribute to a computer search verifying this conjecture for all groups of size up to 1024. The conjecture is also verified theoretically for several infinite families of groups including dihedral and some families of nilpotent groups. Two key results which enable the computer search to reach as far as it does are: if the center of a group has even order, then the conjecture holds (this eliminates all 2-groups from our computer search); if a Cayley graph is geodetic then there are bounds relating the size of the group, generating set and center (which cuts down the number of generating sets which must be searched significantly).

Chat View PDF

On <i>k</i>-geodetic graphs and groups

2023-06-23

Murray Elder , Adam Piggott , Kane Douglas Townsend

We call a graph k-geodetic, for some [Formula: see text], if it is connected and between any two vertices there are at most k geodesics. It is shown that any … We call a graph k-geodetic, for some [Formula: see text], if it is connected and between any two vertices there are at most k geodesics. It is shown that any hyperbolic group with a k-geodetic Cayley graph is virtually-free. Furthermore, in such a group the centralizer of any infinite order element is an infinite cyclic group. These results were known previously only in the case that [Formula: see text]. A key tool used to develop the theorem is a new graph theoretic result concerning “ladder-like structures” in a k-geodetic graph.

Chat View PDF

On groups presented by inverse-closed finite confluent length-reducing rewriting systems

2023-03-30

Murray Elder , Adam Piggott

Graphs and groups with unique geodesics

2023-01-01

Murray Elder , G. E. Gardam , Adam Piggott +2 more

A connected graph is called \emph{geodetic} if there is a unique geodesic between each pair of vertices. In this paper we prove that if a finitely generated group admits a … A connected graph is called \emph{geodetic} if there is a unique geodesic between each pair of vertices. In this paper we prove that if a finitely generated group admits a Cayley graph which is geodetic, then the group must be virtually free. Before now, it was open whether finitely generated and geodetic implied hyperbolic. In fact we prove something more general: if a quasi-transitive locally finite connected undirected graph is geodetic then it is quasi-isometric to a tree. Our main tool is to define a \emph{boundary} of a graph and understand how the local behaviour influences it when the graph is geodetic. Our results unify, and represent significant progress on, research initiated by Ore, Shapiro, and Madlener and Otto.

Chat View PDF

On the geometry of Cayley automatic groups

2022-03-15

Dmitry Berdinsky , Murray Elder , Jennifer Taback

In contrast to being automatic, being Cayley automatic a priori has no geometric consequences. Specifically, Cayley graphs of automatic groups enjoy a fellow traveler property. Here, we study a distance … In contrast to being automatic, being Cayley automatic a priori has no geometric consequences. Specifically, Cayley graphs of automatic groups enjoy a fellow traveler property. Here, we study a distance function introduced by the first author and Trakuldit which aims to measure how far a Cayley automatic group is from being automatic, in terms of how badly the Cayley graph fails the fellow traveler property. The first author and Trakuldit showed that if it fails by at most a constant amount, then the group is in fact automatic. In this paper, we show that for a large class of non-automatic Cayley automatic groups this function is bounded below by a linear function in a precise sense defined herein. In fact, for all Cayley automatic groups which have super-quadratic Dehn function, or which are not finitely presented, we can construct a non-decreasing function which (1) depends only on the group and (2) bounds from below the distance function for any Cayley automatic structure on the group.

Chat View PDF

A virtually 2-step nilpotent group with polynomial geodesic growth

2022-01-01

Alex Bishop , Murray Elder

A direct consequence of Gromov's theorem is that if a group has polynomial geodesic growth with respect to some finite generating set then it is virtually nilpotent. However, until now … A direct consequence of Gromov's theorem is that if a group has polynomial geodesic growth with respect to some finite generating set then it is virtually nilpotent. However, until now the only examples known were virtually abelian. In this note we furnish an example of a virtually 2-step nilpotent group having polynomial geodesic growth with respect to a certain finite generating set.

Chat View PDF

On $k$-geodetic graphs and groups

2022-01-01

Murray Elder , Adam Piggott , Kane Douglas Townsend

We call a graph $k$-geodetic, for some $k\geq 1$, if it is connected and between any two vertices there are at most $k$ geodesics. It is shown that any hyperbolic … We call a graph $k$-geodetic, for some $k\geq 1$, if it is connected and between any two vertices there are at most $k$ geodesics. It is shown that any hyperbolic group with a $k$-geodetic Cayley graph is virtually-free. Furthermore, in such a group the centraliser of any infinite order element is an infinite cyclic group. These results were known previously only in the case that $k=1$. A key tool used to develop the theorem is a new graph theoretic result concerning ``ladder-like structures'' in a $k$-geodetic graph.

Chat View PDF

Rewriting systems, plain groups, and geodetic graphs

2021-12-28

Murray Elder , Adam Piggott

Chat View PDF

The isomorphism problem for plain groups is in $\Sigma_3^{\mathsf{P}}$

2021-10-03

Heiko Dietrich , Murray Elder , Adam Piggott +2 more

Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. S\'enizergues and Wei\ss (ICALP2018) proved that the isomorphism problem for virtually … Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. S\'enizergues and Wei\ss (ICALP2018) proved that the isomorphism problem for virtually free groups is decidable in $\mathsf{PSPACE}$ when the input is given in terms of so-called virtually free presentations. Here we consider the isomorphism problem for the class of \emph{plain groups}, that is, groups that are isomorphic to a free product of finitely many finite groups and finitely many copies of the infinite cyclic group. Every plain group is naturally and efficiently presented via an inverse-closed finite convergent length-reducing rewriting system. We prove that the isomorphism problem for plain groups given in this form lies in the polynomial time hierarchy, more precisely, in $\Sigma_3^{\mathsf{P}}$. This result is achieved by combining new geometric and algebraic characterisations of groups presented by inverse-closed finite convergent length-reducing rewriting systems developed in recent work of Elder and Piggott (2021) with classical finite group isomorphism results of Babai and Szemer\'edi (1984).

Chat View PDF

The complexity of solution sets to equations in hyperbolic groups

2021-10-01

Laura Ciobanu , Murray Elder

Chat View PDF

Detecting plainness in PSPACE.

2021-06-07

Murray Elder , Adam Piggott

We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: non-degenerate triangles in their Cayley graph have uniformly bounded size. We … We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: non-degenerate triangles in their Cayley graph have uniformly bounded size. We then define a simple relation on the set of non-trivial finite-order elements of the group, and prove that the group is plain if and only if this relation is transitive on a bounded set. This in turn gives rise to a deterministic quadratic space algorithm (in the size of the longest right-hand side of a rule in the rewriting system) to decide whether or not the group is plain.

On groups presented by inverse-closed finite convergent length-reducing rewriting systems

2021-06-07

Murray Elder , Adam Piggott

We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: their Cayley graphs are geodetic and side-lengths of non-degenerate triangles are … We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: their Cayley graphs are geodetic and side-lengths of non-degenerate triangles are uniformly bounded. This leads to a new algebraic result: the group is plain (isomorphic to the free product of finitely many finite groups and copies of $\mathbb Z$) if and only if a certain relation on the set of non-trivial finite-order elements of the group is transitive on a bounded set. We use this to prove that deciding if a group presented by an inverse-closed finite convergent length-reducing rewriting system is not plain is in $\mathsf{NP}$. A yes answer would disprove a longstanding conjecture of Madlener and Otto from 1987. We also prove that the isomorphism problem for plain groups presented by inverse-closed finite convergent length-reducing rewriting systems is in $\mathsf{PSPACE}$.

Cayley polynomial–time computable groups

2021-05-26

Dmitry Berdinsky , Murray Elder , Prohrak Kruengthomya

Chat View PDF

BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS

2021-04-13

Dmitry Berdinsky , Murray Elder , Jennifer Taback

Abstract We extend work of Berdinsky and Khoussainov [‘Cayley automatic representations of wreath products’, International Journal of Foundations of Computer Science 27 (2) (2016), 147–159] to show that being Cayley … Abstract We extend work of Berdinsky and Khoussainov [‘Cayley automatic representations of wreath products’, International Journal of Foundations of Computer Science 27 (2) (2016), 147–159] to show that being Cayley automatic is closed under taking the restricted wreath product with a virtually infinite cyclic group. This adds to the list of known examples of Cayley automatic groups.

Chat View PDF

$k$-Pop Stack Sortable Permutations and $2$-Avoidance

2021-03-26

Murray Elder , Yoong Kuan Goh

We consider permutations sortable by $k$ passes through a deterministic pop stack. We show that for any $k\in\mathbb{N}$ the set is characterised by finitely many patterns, answering a question of … We consider permutations sortable by $k$ passes through a deterministic pop stack. We show that for any $k\in\mathbb{N}$ the set is characterised by finitely many patterns, answering a question of Claesson and Guðmundsson. Moreover, these sets of patterns are algorithmically constructible. Our characterisation demands a more precise definition than in previous literature of what it means for a permutation to avoid a set of barred and unbarred patterns. We propose a new notion called $2$-avoidance.

Chat View PDF

Being Cayley automatic is closed under taking wreath product with virtually cyclic groups

2021-03-19

Dmitry Berdinsky , Murray Elder , Jennifer Taback

We extend work of the first author and Khoussainov to show that being Cayley automatic is closed under taking the restricted wreath product with a virtually infinite cyclic group. This … We extend work of the first author and Khoussainov to show that being Cayley automatic is closed under taking the restricted wreath product with a virtually infinite cyclic group. This adds to the list of known examples of Cayley automatic groups.

Chat View PDF

On groups presented by inverse-closed finite convergent length-reducing rewriting systems

2021-01-01

Murray Elder , Adam Piggott

We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: their Cayley graphs are geodetic and side-lengths of non-degenerate triangles are … We show that groups presented by inverse-closed finite convergent length-reducing rewriting systems are characterised by a striking geometric property: their Cayley graphs are geodetic and side-lengths of non-degenerate triangles are uniformly bounded. This leads to a new algebraic result: the group is plain (isomorphic to the free product of finitely many finite groups and copies of $\mathbb Z$) if and only if a certain relation on the set of non-trivial finite-order elements of the group is transitive on a bounded set. We use this to prove that deciding if a group presented by an inverse-closed finite convergent length-reducing rewriting system is not plain is in $\mathsf{NP}$. A "yes" answer would disprove a longstanding conjecture of Madlener and Otto from 1987. We also prove that the isomorphism problem for plain groups presented by inverse-closed finite convergent length-reducing rewriting systems is in $\mathsf{PSPACE}$.

Chat View PDF

Being Cayley automatic is closed under taking wreath product with virtually cyclic groups

2021-01-01

Dmitry Berdinsky , Murray Elder , Jennifer Taback

Chat View PDF

The isomorphism problem for plain groups is in $Σ_3^{\mathsf{P}}$

2021-01-01

Heiko Dietrich , Murray Elder , Adam Piggott +2 more

Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. S{\'e}nizergues and the fifth author (ICALP2018) proved that the isomorphism problem … Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. S{\'e}nizergues and the fifth author (ICALP2018) proved that the isomorphism problem for virtually free groups is decidable in $\mathsf{PSPACE}$ when the input is given in terms of so-called virtually free presentations. Here we consider the isomorphism problem for the class of \emph{plain groups}, that is, groups that are isomorphic to a free product of finitely many finite groups and finitely many copies of the infinite cyclic group. Every plain group is naturally and efficiently presented via an inverse-closed finite convergent length-reducing rewriting system. We prove that the isomorphism problem for plain groups given in this form lies in the polynomial time hierarchy, more precisely, in $\Sigma_3^{\mathsf{P}}$. This result is achieved by combining new geometric and algebraic characterisations of groups presented by inverse-closed finite convergent length-reducing rewriting systems developed in recent work of the second and third authors (2021) with classical finite group isomorphism results of Babai and Szemer\'edi (1984).

Chat View PDF

Rewriting systems, plain groups, and geodetic graphs

2020-09-07

Murray Elder , Adam Piggott

We prove that a group is presented by finite convergent length-reducing rewriting systems where each rule has left-hand side of length 3 if and only if the group is plain. … We prove that a group is presented by finite convergent length-reducing rewriting systems where each rule has left-hand side of length 3 if and only if the group is plain. Our proof goes via a new result concerning properties of embedded circuits in geodetic graphs, which may be of independent interest in graph theory.

Chat View PDF

Separating automatic from Cayley automatic groups

2020-08-05

Dmitry Berdinsky , Murray Elder , Jennifer Taback

We investigate the problem of distinguishing non-automatic Cayley automatic groups from automatic groups. It is well known that automatic groups are finitely presented with either linear or quadratic Dehn function. … We investigate the problem of distinguishing non-automatic Cayley automatic groups from automatic groups. It is well known that automatic groups are finitely presented with either linear or quadratic Dehn function. In this work we show that any Cayley automatic group with Dehn function that is not almost quadratic, or is not finitely presented, is quantitatively separated from the class of automatic groups via a distance function previously introduced by the first author and Trakuldit. For each such group we construct a concrete unbounded function, depending only on the group, so that the distance function for any Cayley automatic structure on the group is bounded below by this function.

Chat View PDF

The complexity of solution sets to equations in hyperbolic groups

2020-01-27

Laura Ciobanu , Murray Elder

We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, as shortlex geodesic words (or any regular set of quasigeodesic normal forms), … We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, as shortlex geodesic words (or any regular set of quasigeodesic normal forms), is an EDT0L language whose specification can be computed in NSPACE$(n^2\log n)$ for the torsion-free case and NSPACE$(n^4\log n)$ in the torsion case. Furthermore, in the presence of quasi-isometrically embeddable rational constraints, we show that the full set of solutions to systems of equations in a hyperbolic group remains EDT0L. Our work combines the geometric results of Rips, Sela, Dahmani and Guirardel on the decidability of the existential theory of hyperbolic groups with the work of computer scientists including Plandowski, Jez, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis.

Chat View PDF

Rewriting systems, plain groups, and geodetic graphs

2020-01-01

Murray Elder , Adam Piggott

Chat View PDF

On the geometry of Cayley automatic groups

2020-01-01

Dmitry Berdinsky , Murray Elder , Jennifer Taback

In contrast to being automatic, being Cayley automatic \emph{a priori} has no geometric consequences. Specifically, Cayley graphs of automatic groups enjoy a fellow traveler property. Here we study a distance … In contrast to being automatic, being Cayley automatic \emph{a priori} has no geometric consequences. Specifically, Cayley graphs of automatic groups enjoy a fellow traveler property. Here we study a distance function introduced by the first author and Trakuldit which aims to measure how far a Cayley automatic group is from being automatic, in terms of how badly the Cayley graph fails the fellow traveler property. The first author and Trakuldit showed that if it fails by at most a constant amount, then the group is in fact automatic. In this article we show that for a large class of non-automatic Cayley automatic groups this function is bounded below by a linear function in a precise sense defined herein. In fact, for all Cayley automatic groups which have super-quadratic Dehn function, or which are not finitely presented, we can construct a non-decreasing function which (1) depends only on the group and (2) bounds from below the distance function for any Cayley automatic structure on the group.

Chat View PDF

The complexity of solution sets to equations in hyperbolic groups

2020-01-01

Laura Ciobanu , Murray Elder

We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, as shortlex geodesic words (or any regular set of quasigeodesic normal forms), … We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, as shortlex geodesic words (or any regular set of quasigeodesic normal forms), is an EDT0L language whose specification can be computed in NSPACE$(n^2\log n)$ for the torsion-free case and NSPACE$(n^4\log n)$ in the torsion case. Furthermore, in the presence of quasi-isometrically embeddable rational constraints, we show that the full set of solutions to systems of equations in a hyperbolic group remains EDT0L. Our work combines the geometric results of Rips, Sela, Dahmani and Guirardel on the decidability of the existential theory of hyperbolic groups with the work of computer scientists including Plandowski, Je\.z, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis.

Chat View PDF

A virtually 2-step nilpotent group with polynomial geodesic growth

2020-01-01

Alex Bishop , Murray Elder

Chat View PDF

Solutions to twisted word equations and equations in virtually free groups

2019-12-09

Volker Diekert , Murray Elder

It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids … It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper, we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in PSPACE . Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in PSPACE an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or “small enough”) finite monoid, then our algorithms can be implemented in [Formula: see text], that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and Sénizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions.

Chat View PDF

On permutations sorted by $k$ passes through a deterministic pop stack

2019-11-08

Murray Elder , Yoong Kuan Goh

We consider permutations sortable by $k$ passes through a deterministic pop stack. We show that for any $k\in\mathbb N$ the set is characterised by finitely many forbidden patterns, answering a … We consider permutations sortable by $k$ passes through a deterministic pop stack. We show that for any $k\in\mathbb N$ the set is characterised by finitely many forbidden patterns, answering a question of Claesson and Guðmundsson. Our characterisation demands a more precise definition than in previous literature of what it means for a permutation to avoid a set of barred and unbarred patterns. We propose a new notion called $PB$-containment and prove some useful results about it.

Chat View PDF

$k$-pop stack sortable permutations and $2$-avoidance

2019-11-08

Murray Elder , Yoong Kuan Goh

We consider permutations sortable by $k$ passes through a deterministic pop stack. We show that for any $k\in\mathbb N$ the set is characterised by finitely many patterns, answering a question … We consider permutations sortable by $k$ passes through a deterministic pop stack. We show that for any $k\in\mathbb N$ the set is characterised by finitely many patterns, answering a question of Claesson and Gu{\dh}mundsson. Our characterisation demands a more precise definition than in previous literature of what it means for a permutation to avoid a set of barred and unbarred patterns. We propose a new notion called \emph{$2$-avoidance}.

Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE

2019-07-01

Laura Ciobanu , Murray Elder

We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, with or without torsion, as shortlex geodesic words, is an EDT0L language … We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, with or without torsion, as shortlex geodesic words, is an EDT0L language whose specification can be computed in $\mathsf{NSPACE}(n^2\log n)$ for the torsion-free case and $\mathsf{NSPACE}(n^4\log n)$ in the torsion case. Our work combines deep geometric results by Rips, Sela, Dahmani and Guirardel on decidability of existential theories of hyperbolic groups, work of computer scientists including Plandowski, Jez, Diekert and others on $\mathsf{PSPACE}$ algorithms to solve equations in free monoids and groups using compression, and an intricate language-theoretic analysis. The present work gives an essentially optimal formal language description for all solutions in all hyperbolic groups, and an explicit and surprising low space complexity to compute them.

Chat View PDF

On a theorem of Avez

2019-01-20

Murray Elder , Cameron Rogers

Abstract For each symmetric, aperiodic probability measure μ on a finitely generated group G , we define a subset <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:msub><m:mi>A</m:mi><m:mi>μ</m:mi></m:msub></m:math> {A_{\mu}} consisting of group elements g for which the … Abstract For each symmetric, aperiodic probability measure μ on a finitely generated group G , we define a subset <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:msub><m:mi>A</m:mi><m:mi>μ</m:mi></m:msub></m:math> {A_{\mu}} consisting of group elements g for which the limit of the ratio <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mrow><m:mrow><m:msup><m:mi>μ</m:mi><m:mrow><m:mi/><m:mo>∗</m:mo><m:mi>n</m:mi></m:mrow></m:msup><m:mo>⁢</m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mi>g</m:mi><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow><m:mo>/</m:mo><m:msup><m:mi>μ</m:mi><m:mrow><m:mi/><m:mo>∗</m:mo><m:mi>n</m:mi></m:mrow></m:msup></m:mrow><m:mo>⁢</m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mi>e</m:mi><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {{\mu^{\ast n}(g)}/{\mu^{\ast n}(e)}} tends to 1. We prove that <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:msub><m:mi>A</m:mi><m:mi>μ</m:mi></m:msub></m:math> {A_{\mu}} is a subgroup, is amenable, contains every finite normal subgroup, and <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi>G</m:mi><m:mo>=</m:mo><m:msub><m:mi>A</m:mi><m:mi>μ</m:mi></m:msub></m:mrow></m:math> {G=A_{\mu}} if and only if G is amenable. For non-amenable groups we show that <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:msub><m:mi>A</m:mi><m:mi>μ</m:mi></m:msub></m:math> {A_{\mu}} is not always a normal subgroup and can depend on the measure. We formulate some conjectures relating <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:msub><m:mi>A</m:mi><m:mi>μ</m:mi></m:msub></m:math> {A_{\mu}} to the amenable radical.

Chat View PDF

Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE

2019-01-01

Laura Ciobanu , Murray Elder

We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, with or without torsion, as shortlex geodesic words, is an EDT0L language … We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, with or without torsion, as shortlex geodesic words, is an EDT0L language whose specification can be computed in $\mathsf{NSPACE}(n^2\log n)$ for the torsion-free case and $\mathsf{NSPACE}(n^4\log n)$ in the torsion case. Our work combines deep geometric results by Rips, Sela, Dahmani and Guirardel on decidability of existential theories of hyperbolic groups, work of computer scientists including Plandowski, Jeż, Diekert and others on $\mathsf{PSPACE}$ algorithms to solve equations in free monoids and groups using compression, and an intricate language-theoretic analysis. The present work gives an essentially optimal formal language description for all solutions in all hyperbolic groups, and an explicit and surprising low space complexity to compute them.

Chat View PDF

Bounded Automata Groups are co-ET0L

2019-01-01

Alex Bishop , Murray Elder

Chat View PDF

$k$-pop stack sortable permutations and $2$-avoidance

2019-01-01

Murray Elder , Yoong Kuan Goh

Chat View PDF

Applications of L systems to group theory

2018-02-04

Laura Ciobanu , Murray Elder , Michal Ferov

L systems generalize context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper, … L systems generalize context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper, we show that many of the languages naturally appearing in group theory, and that were known to be indexed or context-sensitive, are in fact ET0L and in many cases EDT0L. For instance, the language of primitives and bases in the free group on two generators, the Bridson–Gilman normal forms for the fundamental groups of 3-manifolds or orbifolds, and the co-word problem of Grigorchuk’s group can be generated by L systems. To complement the result on primitives in rank 2 free groups, we show that the language of primitives, and primitive sets, in free groups of rank higher than two is context-sensitive. We also show the existence of EDT0L languages of intermediate growth.

Chat View PDF

Permutations Sorted by a Finite and an Infinite Stack in Series

2018-01-01

Murray Elder , Yoong Kuan Goh

Chat View PDF

Totally Disconnected Groups From Baumslag-Solitar Groups

2017-12-19

Murray Elder , George A. Willis

Chat View PDF

Permutations sorted by a finite and an infinite stack in series

2017-11-16

Murray Elder , Yoong Kuan Goh

We prove that the set of permutations sorted by a stack of depth $t \geq 3$ and an infinite stack in series has infinite basis, by constructing an infinite antichain. … We prove that the set of permutations sorted by a stack of depth $t \geq 3$ and an infinite stack in series has infinite basis, by constructing an infinite antichain. This answers an open question on identifying the point at which, in a sorting process with two stacks in series, the basis changes from finite to infinite.

Chat View PDF

Sub-dominant Cogrowth Behavior and the Viability of Deciding Amenability Numerically

2017-08-22

Murray Elder , Cameron Rogers

We critically analyze a recent numerical method due to the first author, Rechnitzer, and van Rensburg, which attempts to detect amenability in a finitely generated group by numerically estimating its … We critically analyze a recent numerical method due to the first author, Rechnitzer, and van Rensburg, which attempts to detect amenability in a finitely generated group by numerically estimating its asymptotic cogrowth rate. We identify two potential sources of error. We then propose a modification of the method that enables it to easily compute surprisingly accurate estimates for initial terms of the cogrowth sequence.

Chat View PDF

Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups.

2017-07-01

Volker Diekert , Murray Elder

We prove that the full solution set of a twisted word equation with regular constraints is an EDT0L language. It follows that the set of solutions to equations with rational … We prove that the full solution set of a twisted word equation with regular constraints is an EDT0L language. It follows that the set of solutions to equations with rational constraints in a context-free group (= finitely generated virtually free group) in reduced normal forms is EDT0L. We can also decide whether or not the solution set is finite, which was an open problem. Moreover, this can all be done in PSPACE. Our results generalize the work by Lohrey and Senizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to complexity and with respect to expressive power. Both papers show that satisfiability is decidable, but neither gave any concrete complexity bound. Our results concern all solutions, and give, in some sense, the optimal formal language characterization.

Applications of L systems to group theory

2017-05-08

Laura Ciobanu , Murray Elder , Michal Ferov

L systems generalise context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper … L systems generalise context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper we show that many of the languages naturally appearing in group theory, and that were known to be indexed or context-sensitive, are in fact ET0L and in many cases EDT0L. For instance, the language of primitives in the free group on two generators, the Bridson-Gilman normal forms for the fundamental groups of 3-manifolds or orbifolds, and the co-word problem of Grigorchuk's group can be generated by L systems. To complement the result on primitives in free groups, we show that the language of primitives, and primitive sets, in free groups of rank higher than two is context-sensitive. We also show the existence of EDT0L and ET0L languages of intermediate growth.

Solutions to twisted word equations and equations in virtually free groups

2017-01-12

Volker Diekert , Murray Elder

It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids … It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in $\mathsf{PSPACE}$. Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in $\mathsf{PSPACE}$ an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or small enough) finite monoid, then our algorithms can be implemented in $\mathsf{NSPACE}(n^2\log n)$, that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and Senizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions.

Chat View PDF

Solutions of twisted word equations, EDT0L languages, and context-free groups

2017-01-12

Volker Diekert , Murray Elder

It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids … It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in $\mathsf{PSPACE}$. Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in $\mathsf{PSPACE}$ an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or small enough) finite monoid, then our algorithms can be implemented in $\mathsf{NSPACE}(n^2\log n)$, that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and Senizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions.

Chat View PDF

Applications of L systems to group theory

2017-01-01

Laura Ciobanu , Murray Elder , Michal Ferov

Chat View PDF

Solutions to twisted word equations and equations in virtually free groups

2017-01-01

Volker Diekert , Murray Elder

It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids … It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in $\mathsf{PSPACE}$. Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in $\mathsf{PSPACE}$ an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or "small enough") finite monoid, then our algorithms can be implemented in $\mathsf{NSPACE}(n^2\log n)$, that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and S\'enizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions.

Chat View PDF

Permutations sorted by a finite and an infinite stack in series

2017-01-01

Murray Elder , Yoong Kuan Goh

Chat View PDF

Sub-dominant cogrowth behaviour and the viability of deciding amenability numerically

2016-08-24

Murray Elder , Cameron Rogers

We critically analyse a recent numerical method due to the first author, Rechnitzer and van Rensburg, which attempts to detect amenability or non-amenability in a finitely generated group by numerically … We critically analyse a recent numerical method due to the first author, Rechnitzer and van Rensburg, which attempts to detect amenability or non-amenability in a finitely generated group by numerically estimating its asymptotic cogrowth rate. We identify two potential sources of error. We then propose a modification of the method that enables it to easily compute surprisingly accurate estimates for initial terms of the cogrowth sequence.

Solution sets for equations over free groups are EDT0L languages

2016-05-31

Laura Ciobanu , Volker Diekert , Murray Elder

We show that, given an equation over a finitely generated free group, the set of all solutions in reduced words forms an effectively constructible EDT0L language. In particular, the set … We show that, given an equation over a finitely generated free group, the set of all solutions in reduced words forms an effectively constructible EDT0L language. In particular, the set of all solutions in reduced words is an indexed language in the sense of Aho. The language characterization we give, as well as further questions about the existence or finiteness of solutions, follow from our explicit construction of a finite directed graph which encodes all the solutions. Our result incorporates the recently invented recompression technique of Jeż, and a new way to integrate solutions of linear Diophantine equations into the process. As a byproduct of our techniques, we improve the complexity from quadratic nondeterministic space in previous works to [Formula: see text] here.

Chat View PDF

Common Coauthors

Coauthor	Papers Together
Laura Ciobanu	16
Adam Piggott	14
Jennifer Taback	13
Andrew Rechnitzer	12
Volker Diekert	10
Dmitry Berdinsky	7
Yoong Kuan Goh	7
A. Weiss	5
Cameron Rogers	5
George A. Willis	5
Sean Cleary	4
José Burillo	4
E J Janse van Rensburg	4
Arkadius Kalka	4
Geoffrey Lee	3
Gretchen Ostheimer	3
Kane Douglas Townsend	3
Thomas G. Wong	3
Nick Davis	3
Michal Ferov	3
Jon McCammond	3
Tara Brough	3
Stephan Tillmann	2
Christopher C. Banks	2
Heiko Dietrich	2
Georg Zetzsche	2
Benjamin A. Burton	2
Martin R. Bridson	2
Lawrence Reeves	2
Will Dison	2
Alexander Thumm	2
Tim Riley	2
Alex Bishop	2
Florian Stober	2
Cameron Rogers	2
Jerry Shen	1
P. Westcott	1
John Meier	1
Mike Zabrocki	1
Mark Kambites	1
Éric Fusy	1
Zoran Šunić	1
Lawrence E. Reeves	1
Davide Spriano	1
Youming Qiao	1
Prohrak Kruengthomya	1
Zoran vSunić	1
Susan Hermiller	1
Robert M. Young	1
Gillian Z. Elston	1

Commonly Cited References

Word Processing in Groups

1992-11-02

D. B. A. Epstein

From the Publisher: This study in combinatorial group theory introduces the concept of automatic groups. It contains a succinct introduction to the theory of regular languages, a discussion of related … From the Publisher: This study in combinatorial group theory introduces the concept of automatic groups. It contains a succinct introduction to the theory of regular languages, a discussion of related topics in combinatorial group theory, and the connections between automatic groups and geometry which motivated the development of this new theory. It is of interest to mathematicians and computer scientists and includes open problems that will dominate the research for years to come.

Combinatorial Group Theory

1990-01-01

Roger C. Lyndon , Paul E. Schupp

Chapter I. Free Groups and Their Subgroups 1. Introduction 2. Nielsen's Method 3. Subgroups of Free Groups 4. Automorphisms of Free Groups 5. Stabilizers in Aut(F) 6. Equations over Groups … Chapter I. Free Groups and Their Subgroups 1. Introduction 2. Nielsen's Method 3. Subgroups of Free Groups 4. Automorphisms of Free Groups 5. Stabilizers in Aut(F) 6. Equations over Groups 7. Quadratic sets of Word 8. Equations in Free Groups 9. Abstract Lenght Functions 10. Representations of Free Groups 11. Free Pruducts with Amalgamation Chapter II. Generators and Relations 1. Introduction 2. Finite Presentations 3. Fox Calculus, Relation Matrices, Connections with Cohomology 4. The Reidemeister-Schreier Method 5. Groups with a Single Defining Relator 6. Magnus' Treatment of One-Relator Groups Chapter III. Geometric Methods 1. Introduction 2. Complexes 3. Covering Maps 4. Cayley Complexes 5. Planar Caley Complexes 6. F-Groups Continued 7. Fuchsian Complexes 8. Planar Groups with Reflections 9. Singular Subcomplexes 10. Sherical Diagrams 11. Aspherical Groups 12. Coset Diagrams and Permutation Representations 13. Behr Graphs Chpter IV. Free Products and HNN Extensions 1. Free Products 2. Higman-Neumann-Neumann Extensions and Free Products with Amalgamation 3. Some Embedding Theorems 4. Some Decision Problems 5. One-Relator Groups 6. Bipolar Structures 7. The Higman Embedding Theorem 8. Algebraically Closed Groups Chapter V. Small Cancellation Theory 1. Diagrams 2. The Small Cancellation Hypotheses 3. The Basic Formulas 4. Dehn's Algorithm and Greendlinger's Lemma 5. The Conjugacy Problem 6. The Word Problem 7. The Cunjugacy Problme 8. Applications to Knot Groups 9. The Theory over Free Products 10. Small Cancellation Products 11. Small Cancellation Theory over free Products with Amalgamation and HNN Extensions Bibliography Index of Names Subject Index

Automatic structures, rational growth, and geometrically finite hyperbolic groups

1995-12-01

Walter D. Neumann , Michael Shapiro

Chat View PDF

FOREST DIAGRAMS FOR ELEMENTS OF THOMPSON'S GROUP F

2005-10-01

James Belk , Kenneth S. Brown

We introduce forest diagrams to represent elements of Thompson's group F. These diagrams relate to a certain action of F on the real line in the same way that tree … We introduce forest diagrams to represent elements of Thompson's group F. These diagrams relate to a certain action of F on the real line in the same way that tree diagrams relate to the standard action of F on the unit interval. Using forest diagrams, we give a conceptually simple length formula for elements of F with respect to the {x_0,x_1} generating set, and we discuss the construction of minimum-length words for positive elements. Finally, we use forest diagrams and the length formula to examine the structure of the Cayley graph of F.

Chat View PDF

Cogrowth and amenability of discrete groups

1982-10-01

Joel M. Cohen

From automatic structures to automatic groups

2014-05-13

Olga Kharlampovich , Bakhadyr Khoussainov , Alexei Miasnikov

In this paper we introduce the concept of a Cayley graph automatic group (CGA group or graph automatic group, for short) which generalizes the standard notion of an automatic group. … In this paper we introduce the concept of a Cayley graph automatic group (CGA group or graph automatic group, for short) which generalizes the standard notion of an automatic group. Like the usual automatic groups graph automatic ones enjoy many nice properties: these groups are invariant under the change of generators, they are closed under direct and free products, certain types of amalgamated products, and finite extensions. Furthermore, the word problem in graph automatic groups is decidable in quadratic time. However, the class of graph automatic groups is much wider then the class of automatic groups. For example, we prove that all finitely generated 2-nilpotent groups and Baumslag–Solitar groups BS(1,n) are graph automatic, as well as many other metabelian groups.

Chat View PDF

Metric Spaces of Non-Positive Curvature

1999-01-01

Martin R. Bridson , André Haefliger

Pascal's triangles in Abelian and hyperbolic groups

1997-10-01

Michael Shapiro

Abstract Given a group G and a finite generating set G , we take p G : G → Z to be the function which counts the number of geodesics … Abstract Given a group G and a finite generating set G , we take p G : G → Z to be the function which counts the number of geodesics for each group element g . This generalizes Pascal's triangle. We compute p G for word hyperbolic and describe generic behaviour in abelian groups.

Chat View PDF

Solution sets for equations over free groups are EDT0L languages

2016-05-31

Laura Ciobanu , Volker Diekert , Murray Elder

Chat View PDF

<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mi mathvariant="script">C</mml:mi></mml:math>-graph automatic groups

2014-06-04

Murray Elder , Jennifer Taback

Chat View PDF

Foliations for solving equations in groups: free, virtually free, and hyperbolic groups

2010-01-01

François Dahmani , Vincent Guirardel

We give an algorithm for solving equations and inequations with rational constraints in virtually free groups. Our algorithm is based on Rips' classification of measured band complexes. Using canonical representatives, … We give an algorithm for solving equations and inequations with rational constraints in virtually free groups. Our algorithm is based on Rips' classification of measured band complexes. Using canonical representatives, we deduce an algorithm for solving equations and inequations in all hyperbolic groups (possibly with torsion). Additionally, we can deal with quasi-isometrically embeddable rational constraints.

Chat View PDF

Combinatorial Group Theory

2001-01-01

Roger C. Lyndon , Paul E. Schupp

Chat View PDF

On rationality of the cogrowth series

1998-01-01

Dmitri Kouksov

The cogrowth series of a group <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> depends on the presentation of the group. We show that the … The cogrowth series of a group <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> depends on the presentation of the group. We show that the cogrowth series of a non-empty presentation is a rational function not equal to 1 if and only if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is finite. Except for the trivial group, this property is independent of presentation.

Chat View PDF

Computational Explorations in Thompson’s Group F

2007-09-23

José Burillo , Sean Cleary , Bert Wiest

Here we describe the results of some computational explorations in Thompson's group F. We describe experiments to estimate the cogrowth of F with respect to its standard finite generating set, … Here we describe the results of some computational explorations in Thompson's group F. We describe experiments to estimate the cogrowth of F with respect to its standard finite generating set, designed to address the subtle and difficult question whether or not Thompson's group is amenable. We also describe experiments to estimate the exponential growth rate of F and the rate of escape of symmetric random walks with respect to the standard generating set.

Chat View PDF

On groups that have normal forms computable in logspace

2013-02-26

Murray Elder , Gillian Z. Elston , Gretchen Ostheimer

Chat View PDF

Minimal length normal forms for some soluble groups

1996-12-01

J. R. J. Groves

Testing Cayley graph densities

2008-01-01

Goulnara Arzhantseva , Victor Guba , Martin Lustig +1 more

We present a computer-assisted analysis of combinatorial properties of the Cayley graphs of certain finitely generated groups: given a group with a finite set of generators, we study the density … We present a computer-assisted analysis of combinatorial properties of the Cayley graphs of certain finitely generated groups: given a group with a finite set of generators, we study the density of the corresponding Cayley graph, that is, the least upper bound for the average vertex degree (= number of adjacent edges) of any finite subgraph. It is known that an m-generated group is amenable if and only if the density of the corresponding Cayley graph equals to 2m. We test amenable and non-amenable groups, and also groups for which amenability is unknown. In the latter class we focus on Richard Thompson’s group F.

Chat View PDF

Finite and infinite cyclic extensions of free groups

1973-12-01

A. Karrass , Alfred Pietrowski , D. Solitar

Using Stalling's characterization [11] of finitely generated (f. g.) groups with infinitely many ends, and subgroup theorems for generalized free products and HNN groups (see [9], [5], and [7]), we … Using Stalling's characterization [11] of finitely generated (f. g.) groups with infinitely many ends, and subgroup theorems for generalized free products and HNN groups (see [9], [5], and [7]), we give (in Theorem 1) a n.a.s.c. for a f.g. group to be a finite extension of a free group. Specifically (using the terminology extension of and notation of [5]), a f.g. group G is a finite extension of a free group if and only if G is an HNN group where K is a tree product of a finite number of finite groups (the vertices of K ), and each (associated) subgroup L i , M i is a subgroup of a vertex of K .

Chat View PDF

Elementary theory of free non-abelian groups

2006-06-07

Olga Kharlampovich , Alexei Myasnikov

Diophantine geometry over groups VIII: Stability

2013-03-06

Zlil Sela

This paper is the eighth in a sequence on the structure of sets of solutions to systems of equations in free and hyperbolic groups, projections of such sets (Diophantine sets), … This paper is the eighth in a sequence on the structure of sets of solutions to systems of equations in free and hyperbolic groups, projections of such sets (Diophantine sets), and the structure of denable sets over free and hyperbolic groups. In this eighth paper we use a modication of the sieve procedure, which was used in proving quantier elimination in the theory of a free group, to prove that free and torsion-free (Gromov) hyperbolic groups are stable. In the

Chat View PDF

Almost convex groups

1987-02-01

J. W. Cannon

Commutativity in groups presented by finite Church-Rosser Thue systems

1988-01-01

Klaus Madlener , Friedrich Otto

Let G be a group that can be presented by a flnite Church-Rosser Thue System.Then, whenever two éléments u and v of G commute, the subgroup < u, v > … Let G be a group that can be presented by a flnite Church-Rosser Thue System.Then, whenever two éléments u and v of G commute, the subgroup < u, v > G o f G generaled by u and v is finite, or it is infinité cycîic.In particular, each finiteîy generaled abelian subgroup of G is either finite or isomorphic to Z. Further, if the center of G is non-trivial, then G itself is already finite or isomorphic to Z, Résumé.-Soit G un groupe présenté par un système de Thue fini ayant la propriété Church-Rosser, Si deux éléments u et v de G commutent, alors le sous-groupe <u, V} G de G quHls engendrent est fini, ou cyclique.En particulier, tout sous-groupe abélien finissent engendré de G est fini ou isomorphe à Z. De plus, si G possède un centre non trivial, alors G lui-même est fini ou isomorphe à Z.

Chat View PDF

A Survey of Stack-Sorting Disciplines

2003-07-27

Miklós Bóna

We review the various ways that stacks, their variations and their combinations, have been used as sorting devices. In particular, we show that they have been a key motivator for … We review the various ways that stacks, their variations and their combinations, have been used as sorting devices. In particular, we show that they have been a key motivator for the study of permutation patterns. We also show that they have connections to other areas in combinatorics such as Young tableau, planar graph theory, and simplicial complexes.

Chat View PDF

Canonical representatives and equations in hyperbolic groups

1995-12-01

Eliyahu Rips , Zlil Sela

Combinatorial group theory

1978-04-01

Gian‐Carlo Rota

Cogrowth of groups and simple random walks

1983-09-01

Wolfgang Woess

Groups presented by finite two-monadic Church-Rosser Thue systems

1986-01-01

Jürgen Avenhaus , Klaus Madlener , F. Otto

It is shown that a group <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> can be defined by a monoid-presentation of the form <inline-formula content-type="math/mathml"> … It is shown that a group <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> can be defined by a monoid-presentation of the form <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis normal upper Sigma semicolon upper T right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi mathvariant="normal">Σ</mml:mi> <mml:mo>;</mml:mo> <mml:mi>T</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(\Sigma ;T)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T"> <mml:semantics> <mml:mi>T</mml:mi> <mml:annotation encoding="application/x-tex">T</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a finite two-monadic Church-Rosser Thue system over <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Sigma"> <mml:semantics> <mml:mi mathvariant="normal">Σ</mml:mi> <mml:annotation encoding="application/x-tex">\Sigma</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, if and only if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is isomorphic to the free product of a finitely generated free group with a finite number of finite groups.

Chat View PDF

GROUPS WITH INDEXED CO-WORD PROBLEM

2006-10-01

Derek F. Holt , Claas E. Röver

We investigate co-indexed groups, that is groups whose co-word problem (all words defining nontrivial elements) is an indexed language. We show that all Higman–Thompson groups and a large class of … We investigate co-indexed groups, that is groups whose co-word problem (all words defining nontrivial elements) is an indexed language. We show that all Higman–Thompson groups and a large class of tree automorphism groups defined by finite automata are co-indexed groups. The latter class is closely related to dynamical systems and includes the Grigorchuk 2-group and the Gupta–Sidki 3-group. The co-word problems of all these examples are in fact accepted by nested stack automata with certain additional properties, and we establish various closure properties of this restricted class of co-indexed groups, including closure under free products.

The word and geodesic problems in free solvable groups

2010-04-14

Alexei Myasnikov , В. А. Романьков , Alexander Ushakov +1 more

We study the computational complexity of the Word Problem (WP) in free solvable groups <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript r comma d"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>r</mml:mi> … We study the computational complexity of the Word Problem (WP) in free solvable groups <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript r comma d"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">S_{r,d}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r greater-than-or-equal-to 2"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">r \geq 2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the rank and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d greater-than-or-equal-to 2"> <mml:semantics> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">d \geq 2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the solvability class of the group. It is known that the Magnus embedding of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript r comma d"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">S_{r,d}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> into matrices provides a polynomial time decision algorithm for WP in a fixed group <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript r comma d"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">S_{r,d}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Unfortunately, the degree of the polynomial grows together with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, so the uniform algorithm is not polynomial in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. In this paper we show that WP has time complexity <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis r n log Subscript 2 Baseline n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>r</mml:mi> <mml:mi>n</mml:mi> <mml:msub> <mml:mi>log</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>⁡</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(r n \log _2 n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript r comma 2"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">S_{r,2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis n cubed r d right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mi>r</mml:mi> <mml:mi>d</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(n^3 r d)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript r comma d"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">S_{r,d}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d greater-than-or-equal-to 3"> <mml:semantics> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">d \geq 3</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. However, it turns out, that a seemingly close problem of computing the geodesic length of elements in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript r comma 2"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">S_{r,2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N upper P"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mi>P</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">NP</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-complete. We prove also that one can compute Fox derivatives of elements from <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript r comma d"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">S_{r,d}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in time <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis n cubed r d right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mi>r</mml:mi> <mml:mi>d</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(n^3 r d)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>; in particular, one can use efficiently the Magnus embedding in computations with free solvable groups. Our approach is based on such classical tools as the Magnus embedding and Fox calculus, as well as on relatively new geometric ideas; in particular, we establish a direct link between Fox derivatives and geometric flows on Cayley graphs.

A linear-time algorithm to compute geodesics in solvable Baumslag–Solitar groups

2010-01-01

Murray Elder

We present an algorithm to convert a word of length $n$ in the standard generators of the solvable Baumslag–Solitar group $\operatorname{BS}(1,p)$ into a geodesic word, which runs in linear time … We present an algorithm to convert a word of length $n$ in the standard generators of the solvable Baumslag–Solitar group $\operatorname{BS}(1,p)$ into a geodesic word, which runs in linear time and $O(n\log n)$ space on a random access machine.

Chat View PDF

A characterisation of virtually free groups

2007-09-10

Robert H. Gilman , Susan Hermiller , Derek F. Holt +1 more

Chat View PDF

Formal languages and infinite groups

1995-11-22

Robert H. Gilman

This article is an introduction to formal languages from the point of view of combinatorial group theory. This article is an introduction to formal languages from the point of view of combinatorial group theory.

Chat View PDF

A REMARK ABOUT COMBINGS OF GROUPS

1993-12-01

Martin R. Bridson , Robert H. Gilman

It is currently unknown whether or not there exist (synchronously) combable groups which are not automatic. This note settles an analogous question in a simpler context. The notion of a … It is currently unknown whether or not there exist (synchronously) combable groups which are not automatic. This note settles an analogous question in a simpler context. The notion of a broomlike combing is introduced. It is shown that if a group admits a broomlike combing then it admits a broomlike combing in which the language of combing words is regular. A finitely generated group admits a broomlike combing if and only if it contains a free subgroup of finite index.

Higher rank lamplighter groups are graph automatic

2017-11-06

Sophie Bérubé , Tara Palnitkar , Jennifer Taback

Chat View PDF

Finding all solutions of equations in free groups and monoids with involution

2016-10-06

Volker Diekert , Artur Jeż , Wojciech Plandowski

Chat View PDF

A context-free and a 1-counter geodesic language for a Baumslag–Solitar group

2005-04-07

Murray Elder

Chat View PDF

Finiteness Properties of Asynchronously Automatic Groups

1995-12-31

S. M. Gersten

Doubles, Finiteness Properties of Groups, and Quadratic Isoperimetric Inequalities

1999-04-01

Martin R. Bridson

ON COMPUTING GEODESICS IN BAUMSLAG–SOLITAR GROUPS

2011-02-01

Volker Diekert , Jürn Laun

We introduce the peak normal form for elements of the Baumslag–Solitar groups BS(p,q). This normal form is very close to the length-lexicographical normal form, but more symmetric. Both normal forms … We introduce the peak normal form for elements of the Baumslag–Solitar groups BS(p,q). This normal form is very close to the length-lexicographical normal form, but more symmetric. Both normal forms are geodesic. This means the normal form of an element u -1 v yields the shortest path between u and v in the Cayley graph. For horocyclic elements the peak normal form and the length-lexicographical normal form coincide. The main result of this paper is that we can compute the peak normal form in polynomial time if p divides q. As consequence we can compute geodesic lengths in this case. In particular, this gives a partial answer to Question 1 in [4] For arbitrary p and q it is possible to compute the peak normal form (length-lexicographical normal form resp.) also the for elements in the horocyclic subgroup and, more generally, for elements which we call hills. This approach leads to a linear time reduction of the problem of computing geodesics to the problem of computing geodesics for Britton-reduced words where the t-sequence starts with t -1 and ends with t.

Chat View PDF

Cayley Automatic Representations of Wreath Products

2016-02-01

Dmitry Berdinsky , Bakhadyr Khoussainov

We construct the representations of Cayley graphs of wreath products using finite automata, pushdown automata and nested stack automata. These representations are in accordance with the notion of Cayley automatic … We construct the representations of Cayley graphs of wreath products using finite automata, pushdown automata and nested stack automata. These representations are in accordance with the notion of Cayley automatic groups introduced by Kharlampovich, Khoussainov and Miasnikov and its extensions introduced by Elder and Taback. We obtain the upper and lower bounds for a length of an element of a wreath product in terms of the representations constructed.

Chat View PDF

On Growth Rates of Closed Permutation Classes

2003-04-10

Tomáš Kaiser , Martin Klazar

A class of permutations $\Pi$ is called closed if $\pi\subset\sigma\in\Pi$ implies $\pi\in\Pi$, where the relation $\subset$ is the natural containment of permutations. Let $\Pi_n$ be the set of all permutations … A class of permutations $\Pi$ is called closed if $\pi\subset\sigma\in\Pi$ implies $\pi\in\Pi$, where the relation $\subset$ is the natural containment of permutations. Let $\Pi_n$ be the set of all permutations of $1,2,\dots,n$ belonging to $\Pi$. We investigate the counting functions $n\mapsto|\Pi_n|$ of closed classes. Our main result says that if $|\Pi_n| < 2^{n-1}$ for at least one $n\ge 1$, then there is a unique $k\ge 1$ such that $F_{n,k}\le |\Pi_n|\le F_{n,k}\cdot n^c$ holds for all $n\ge 1$ with a constant $c>0$. Here $F_{n,k}$ are the generalized Fibonacci numbers which grow like powers of the largest positive root of $x^k-x^{k-1}-\cdots-1$. We characterize also the constant and the polynomial growth of closed permutation classes and give two more results on these.

Chat View PDF

Groups of polynomial growth and expanding maps

1981-12-01

Mikhael Gromov

HYPERBOLICITY OF GROUPS WITH SUBQUADRATIC ISOPERIMETRIC INEQUALITY

1991-09-01

A. Yu. Olshanskii

The author gives a simple and coherent proof of Gromov's statement on hyperbolicity of groups with subquadratic isoperimetric inequality. The author gives a simple and coherent proof of Gromov's statement on hyperbolicity of groups with subquadratic isoperimetric inequality.

On the cogrowth of Thompson's group F

2012-01-01

Murray Elder , Andrew Rechnitzer , Thomas G. Wong

We investigate the cogrowth and distribution of geodesics in R. Thompson's group $F$. We investigate the cogrowth and distribution of geodesics in R. Thompson's group $F$.

Chat View PDF