Compressed word problems in HNN-extensions and amalgamated products

DOI10.1007/s00224-010-9295-2zbMath1235.68106arXiv0811.3303OpenAlexW1971387267MaRDI 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 programsHNN-extensionsalgorithms for compressed stringsword problems for groups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (7)

Taming the hydra: The word problem and extreme integer compression ⋮ Closure properties of knapsack semilinear groups ⋮ 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 ⋮ Compressed Word Problems in HNN-Extensions and Amalgamated Products ⋮ Compression techniques in group theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Compressed word problems in HNN-extensions and amalgamated products