Polynomial-time word problems.

DOI10.4171/CMH/142MaRDI QIDQ951964zbMATH OpenOpenAlexFDO

Authors 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, http://www.ems-ph.org/journals/show_pdf.php?issn=0010-2571&vol=83&iss=4&rank=3

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)

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.

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.

Cited in

(30)

• SLP compression for solutions of equations with constraints in free and hyperbolic groups.
• Membership Problem for the Modular Group
• Compression techniques in group theory
• The primitivity index function for a free group, and untangling closed curves on hyperbolic surfaces.With the appendix by Khalid Bou–Rabee
• The word and geodesic problems in free solvable groups.
• Non-commutative lattice problems
• Compressed words and automorphisms in fully residually free groups.
• Cayley linear-time computable groups
• Taming the hydra: the word problem and extreme integer compression
• Logspace and compressed-word computations in nilpotent groups
• Compressed Word Problems in HNN-Extensions and Amalgamated Products
• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P.
• Compressed decision problems in hyperbolic groups
• Algorithmic theory of free solvable groups: randomized computations.
• The compressed word problem in relatively hyperbolic groups
• Cryptanalysis of a combinatorial public key cryptosystem
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• Polynomial braid combing
• The fully compressed subgroup membership problem
• scientific article; zbMATH DE number 5560346 (Why is no real title available?)
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• Some aspects of the SD-world
• The bounded and precise word problems for presentations of groups
• A presentation of a finitely generated submonoid of invertible endomorphisms of the free monoid
• Complexity of word problems for HNN-extensions
• Compressed word problems in HNN-extensions and amalgamated products
• Computing area in presentations of the trivial group
• On constructing possibly one-way functions based on the non-decidability of the endomorphism problem in groups
• Compressed membership in automata with compressed labels
• scientific article; zbMATH DE number 7559146 (Why is no real title available?)

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)