GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS

DOI10.1142/S0218196707003913zbMath1171.20016arXiv0903.3754OpenAlexW1997046888MaRDI QIDQ5386949

Alexandre V. Borovik, Vladimir N. Remeslennikov, Alexei G. Myasnikov

Publication date: 14 May 2008

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

algorithmsword problemtime complexityHNN-extensionsconjugacy problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (8)

Random equations in free groups ⋮ Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem ⋮ Partial word and equality problems and Banach densities ⋮ Amalgamated products of groups: measures of random normal forms. ⋮ THE CONJUGACY PROBLEM IN AMALGAMATED PRODUCTS I: REGULAR ELEMENTS AND BLACK HOLES ⋮ Random equations in nilpotent groups. ⋮ Exponentially generic subsets of groups ⋮ Conjugacy in Baumslag's group, generic case complexity, and division in power circuits

Cites Work

• Unnamed Item
• Unnamed Item
• Average-case complexity and decision problems in group theory.
• Cogrowth of groups and simple random walks
• Automatic groups and amalgams
• Generic-case complexity, decision problems in group theory, and random walks.
• An algebraic method for public-key cryptography
• Stallings foldings and subgroups of free groups
• Statistical properties of finitely presented groups
• Recursively enumerable degress and the conjugacy problem
• ALMOST EVERY GROUP IS HYPERBOLIC
• Hyperbolic groups and free constructions
• MULTIPLICATIVE MEASURES ON FREE GROUPS

This page was built for publication: GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS