Algorithms and topology of Cayley graphs for groups

作者：Brittenham Mark; Hermiller Susan^*; Holt Derek

来源：Journal of Algebra, 2014, 415: 112-136.

DOI：10.1016/j.jalgebra.2014.06.001

• Automatic group
• Rewriting system
• Word problem
• 3-Manifold

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.

• 出版日期2014-10-1