Logspace and compressed-word computations in nilpotent groups

DOI10.1090/TRAN/8623MaRDI QIDQ5100019zbMATH OpenOpenAlexFDO

Authors

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) Derived series, central series, and generalizations for groups (20F14) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Nilpotent groups (20F18)

Recommendations

• Low-complexity computations for nilpotent subgroup problems
• Parallel complexity for nilpotent groups
• scientific article; zbMATH DE number 919272
• Finding intersections and normalizers in finitely generated nilpotent groups
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups

Cites work

• scientific article; zbMATH DE number 3875506 (Why is no real title available?)
• scientific article; zbMATH DE number 534859 (Why is no real title available?)
• scientific article; zbMATH DE number 799777 (Why is no real title available?)
• scientific article; zbMATH DE number 7559146 (Why is no real title available?)
• Algorithmics on SLP-compressed strings: a survey
• Automata, Languages and Programming
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• Compressed membership for NFA (DFA) with compressed labels is in NP (P)
• Compressed words and automorphisms in fully residually free groups.
• Computational algorithms for deciding some problems for nilpotent groups
• Conjugacy in Nilpotent Groups
• Conjugate separability in polycyclic groups
• Efficient Computation in Groups Via Compression
• Evaluating matrix circuits
• Full residual finiteness growths of nilpotent groups
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• Logspace computations in graph groups and Coxeter groups.
• Matrix representations for torsion-free nilpotent groups by Deep Thought.
• Non-commutative lattice problems
• On groups that have normal forms computable in logspace.
• On homomorphisms onto finite groups
• Polynomial time conjugacy in wreath products and free solvable groups.
• Polynomial-time word problems.
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• SOLVING THE WORD PROBLEM IN REAL TIME
• Some general algorithms. II: Nilpotent groups
• Symbolic Collection using Deep Thought
• The Post correspondence problem in groups.
• The algorithmic theory of polycyclic-by-finite groups
• Time complexity of the conjugacy problem in relatively hyperbolic groups.
• Word Problems Solvable in Logspace

Cited in

(11)

• Algorithmic problems for class-2 nilpotents MR-groups
• Two general schemes of algebraic cryptography
• Low-complexity computations for nilpotent subgroup problems
• Non-commutative lattice problems
• A PTIME solution to the restricted conjugacy problem in generalized Heisenberg groups
• Parallel complexity for nilpotent groups
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• Logspace computations in Coxeter groups and graph groups.
• Algorithmic use of the Mal'cev correspondence.
• On groups that have normal forms computable in logspace.
• Distortion of embeddings of a torsion-free finitely generated nilpotent group into a unitriangular group

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

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