FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY

DOI10.1142/S0218196704001815MaRDI QIDQ4824696zbMATH OpenOpenAlexFDO

Authors J.-C. 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

combinatorial group theorycomputational complexitycontext-free languagesfilling length functionsfinitely presented groupsisodiametric functionsisoperimetric functionsword problem

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Geometric group theory (20F65) Analysis of algorithms and problem complexity (68Q25)

Abstract: We give some connections between various functions defined on finitely presented groups (isoperimetric, isodiametric, Todd-Coxeter radius, filling length functions, etc.), and we study the relation between those functions and the computational complexity of the word problem (deterministic time, nondeterministic time, symmetric space). We show that the isoperimetric function can always be linearly decreased (unless it is the identity map). We present a new proof of the Double Exponential Inequality, based on context-free languages.

Recommendations

• Isoperimetric and isodiametric functions of groups
• The geometry of the word problem for finitely generated groups.
• Space functions of groups.
• On Dehn functions of infinite presentations of groups.
• Isoperimetric functions of groups and computational complexity of the word problem

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• Isodiametric and Isoperimetric Inequalities for Complexes and Groups
• ISODIAMETRIC AND ISOPERIMETRIC INEQUALITIES FOR GROUP PRESENTATIONS
• On the complexity of intersection and conjugacy problems in free groups
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
• Subrekursive Komplexität bei Gruppen. II: Der Einbettungssatz von Higman für entscheidbare Gruppen
• Symmetric space-bounded computation
• The complexity of Grigorchuk groups with application to cryptography
• THE DOUBLE EXPONENTIAL THEOREM FOR ISODIAMETRIC AND ISOPERIMETRIC FUNCTIONS
• The Nielsen reduction and P-complete problems in free groups
• The word problem for geometrically finite groups
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem

Cited in

(9)

• Space functions of groups.
• Asymptotic invariants, complexity of groups and related problems.
• Space functions and space complexity of the word problem in semigroups.
• scientific article; zbMATH DE number 67432 (Why is no real title available?)
• THE GALLERY LENGTH FILLING FUNCTION AND A GEOMETRIC INEQUALITY FOR FILLING LENGTH
• SOME DUALITY CONJECTURES FOR FINITE GRAPHS AND THEIR GROUP THEORETIC CONSEQUENCES
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• Homological and homotopical higher-order filling functions.
• The geometry of the word problem for finitely generated groups.

This page was built for publication: FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4824696)