Logspace and compressed-word computations in nilpotent groups

DOI10.1090/tran/8623OpenAlexW2211936080MaRDI QIDQ5100019

No author found.

Publication date: 29 August 2022

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nilpotent groups (20F18) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Derived series, central series, and generalizations for groups (20F14)

Related Items (6)

Non-commutative lattice problems ⋮ A PTIME solution to the restricted conjugacy problem in generalized Heisenberg groups ⋮ Distortion of embeddings of a torsion-free finitely generated nilpotent group into a unitriangular group ⋮ TC^0 circuits for algorithmic problems in nilpotent groups ⋮ Low-complexity computations for nilpotent subgroup problems ⋮ Two general schemes of algebraic cryptography

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-commutative lattice problems
• Full residual finiteness growths of nilpotent groups
• On groups that have normal forms computable in logspace.
• The Post correspondence problem in groups.
• Polynomial-time word problems.
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Some general algorithms. II: Nilpotent groups
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• The algorithmic theory of polycyclic-by-finite groups
• Conjugate separability in polycyclic groups
• Matrix representations for torsion-free nilpotent groups by Deep Thought.
• Algorithmics on SLP-compressed strings: A survey
• Polynomial time conjugacy in wreath products and free solvable groups
• Logspace Computations in Graph Groups and Coxeter Groups
• Time complexity of the conjugacy problem in relatively hyperbolic groups
• SOLVING THE WORD PROBLEM IN REAL TIME
• Evaluating Matrix Circuits
• Efficient Computation in Groups Via Compression
• COMPRESSED WORDS AND AUTOMORPHISMS IN FULLY RESIDUALLY FREE GROUPS
• Word Problems Solvable in Logspace
• Symbolic Collection using Deep Thought
• On homomorphisms onto finite groups
• COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS
• Conjugacy in Nilpotent Groups
• Automata, Languages and Programming
• Computational algorithms for deciding some problems for nilpotent groups

This page was built for publication: Logspace and compressed-word computations in nilpotent groups