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

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)

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.

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

• 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?)
• 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
• 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
• TWO AUTOMATIC SPANNING TREES IN SMALL CANCELLATION GROUP PRESENTATIONS
• The geometry of the word problem for finitely generated groups.

Cited in

(11)

• Lamplighter groups and automata
• Algorithms and geometry for graph products of groups
• Cayley linear-time computable groups
• From automatic structures to automatic 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
• A uniform model for almost convexity and rewriting systems
• HNN extensions and stackable groups
• 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)