Cyclic rewriting and conjugacy problems.

DOI10.1515/GCC-2012-0020MaRDI QIDQ2874367zbMATH OpenOpenAlexFDO

Authors Volker Diekert, Andrew Duncan, Alexei Myasnikov

Publication date 30 January 2014

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

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

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)

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.

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

Cited in

(9)

• Some applications of prefix-rewriting in monoids, groups, and rings
• String rewriting for double coset systems.
• scientific article; zbMATH DE number 4042147 (Why is no real title available?)
• 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
• A uniform model for almost convexity and rewriting systems
• scientific article; zbMATH DE number 5560346 (Why is no real title available?)
• 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)