On groups that have normal forms computable in logspace.

DOI10.1016/J.JALGEBRA.2013.01.036zbMATH Open1279.20042arXiv1201.4363OpenAlexW1995278772MaRDI QIDQ375212FDOQ375212

Gretchen Ostheimer, Murray Elder, Gillian Elston

Publication date: 28 October 2013

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

Abstract: We consider the class of finitely generated groups which have a normal form computable in logspace. We prove that the class of such groups is closed under finite extensions, finite index subgroups, direct products, wreath products, and also certain free products, and includes the solvable Baumslag-Solitar groups, as well as non-residually finite (and hence non-linear) examples. We define a group to be logspace embeddable if it embeds in a group with normal forms computable in logspace. We prove that finitely generated nilpotent groups are logspace embeddable. It follows that all groups of polynomial growth are logspace embeddable.

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

Recommendations

• Logspace and compressed-word computations in nilpotent groups
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Logspace computations in Coxeter groups and graph groups.
• Logspace computations in graph groups and Coxeter groups.
• On the Geometry of Normal Forms in Discrete Groups

zbMATH Keywords

finitely generated groupswreath productsBaumslag-Solitar groupslogspace algorithmslogspace embeddable groupslogspace normal formslogspace word problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Lamplighter groups and automata
• Logspace and compressed-word computations in nilpotent groups
• \(\mathcal C\)-graph automatic groups.
• On the Geometry of Normal Forms in Discrete Groups
• Logspace computations in graph products
• Log-space conjugacy problem in the Grigorchuk group

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q375212)