FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY

DOI10.1142/S0218196704001815zbMATH Open1063.20034arXivmath/0202124OpenAlexW1978480097MaRDI QIDQ4824696FDOQ4824696

Authors: J.-C. Birget 

Publication date: 1 November 2004

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0202124

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Isodiametric and Isoperimetric Inequalities for Complexes and Groups
• Symmetric space-bounded computation
• THE DOUBLE EXPONENTIAL THEOREM FOR ISODIAMETRIC AND ISOPERIMETRIC FUNCTIONS
• 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
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
• The complexity of Grigorchuk groups with application to cryptography
• Subrekursive Komplexität bei Gruppen. II: Der Einbettungssatz von Higman für entscheidbare Gruppen
• The Nielsen reduction and P-complete problems in free groups
• On the complexity of intersection and conjugacy problems in free groups
• ISODIAMETRIC AND ISOPERIMETRIC INEQUALITIES FOR GROUP PRESENTATIONS
• The word problem for geometrically finite groups

Cited In (9)

• 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
• Title not available (Why is that?)

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)