2002/02/13 by Jean-Camille Birget, Birget, Jean-Camille
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Geometric and Algebraic Topology #math.GR #msc:20F10 #msc:68Q15 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0202124
arxiv created 2002/02/13 · arxiv updated 2009/11/30
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.