Polynomial-time word problems.

DOI10.4171/CMH/142zbMath1172.20028arXivmath/0608563OpenAlexW2076505256MaRDI QIDQ951964

Saul Schleimer

Publication date: 5 November 2008

Published in: Commentarii Mathematici Helvetici (Search for Journal in Brave)

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

zbMATH Keywords

word problemcompressionstraight-line programsefficient algorithmsfree-by-cyclic groupsautomorphisms of free groups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Topological methods in group theory (57M07) Automorphisms of infinite groups (20E36) Other groups related to topology or analysis (20F38) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (20)

Non-commutative lattice problems ⋮ Taming the hydra: The word problem and extreme integer compression ⋮ Cryptanalysis of a combinatorial public key cryptosystem ⋮ Logspace and compressed-word computations in nilpotent groups ⋮ The fully compressed subgroup membership problem ⋮ Algorithms for contractibility of compressed curves on 3-manifold boundaries ⋮ Compressed word problems in HNN-extensions and amalgamated products ⋮ The primitivity index function for a free group, and untangling closed curves on hyperbolic surfaces.With the appendix by Khalid Bou–Rabee ⋮ Polynomial braid combing ⋮ Compressed Membership in Automata with Compressed Labels ⋮ COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS ⋮ EFFICIENT ALGORITHMS FOR HIGHLY COMPRESSED DATA: THE WORD PROBLEM IN HIGMAN'S GROUP IS IN P ⋮ A presentation of a finitely generated submonoid of invertible endomorphisms of the free monoid ⋮ Unnamed Item ⋮ Complexity of word problems for HNN-extensions ⋮ Compressed Word Problems in HNN-Extensions and Amalgamated Products ⋮ Some aspects of the SD-world ⋮ SLP compression for solutions of equations with constraints in free and hyperbolic groups ⋮ Unnamed Item ⋮ Compression techniques in group theory

This page was built for publication: Polynomial-time word problems.