Algorithms and topology of Cayley graphs for groups. (Q404175): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(7 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Q404174 / rank | |||
Property / author | |||
Property / author: Derek F. Holt / rank | |||
Property / author | |||
Property / author: Susan M. Hermiller / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Derek F. Holt / rank | |||
Normal rank | |||
Property / 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. 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. | |||
Property / 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. 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20F65 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20F10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20F05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 57M05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q42 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6339507 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
automatic groups | |||
Property / zbMATH Keywords: automatic groups / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
finitely generated groups | |||
Property / zbMATH Keywords: finitely generated groups / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Cayley graphs | |||
Property / zbMATH Keywords: Cayley graphs / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
autostackable groups | |||
Property / zbMATH Keywords: autostackable groups / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
van Kampen diagrams | |||
Property / zbMATH Keywords: van Kampen diagrams / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
finite presentations | |||
Property / zbMATH Keywords: finite presentations / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
rewriting systems | |||
Property / zbMATH Keywords: rewriting systems / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
word problem | |||
Property / zbMATH Keywords: word problem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
3-manifolds | |||
Property / zbMATH Keywords: 3-manifolds / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Vitaliĭ Roman'kov / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2028398007 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1307.4981 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sol Geometry Groups are not Asynchronously Automatic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The geometry of the word problem for finitely generated groups. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4780255 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Formal language theory and the geometry of 3-manifolds / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A finiteness property and an automatic structure for Coxeter groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Geodesic automation and growth functions for Artin groups of finite type / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rewriting systems in alternating knot groups with the Dehn presentation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3577833 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4003861 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4012142 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Automatic quotients of free groups. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Soluble groups with a finite rewriting system / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rewriting systems of Coxeter groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms and geometry for graph products of groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Artin groups, rewriting systems and three-manifolds / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Measuring the tameness of almost convex groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rewriting systems and geometric three-manifolds / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Artin groups of large type are shortlex automatic with regular geodesics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3862379 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: TWO AUTOMATIC SPANNING TREES IN SMALL CANCELLATION GROUP PRESENTATIONS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: From automatic structures to automatic groups. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A catalogue of complete group presentations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3992832 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Combinatorial group theory. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Group-Theoretic Decision Problems and Their Classification. (AM-68) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4938677 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Artin groups of extra-large type are biautomatic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5541339 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 00:30, 9 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms and topology of Cayley graphs for groups. |
scientific article |
Statements
Algorithms and topology of Cayley graphs for groups. (English)
0 references
4 September 2014
0 references
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. 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.
0 references
automatic groups
0 references
finitely generated groups
0 references
Cayley graphs
0 references
autostackable groups
0 references
van Kampen diagrams
0 references
finite presentations
0 references
rewriting systems
0 references
word problem
0 references
3-manifolds
0 references