Compressed word problems in HNN-extensions and amalgamated products
From MaRDI portal
Publication:639849
DOI10.1007/s00224-010-9295-2zbMath1235.68106arXiv0811.3303OpenAlexW1971387267MaRDI QIDQ639849
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
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