Linear time algorithm for the conjugacy problem in the first Grigorchuk group

DOI10.1142/S0218196721500363MaRDI QIDQ5002196zbMATH OpenOpenAlexFDO

Authors

Publication date 27 July 2021

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

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

zbMATH Keywords

complexityconjugacy problemGrigorchuk groupword problem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Groups acting on trees (20E08) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Recommendations

• The conjugacy problem in the Grigorchuk group is polynomial time decidable.
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• Conjugacy problem in a class of \(2\)-groups
• Computational complexity and the conjugacy problem
• Time complexity of the conjugacy problem in relatively hyperbolic groups.

Cites work

• scientific article; zbMATH DE number 5152179 (Why is no real title available?)
• scientific article; zbMATH DE number 1267534 (Why is no real title available?)
• scientific article; zbMATH DE number 1544074 (Why is no real title available?)
• A STRUCTURAL PROPERTY CONCERNING ABSTRACT COMMENSURABILITY OF SUBGROUPS
• A system of defining relations for a Grigorchuk group
• Conjugacy problem in a class of \(2\)-groups
• Conjugacy problem in an automorphism group of an infinite tree
• Cryptography and Coding
• Fast Pattern Matching in Strings
• Lexicographically least circular substrings
• On Burnside's problem on periodic groups
• Quadratic equations in the Grigorchuk group.
• Random subgroups and analysis of the length-based and quotient attacks
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• The complexity of Grigorchuk groups with application to cryptography
• The conjugacy problem in the Grigorchuk group is polynomial time decidable.

Cited in

(2)

• A STRUCTURAL PROPERTY CONCERNING ABSTRACT COMMENSURABILITY OF SUBGROUPS
• The power word problem in graph products

This page was built for publication: Linear time algorithm for the conjugacy problem in the first Grigorchuk group

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