Polynomial-time word problems.

DOI10.4171/CMH/142zbMATH Open1172.20028arXivmath/0608563OpenAlexW2076505256MaRDI QIDQ951964FDOQ951964

Authors: Saul Schleimer 

Publication date: 5 November 2008

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

Abstract: We find polynomial-time solutions to the word problem for free-by-cyclic groups, the word problem for automorphism groups of free groups, and the membership problem for the handlebody subgroup of the mapping class group. All of these results follow from observing that automorphisms of the free group strongly resemble straight line programs, which are widely studied in the theory of compressed data structures. In an effort to be self-contained we give a detailed exposition of the necessary results from computer science.

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

Recommendations

• Compressed words and automorphisms in fully residually free groups.
• The Nielsen reduction and P-complete problems in free groups
• The Compressed Word Problem for Groups
• Compressed Conjugacy and the Word Problem for Outer Automorphism Groups of Graph Groups
• Compressed decision problems for graph products and applications to (outer) automorphism groups.

zbMATH Keywords

compressionword problemefficient algorithmsautomorphisms of free groupsfree-by-cyclic groupsstraight-line programs

Mathematics Subject Classification ID

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

Cited In (28)

• Algorithmic theory of free solvable groups: randomized computations.
• The primitivity index function for a free group, and untangling closed curves on hyperbolic surfaces.With the appendix by Khalid Bou–Rabee
• 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.
• Logspace and compressed-word computations in nilpotent groups
• Polynomial braid combing
• Non-commutative lattice problems
• On constructing possibly one-way functions based on the non-decidability of the endomorphism problem in groups
• The fully compressed subgroup membership problem
• Some aspects of the SD-world
• Compressed membership in automata with compressed labels
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• Compressed decision problems in hyperbolic groups
• Complexity of word problems for HNN-extensions
• SLP compression for solutions of equations with constraints in free and hyperbolic groups.
• The compressed word problem in relatively hyperbolic groups
• The word and geodesic problems in free solvable groups.
• Compression techniques in group theory
• Cryptanalysis of a combinatorial public key cryptosystem
• Compressed word problems in HNN-extensions and amalgamated products
• Title not available (Why is that?)
• Compressed Word Problems in HNN-Extensions and Amalgamated Products
• Title not available (Why is that?)
• A presentation of a finitely generated submonoid of invertible endomorphisms of the free monoid
• Membership Problem for the Modular Group
• Compressed words and automorphisms in fully residually free groups.
• Taming the hydra: the word problem and extreme integer compression
• Computing area in presentations of the trivial group

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

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