Compressed Word Problems in HNN-Extensions and Amalgamated Products

DOI10.1007/978-3-642-03351-3_23zbMath1190.20018OpenAlexW1842686199MaRDI QIDQ3392958

Niko Haubold, Markus Lohrey

Publication date: 18 August 2009

Published in: Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_23

zbMATH Keywords

HNN extensionsamalgamated free productscompressed word problempolynomial time Turing-reducible problems

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compressed word problems in HNN-extensions and amalgamated products
• Group-based cryptography
• Polynomial-time word problems.
• Generic-case complexity, decision problems in group theory, and random walks.
• Efficient Computation in Groups Via Compression
• RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS
• Theories of HNN-Extensions and Amalgamated Products
• Word Problems and Membership Problems on Compressed Words
• EMBEDDING THEOREMS FOR SEMIGROUPS
• Embedding Theorems for Groups

This page was built for publication: Compressed Word Problems in HNN-Extensions and Amalgamated Products