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

computational complexitycontext-free languagesword problemfinitely presented groupsisoperimetric functionscombinatorial group theoryisodiametric 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)

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 GROUP PRESENTATIONS
• Isodiametric and Isoperimetric Inequalities for Complexes and 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
• 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 DOUBLE EXPONENTIAL THEOREM FOR ISODIAMETRIC AND ISOPERIMETRIC FUNCTIONS
• The Nielsen reduction and P-complete problems in free groups
• The complexity of Grigorchuk groups with application to cryptography
• The word problem for geometrically finite groups
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem

Cited in

(9)

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

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)