Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.

DOI10.2140/pjm.2006.223.113zbMath1149.20028arXivmath/0303386MaRDI QIDQ868743

Ilya Kapovich, Vladimir Shpilrain, Paul E. Schupp

Publication date: 26 February 2007

Published in: Pacific Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

one-relator groups; Whitehead algorithm; generic-case complexity

Mathematics Subject Classification ID

68W40: Analysis of algorithms

20F05: Generators, relations, and presentations of groups

20E36: Automorphisms of infinite groups

03D15: Complexity of computation (including implicit computational complexity)

57M05: Fundamental group, presentations, free differential calculus

20E05: Free nonabelian groups

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

20P05: Probabilistic methods in group theory

Related Items

Statistical properties of subgroups of free groups, Subnormal subgroups in free groups, their growth and cogrowth, GENERICITY OF FILLING ELEMENTS, ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS, Conformal dimension and random groups., Random groups arising as graph products., Random equations in nilpotent groups., Almost all one-relator groups with at least three generators are residually finite., On mathematical contributions of Paul E. Schupp, Sublinear time algorithms in the theory of groups and semigroups., Exponentially generic subsets of groups, Some metric properties of automorphisms of groups., A tighter bound for the number of words of minimum length in an automorphic orbit., The subadditive ergodic theorem and generic stretching factors for free group automorphisms., On the asymptotics of visible elements and homogeneous equations in surface groups., A hybrid search algorithm for the Whitehead minimization problem., Counting words of minimum length in an automorphic orbit., Random equations in free groups, Virtual geometricity is rare, Search and witness problems in group theory, Asymptotic invariants, complexity of groups and related problems, ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM, On an algorithm to decide whether a free group is a free factor of another