On groups that have normal forms computable in logspace.
From MaRDI portal
Publication:375212
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
wreath products; finitely generated groups; Baumslag-Solitar groups; logspace algorithms; logspace embeddable groups; logspace normal forms; logspace word problem
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)