Polynomial-time word problems.
automorphisms of free groupscompressionefficient algorithmsfree-by-cyclic groupsstraight-line programsword problem
Free nonabelian groups (20E05) Automorphisms of infinite groups (20E36) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Other groups related to topology or analysis (20F38) Topological methods in group theory (57M07) Analysis of algorithms and problem complexity (68Q25)
The author observes that automorphisms of the free group strongly resemble straight-line programs, which are widely studied in the theory of compressed data structures in computer science. A crucial result by M. Lohrey is used that the word problem for compressed words in the free group is solvable in polynomial time. This theorem is applied to 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 handlebody subgroup of the mapping class group. The paper is self-contained. A detailed exposition of the necessary results from computer science including Plandowski theorem is given.
- 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.
- Cryptanalysis of a combinatorial public key cryptosystem
- Cayley polynomial-time computable groups
- Compression techniques in group theory
- The compressed word problem in relatively hyperbolic groups
- Non-commutative lattice problems
- Compressed membership in automata with compressed labels
- Compressed Word Problems in HNN-Extensions and Amalgamated Products
- Compressed words and automorphisms in fully residually free groups.
- scientific article; zbMATH DE number 5560346 (Why is no real title available?)
- Algorithmic theory of free solvable groups: randomized computations.
- Taming the hydra: the word problem and extreme integer compression
- Computing area in presentations of the trivial group
- 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 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.
- The word and geodesic problems in free solvable groups.
- Compressed decision problems in hyperbolic groups
- Logspace and compressed-word computations in nilpotent groups
- A presentation of a finitely generated submonoid of invertible endomorphisms of the free monoid
- On constructing possibly one-way functions based on the non-decidability of the endomorphism problem in groups
- Some aspects of the SD-world
- SLP compression for solutions of equations with constraints in free and hyperbolic groups.
- Membership Problem for the Modular Group
- Complexity of word problems for HNN-extensions
- The fully compressed subgroup membership problem
- Algorithms for contractibility of compressed curves on 3-manifold boundaries
- The bounded and precise word problems for presentations of groups
- Compressed word problems in HNN-extensions and amalgamated products
- Cayley linear-time computable groups
- Compressed decision problems in hyperbolic groups
- Directed regular and context-free languages
- Algorithms for contractibility of compressed curves on 3-manifold boundaries
- Some fast algorithms for curves in surfaces
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)
