Average-case complexity of the Whitehead problem for free groups

DOI10.1080/00927872.2022.2113791MaRDI QIDQ5879445zbMATH OpenOpenAlexFDO

Authors Vladimir Shpilrain

Publication date 1 March 2023

Published in Communications in Algebra (Search for Journal in Brave)

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

zbMATH Keywords

automorphismsfree groupaverage-case complexityWhitehead problem

Mathematics Subject Classification ID

Automorphism groups of groups (20F28) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Average-case complexity and decision problems in group theory.
• ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 2144698

Cites work

• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 2144699 (Why is no real title available?)
• scientific article; zbMATH DE number 1421182 (Why is no real title available?)
• scientific article; zbMATH DE number 3045103 (Why is no real title available?)
• A remark on Whitehead's cut-vertex lemma
• Automorphic orbits in free groups.
• Average-case complexity and decision problems in group theory.
• Counting words of minimum length in an automorphic orbit.
• Densities in free groups and \(\mathbb{Z}^k\), visible points and test elements.
• Fast Pattern Matching in Strings
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Generic-case complexity, decision problems in group theory, and random walks.
• Growth and ergodicity of context-free languages
• Growth of primitive elements in free groups.
• On equivalent sets of elements in a free group
• On two-generator subgroups in \(\mathrm{SL}_2(\mathbb{Z})\), \(\mathrm{SL}_2(\mathbb{Q})\), and \(\mathrm{SL}_2(\mathbb{R})\)
• Sublinear time algorithms in the theory of groups and semigroups.
• The class of groups all of whose subgroups with lesser number of generators are free is generic

Cited in

(8)

• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Average-case complexity and decision problems in group theory.
• scientific article; zbMATH DE number 2144698 (Why is no real title available?)
• Heuristics for the Whitehead Minimization Problem
• The central tree property and algorithmic problems on subgroups of free groups
• Average-case complexity of the Whitehead problem for a free group
• On the genericity of Whitehead minimality
• Generic-case complexity, decision problems in group theory, and random walks.

This page was built for publication: Average-case complexity of the Whitehead problem for free groups

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