Space functions of groups

Details Space functions of groups Space functions of groups

2010-10-31

arxiv.org/abs/1011.0118v3

Mathematics

Group Theory

The paper has been replaced by the new version in which some typos are corrected and references are added

Scientific paper

We consider space functions $s(n)$ of finitely presented groups $G =< A\mid R> .$ (These functions have a natural geometric analog.) To define $s(n)$ we start with a word $w$ over $A$ of length at most $n$ equal to 1 in $G$ and use relations from $R$ for elementary transformations to obtain the empty word; $s(n)$ bounds from above the tape space (or computer memory) one needs to transform any word of length at most $n$ vanishing in $G$ to the empty word. One of the main obtained results is the following criterion: A finitely generated group $H$ has decidable word problem of polynomial space complexity if and only if $H$ is a subgroup of a finitely presented group $G$ with a polynomial space function.

Affiliated with

Also associated with

No associations

Rating

Space functions of groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Space functions of groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space functions of groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-663247