FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY

DOI10.1142/S0218196704001815zbMath1063.20034arXivmath/0202124OpenAlexW1978480097MaRDI QIDQ4824696

Jean-Camille Birget

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

zbMATH Keywords

computational complexityword problemfinitely presented groupscontext-free languagescombinatorial group theoryisoperimetric functionsisodiametric functionsfilling length functions

Mathematics Subject Classification ID

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)

Space functions and space complexity of the word problem in semigroups. ⋮ CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS ⋮ Space functions of groups ⋮ Asymptotic invariants, complexity of groups and related problems

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