Logspace and compressed-word computations in nilpotent groups

DOI10.1090/TRAN/8623OpenAlexW2211936080MaRDI QIDQ5100019FDOQ5100019

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

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

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)

Cites Work

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

Cited In (11)

• Algorithmic problems for class-2 nilpotents MR-groups
• Two general schemes of algebraic cryptography
• Low-complexity computations for nilpotent subgroup problems
• Parallel complexity for nilpotent groups
• Non-commutative lattice problems
• A PTIME solution to the restricted conjugacy problem in generalized Heisenberg 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)