Efficient Computation in Groups Via Compression

DOI10.1007/978-3-540-74510-5_26zbMath1188.20027OpenAlexW1556583142MaRDI QIDQ3499779

Saul Schleimer, Markus Lohrey

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 groupsfree productscontext-free grammarscomplexity boundsgraph groupscompressed word problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) 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)

Related Items (13)

Taming the hydra: The word problem and extreme integer compression ⋮ The power word problem in graph products ⋮ Logspace and compressed-word computations in nilpotent groups ⋮ Knapsack in graph groups ⋮ Compressed word problems in HNN-extensions and amalgamated products ⋮ On secret sharing protocols ⋮ AUTOMORPHISMS OF PARTIALLY COMMUTATIVE GROUPS II: COMBINATORIAL SUBGROUPS ⋮ Compressed Membership in Automata with Compressed Labels ⋮ The complexity of compressed membership problems for finite automata ⋮ Unnamed Item ⋮ Compressed Word Problems in HNN-Extensions and Amalgamated Products ⋮ Unnamed Item ⋮ Compression techniques in group theory

This page was built for publication: Efficient Computation in Groups Via Compression