Efficient Computation in Groups Via Compression

DOI10.1007/978-3-540-74510-5_26MaRDI QIDQ3499779zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complexity boundscompressed word problemcontext-free grammarsfinitely generated groupsfree productsgraph groups

Mathematics Subject Classification ID

Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

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

Cited in

(20)

• Knapsack in graph groups
• Compression techniques in group theory
• The power word problem in graph products
• The complexity of compressed membership problems for finite automata
• Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P
• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P
• On secret sharing protocols
• Compressed membership in automata with compressed labels
• Compressed Word Problems in HNN-Extensions and Amalgamated Products
• Taming the hydra: the word problem and extreme integer compression
• 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
• Compressed decision problems in hyperbolic groups
• The power word problem
• 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
• Compressed word problems in HNN-extensions and amalgamated products
• The power word problem in graph products

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)