Algorithms and topology of Cayley graphs for groups.

DOI10.1016/J.JALGEBRA.2014.06.001zbMATH Open1305.20051arXiv1307.4981OpenAlexW2028398007MaRDI QIDQ404175FDOQ404175

Authors: Mark Brittenham, Susan Hermiller, Derek F. Holt 

Publication date: 4 September 2014

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

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.

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

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

zbMATH Keywords

Cayley graphsfinitely generated groupsword problem3-manifoldsrewriting systemsfinite presentationsvan Kampen diagramsautomatic groupsautostackable groups

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Lamplighter groups and automata
• Cayley linear-time computable groups
• Algorithms and geometry for graph products of groups
• Autostackability of Thompson's group \(F\)
• Homology and closure properties of autostackable groups
• Geometry of the word problem for 3-manifold groups
• TWO AUTOMATIC SPANNING TREES IN SMALL CANCELLATION GROUP PRESENTATIONS
• Cayley polynomial-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)