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)

• 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.
• Non-commutative lattice problems
• Logspace and compressed-word computations in nilpotent groups
• Polynomial braid combing
• 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
• Cayley linear-time computable groups
• Compressed membership in automata with compressed labels
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• Compressed decision problems in hyperbolic groups
• The compressed word problem in relatively hyperbolic groups
• Complexity of word problems for HNN-extensions
• SLP compression for solutions of equations with constraints in free and 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
• The bounded and precise word problems for presentations of groups
• scientific article; zbMATH DE number 7559146 (Why is no real title available?)
• Compressed Word Problems in HNN-Extensions and Amalgamated Products
• scientific article; zbMATH DE number 5560346 (Why is no real title available?)
• 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)