Compressed word problems in HNN-extensions and amalgamated products

DOI10.1007/s00224-010-9295-2zbMath1235.68106arXiv0811.3303MaRDI QIDQ639849

Markus Lohrey, Niko Haubold

Publication date: 11 October 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0811.3303

zbMATH Keywords

straight-line programs; HNN-extensions; algorithms for compressed strings; word problems for groups

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q70: Algebraic theory of languages and automata

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

Related Items

Taming the hydra: The word problem and extreme integer compression, COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS, Complexity of word problems for HNN-extensions, Complexity of word problems for HNN-extensions, Compression techniques in group theory, Closure properties of knapsack semilinear groups, Compressed Word Problems in HNN-Extensions and Amalgamated Products

Cites Work

• Group-based cryptography
• Polynomial-time word problems.
• Generic-case complexity, decision problems in group theory, and random walks.
• On the algorithmic insolvability of the word problem in group theory
• Efficient Computation in Groups Via Compression
• RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS
• Processing Compressed Texts: A Tractability Border
• COMPRESSED WORDS AND AUTOMORPHISMS IN FULLY RESIDUALLY FREE GROUPS
• Theories of HNN-Extensions and Amalgamated Products
• Word Problems and Membership Problems on Compressed Words
• EMBEDDING THEOREMS FOR SEMIGROUPS
• Embedding Theorems for Groups
• The word problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item