FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY
DOI10.1142/S0218196704001815zbMath1063.20034arXivmath/0202124OpenAlexW1978480097MaRDI QIDQ4824696
Publication date: 1 November 2004
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0202124
computational complexityword problemfinitely presented groupscontext-free languagescombinatorial group theoryisoperimetric functionsisodiametric functionsfilling length functions
Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Related Items (4)
Cites Work
- Unnamed Item
- Unnamed Item
- The Nielsen reduction and P-complete problems in free groups
- On the complexity of intersection and conjugacy problems in free groups
- Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
- The word problem for geometrically finite groups
- Symmetric space-bounded computation
- The complexity of Grigorchuk groups with application to cryptography
- Subrekursive Komplexität bei Gruppen. II: Der Einbettungssatz von Higman für entscheidbare Gruppen
- THE DOUBLE EXPONENTIAL THEOREM FOR ISODIAMETRIC AND ISOPERIMETRIC FUNCTIONS
- ISODIAMETRIC AND ISOPERIMETRIC INEQUALITIES FOR GROUP PRESENTATIONS
- Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
- Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
- Isodiametric and Isoperimetric Inequalities for Complexes and Groups
This page was built for publication: FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY