On groups that have normal forms computable in logspace.

DOI10.1016/j.jalgebra.2013.01.036zbMath1279.20042arXiv1201.4363MaRDI QIDQ375212

Gretchen Ostheimer, Murray J. Elder, Gillian Z. Elston

Publication date: 28 October 2013

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

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

zbMATH Keywords

wreath products; finitely generated groups; Baumslag-Solitar groups; logspace algorithms; logspace embeddable groups; logspace normal forms; logspace word problem

Mathematics Subject Classification ID

20F05: Generators, relations, and presentations of groups

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Logspace and compressed-word computations in nilpotent groups, Logspace computations in graph products, \(\mathcal C\)-graph automatic groups., Log-space conjugacy problem in the Grigorchuk group, Lamplighter groups and automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Group-based cryptography
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• Isoperimetric functions of groups and computational complexity of the word problem
• Inverse monoids: decidability and complexity of algebraic questions.
• Logspace Computations in Graph Groups and Coxeter Groups
• Growth Series of Some Wreath Products
• Word Problems Solvable in Logspace
• The word and geodesic problems in free solvable groups
• THE OCCURRENCE PROBLEM FOR FREE PRODUCTS OF GROUPS
• On Infinite Soluble Groups (III)