Algorithms and topology of Cayley graphs for groups.

DOI10.1016/J.JALGEBRA.2014.06.001MaRDI QIDQ404175zbMATH OpenOpenAlexFDO

Authors Mark Brittenham, Susan Hermiller, Derek F. Holt

Publication date 4 September 2014

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.4981

zbMATH Keywords

3-manifoldsautomatic groupsautostackable groupsCayley graphsfinite presentationsfinitely generated groupsrewriting systemsvan Kampen diagramsword problem

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Geometric group theory (20F65) Fundamental group, presentations, free differential calculus (57M05) Grammars and rewriting systems (68Q42)

Abstract: Autostackability for finitely generated groups is defined via a topological property of the associated Cayley graph which can be encoded in a finite state automaton. Autostackable groups have solvable word problem and an effective inductive procedure for constructing van Kampen diagrams with respect to a canonical finite presentation. A comparison with automatic groups is given. Another characterization of autostackability is given in terms of prefix-rewriting systems. Every group which admits a finite complete rewriting system or an asynchronously automatic structure with respect to a prefix-closed set of normal forms is also autostackable. As a consequence, the fundamental group of every closed 3-manifold with any of the eight possible uniform geometries is autostackable.

Review text

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.NEWLINENEWLINE 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.

Recommendations

• Homology and closure properties of autostackable groups
• From automatic structures to automatic groups.
• Geometry of the word problem for 3-manifold groups
• A uniform model for almost convexity and rewriting systems
• Cayley graph automatic groups are not necessarily Cayley graph biautomatic

Cites work

• A catalogue of complete group presentations
• A finiteness property and an automatic structure for Coxeter groups
• Algorithms and geometry for graph products of groups
• Artin groups of extra-large type are biautomatic
• Artin groups of large type are shortlex automatic with regular geodesics.
• Artin groups, rewriting systems and three-manifolds
• Automatic quotients of free groups.
• Combinatorial group theory.
• Formal language theory and the geometry of 3-manifolds
• From automatic structures to automatic groups.
• Geodesic automation and growth functions for Artin groups of finite type
• Graph theory
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 43246 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 67432 (Why is no real title available?)
• scientific article; zbMATH DE number 1822302 (Why is no real title available?)
• scientific article; zbMATH DE number 1405695 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• Measuring the tameness of almost convex groups
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• Rewriting systems and geometric three-manifolds
• Rewriting systems in alternating knot groups with the Dehn presentation
• Rewriting systems of Coxeter groups
• Sol geometry groups are not asynchronously automatic
• Soluble groups with a finite rewriting system
• The geometry of the word problem for finitely generated groups.
• TWO AUTOMATIC SPANNING TREES IN SMALL CANCELLATION GROUP PRESENTATIONS

Cited in

(11)

• Algorithms and geometry for graph products of groups
• Geometry of the word problem for 3-manifold groups
• HNN extensions and stackable groups
• From automatic structures to automatic groups.
• Cayley polynomial-time computable groups
• Lamplighter groups and automata
• Autostackability of Thompson's group \(F\)
• TWO AUTOMATIC SPANNING TREES IN SMALL CANCELLATION GROUP PRESENTATIONS
• A uniform model for almost convexity and rewriting systems
• Homology and closure properties of autostackable groups
• Cayley linear-time computable groups

This page was built for publication: Algorithms and topology of Cayley graphs for groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404175)