Functions on groups and computational complexity

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)409-429
Number of pages21
JournalInternational Journal of Algebra and Computation
Volume14
Issue number4
DOIs
StatePublished - Aug 2004

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Combinatorial group theory
  • Complexity
  • Word problem

Fingerprint Dive into the research topics of 'Functions on groups and computational complexity'. Together they form a unique fingerprint.

Cite this