Efficient Computation in Groups Via Compression
DOI10.1007/978-3-540-74510-5_26zbMATH Open1188.20027OpenAlexW1556583142MaRDI QIDQ3499779FDOQ3499779
Authors: Markus Lohrey, Saul Schleimer 
Publication date: 3 June 2008
Published in: Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-74510-5_26
Recommendations
- The Compressed Word Problem for Groups
- Compressed decision problems for graph products and applications to (outer) automorphism groups.
- Compressed word problems in HNN-extensions and amalgamated products
- Compressed Conjugacy and the Word Problem for Outer Automorphism Groups of Graph Groups
- Compressed Word Problems in HNN-Extensions and Amalgamated Products
finitely generated groupscontext-free grammarsfree productscomplexity boundsgraph groupscompressed word problem
Analysis of algorithms and problem complexity (68Q25) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Grammars and rewriting systems (68Q42) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Cited In (19)
- Automorphisms of partially commutative groups. II: Combinatorial subgroups.
- 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 isomorphism problem for finite extensions of free groups is in PSPACE
- Logspace and compressed-word computations in nilpotent groups
- On constructing possibly one-way functions based on the non-decidability of the endomorphism problem in groups
- Knapsack in graph groups
- Compressed membership in automata with compressed labels
- Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
- The power word problem in graph products
- On secret sharing protocols
- The complexity of compressed membership problems for finite automata
- The power word problem in graph products
- Compression techniques in group theory
- Compressed word problems in HNN-extensions and amalgamated products
- Title not available (Why is that?)
- 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
- Taming the hydra: the word problem and extreme integer compression
This page was built for publication: Efficient Computation in Groups Via Compression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499779)
