Algorithms and topology of Cayley graphs for groups. (Q404175)

The authors define the notion of autostackability for finitely generated groups using properties very closely related to automatic structures, that hold for 3-manifold groups of all uniform geometries. A topological property of the associated Cayley graph is used in this definition which can be encoded in a finite state automaton. Autostackable groups have solvable word problem and effective inductive procedure for constructing van Kampen diagrams with respect to a canonical finite presentation. Another characterization of autostackability is given in terms of prefix-rewriting systems. It is shown that every group admitting a finite complete rewriting system or an asynchronously automatic structure w.r.t. a prefix-closed set of normal forms is also autostackable. We notice that recently Kharlampovich, Khoussainov, and Miasnikov have defined the class of Cayley automatic groups, extending the notion of an automatic structure, but it is as yet unknown whether all Nil and Sol 3-manifold groups are Cayley automatic.