On groups that have normal forms computable in logspace.

DOI10.1016/j.jalgebra.2013.01.036zbMath1279.20042arXiv1201.4363OpenAlexW1995278772MaRDI 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 productsfinitely generated groupsBaumslag-Solitar groupslogspace algorithmslogspace embeddable groupslogspace normal formslogspace word problem

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

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

Cites Work

• 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)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On groups that have normal forms computable in logspace.