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