Compressed Word Problems in HNN-Extensions and Amalgamated Products

DOI10.1007/978-3-642-03351-3_23MaRDI QIDQ3392958zbMATH OpenOpenAlexFDO

Authors 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

amalgamated free productscompressed word problemHNN extensionspolynomial 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)

Recommendations

• Compressed word problems in HNN-extensions and amalgamated products
• scientific article; zbMATH DE number 7120879
• The Compressed Word Problem for Groups
• Efficient Computation in Groups Via Compression
• Compressed decision problems for graph products and applications to (outer) automorphism groups.

Cites work

• Compressed word problems in HNN-extensions and amalgamated products
• Efficient Computation in Groups Via Compression
• Embedding Theorems for Groups
• EMBEDDING THEOREMS FOR SEMIGROUPS
• Generic-case complexity, decision problems in group theory, and random walks.
• Group-based cryptography
• scientific article; zbMATH DE number 41228 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 1408351 (Why is no real title available?)
• scientific article; zbMATH DE number 3381557 (Why is no real title available?)
• Polynomial-time word problems.
• RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS
• Theories of HNN-Extensions and Amalgamated Products
• Word Problems and Membership Problems on Compressed Words

Cited in

(6)

• Efficient Computation in Groups Via Compression
• RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS
• Theories of HNN-Extensions and Amalgamated Products
• On powered one-relator HNN-extensions of groups
• Word Problems and Membership Problems on Compressed Words
• Compressed word problems in HNN-extensions and amalgamated products

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392958)