Algorithms and topology of Cayley graphs for groups.
From MaRDI portal
(Redirected from Publication:404175)
3-manifoldsautomatic groupsautostackable groupsCayley graphsfinite presentationsfinitely generated groupsrewriting systemsvan Kampen diagramsword problem
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.
Recommendations
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)
