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

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