Cyclic rewriting and conjugacy problems.

DOI10.1515/GCC-2012-0020zbMATH Open1286.20035arXiv1206.4431OpenAlexW2166341929MaRDI QIDQ2874367FDOQ2874367

Alexei Myasnikov, Volker Diekert, Andrew Duncan

Publication date: 30 January 2014

Published in: Groups, Complexity, Cryptology (Search for Journal in Brave)

Abstract: 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 pregroups 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.

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

Recommendations

• The Knuth-Bendix algorithm and the conjugacy problem in monoids.
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• A completion procedure for finitely presented groups that is based on word cycles
• Geodesic rewriting systems and pregroups
• On the Conjugacy Problem for Cyclic Extensions of Free Groups

zbMATH Keywords

algorithmsconjugacy classesconjugacy problemHNN-extensionsrewriting systemsfree products with amalgamationalgorithmic group theoryStallings pregroups

Mathematics Subject Classification ID

Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Conjugacy classes for groups (20E45) Grammars and rewriting systems (68Q42) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cited In (8)

• Some applications of prefix-rewriting in monoids, groups, and rings
• Title not available (Why is that?)
• The Knuth-Bendix algorithm and the conjugacy problem in monoids.
• Confluence of algebraic rewriting systems
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem.
• Title not available (Why is that?)
• Term rewriting for the conjugacy problem and the braid groups

This page was built for publication: Cyclic rewriting and conjugacy problems.

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