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

finitely generated groupscontext-free grammarsfree productscomplexity boundsgraph groupscompressed word problem

Mathematics Subject Classification ID

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)

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

(19)

• Compression techniques in group theory
• The power word problem in graph products
• 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.
• 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
• Knapsack in graph groups
• The isomorphism problem for finite extensions of free groups is in PSPACE
• 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
• Compressed word problems in HNN-extensions and amalgamated products
• Automorphisms of partially commutative groups. II: Combinatorial subgroups.
• 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 7561687 (Why is no real title available?)

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)