BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Derek F. Holt appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We investigate the solution sets to equations in the solvable Baumslag-Solitar groups $BS(1,k)$, $k\geq2$, and show that these sets are represented by EDT0L languages in some cases. In particular, we prove that the multiplication table of such a group forms an EDT0L language with respect to a specific natural normal form for group elements.
We prove that the generalised word problem of a finitely generated subgroup of a finitely generated virtually free group is context-free, that a hyperbolic group must be virtually free if it has a torsion-free quasiconvex subgroup of infinite index with context-free generalised word problem, and that, for any hyperbolic group, the generalised word problem of a torsion-free quasiconvex subgroup is recognised by a real-time Turing machine.
We prove that graph products of sofic groups are sofic, as are graphs of groups for which vertex groups are sofic and edge groups are amenable.
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 generating set are geodesic.
We prove three results about the graph product $G=\G(Γ;G_v, v \in V(Γ))$ of groups $G_v$ over a graph $Γ$. The first result generalises a result of Servatius, Droms and Servatius, proved by them for right-angled Artin groups; we prove a necessary and sufficient condition on a finite graph $Γ$ for the kernel of the map from $G$ to the associated direct product to be free (one part of this result already follows from a result in S. Kim's Ph.D. thesis). The second result generalises a result of Hermiller and Sunic, again from right-angled Artin groups; we prove that for a graph $Γ$ with finite chromatic number, $G$ has a series in which every factor is a free product of vertex groups. The third result provides an alternative proof of a theorem due to Meier, which provides necessary and sufficient conditions on a finite graph $Γ$ for $G$ to be hyperbolic.
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 which the set of all geodesic words with respect to some generating set is ($k$-)locally testable, and we call such groups ($k$-)locally testable. We show that a group is \klt{1} if and only if it is free abelian. We show that the class of ($k$-)locally testable groups is closed under taking finite direct products. We show also that a locally testable group has finitely many conjugacy classes of torsion elements. Our work involved computer investigations of specific groups, for which purpose we implemented an algorithm in \GAP\ to compute a finite state automaton with language equal to the set of all geodesics of a group (assuming that this language is regular), starting from a shortlex automatic structure. We provide a brief description of that algorithm.
We prove that the rapid decay property (RD) of groups is preserved by graph products defined on finite simplicial graphs.
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 the set of all geodesics (over the same generating set) is a star-free regular language. Star-free regularity of the geodesic set is shown to be dependent on the generating set chosen, even for free groups. We also show that the class of groups whose geodesic sets are star-free with respect to some generating set is closed under taking graph (and hence free and direct) products, and includes all virtually abelian groups.
Let G be a word-hyperbolic group with given finite generating set, for which various standard structures and constants have been pre-computed. A (non-practical) algorithm is described that, given as input two lists A and B, each composed of m words in the generators and their inverses, determines whether or not the lists are conjugate in G, and returns a conjugating element should one exist. The algorithm runs in time O(m mu)$, where mu is an upper bound on the lengths of elements in the two lists. Similarly, an algorithm is outlined that computes generators of the centraliser of A, with the same bound on running time.
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 the asynchronous automaticity of an HNN extension is then proved and applied to an example that was proposed by Mark Sapir.