Cyclic rewriting and conjugacy problems

作     者：Diekert, Volker Duncan, Andrew Myasnikov, Alexei G. 

作者机构：Univ Stuttgart Univ Str 38 D-70569 Stuttgart Germany Newcastle Univ Newcastle Upon Tyne NE1 7RU Tyne & Wear England Stevens Inst Technol Hoboken NJ 07030 USA 

出 版 物：《GROUPS COMPLEXITY CRYPTOLOGY》 (Group Complexity Cryptology)

年 卷 期：2012年第4卷第2期

页      面：321-355页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：EPSRC [EP/F01495/1] EPSRC [EP/F014945/1] Funding Source: UKRI Division Of Mathematical Sciences Direct For Mathematical & Physical Scien Funding Source: National Science Foundation 

主　　题：Algorithmic group theory rewriting system conjugacy problem HNN-extension free product with amalgamation Stallings pregroup 

摘      要：Cyclic words are equivalence classes of cyclic permutations of ordinary words. When a group is given by a rewriting relation, a rewriting system on cyclic words is induced, which is used to construct algorithms to find minimal length elements of conjugacy classes in the group. These techniques are applied to the universal groups of Stallings pre-groups and in particular to free products with amalgamation, HNN- extensions and virtually free groups, to yield simple and intuitive algorithms and proofs of conjugacy criteria.