On groups that have normal forms computable in logspace.

DOI10.1016/J.JALGEBRA.2013.01.036MaRDI QIDQ375212zbMATHOpenAlexFDO

Authors Gretchen Ostheimer, Murray Elder, Gillian 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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3642708 (Why is no real title available?)
• scientific article; zbMATH DE number 3815938 (Why is no real title available?)
• scientific article; zbMATH DE number 3784868 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 2146477 (Why is no real title available?)
• scientific article; zbMATH DE number 3411305 (Why is no real title available?)
• Group-based cryptography
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• Growth Series of Some Wreath Products
• Inverse monoids: decidability and complexity of algebraic questions.
• Isoperimetric functions of groups and computational complexity of the word problem
• Logspace computations in graph groups and Coxeter groups.
• On Infinite Soluble Groups (III)
• THE OCCURRENCE PROBLEM FOR FREE PRODUCTS OF GROUPS
• The word and geodesic problems in free solvable groups.
• Word Problems Solvable in Logspace

Cited in

(9)

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

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)