# TheGrigorchukGroupAlgorithms Class Reference

Static class TheGrigorchukGroupAlgorithms encapsulates algorithms for the original Grigorchuk group. More...

#include <TheGrigorchukGroupAlgorithms.h>

List of all members.

## Public Member Functions

TheGrigorchukGroupAlgorithms ()
Default constructor is not instantiated to protect from creating the obects of this class.

## Static Public Member Functions

static bool trivial (const Word &w)
Solve the Identity Problem for a non-reduced word.
static bool trivial_reduced (const Word &w)
Solve the Identity Problem for a reduced word.
static triple< int, int, int > abelianImage (const Word &w)
Compute the abelian image of an element.
static Word reduce (const Word &w)
Reduce a word.
static int findOrder (const Word &w)
Find the order of an element.
static bool conjugate (const Word &w1, const Word &w2)
Determine if 2 words represent conjugate elements of the Grigorchuk group.
static set< int > conjugate_Kcosets (const Word &w1, const Word &w2)
Compute the -set for a pair of words.
static set< WordfindConjugator_Kcosets (const Word &w1, const Word &w2)
Determine if 2 words represent conjugate elements of the Grigorchuk group and find the actual conjugators, one for each K-coset.
static pair< Word, Wordsplit (const Word &w)
Split an element of .
static void push_back (Word &w, int g)
Multiply an element by a generator on the right and perform a reduction if possible.
static void push_front (Word &w, int g)
Multiply an element by a generator on the left and perform a reduction if possible.
static Word randomWord (int len)
Generate a random reduced word.
static pair< Word, list< Word > > decompositionBSbgp (const Word &w)
Compute the decomposition of a word as an element of a subgroup .
static pair< Word, WordliftToSTone (const Word &w1, const Word &w2)
Compute the preimage of along .
static int cosetRepresentativeKSbgp (const Word &w)
Find a number of a right K-coset where .
static Word cosetRepresentativeKSbgp (int c)
Get a word representative of a right K-coset with number c.
static int liftPairKcosetsUP (int x, int y)
Lift the pair of right K-cosets to if possible.
static set< int > liftPairsKcosetsUP (const set< int > &K1, const set< int > &K2)
For two sets of K-cosets find all K-lifts.
static map< pair< int, int >, int > KCosetLiftTable ()
For each pair of K-cosets that can be lifted up to it associates such a lift.

## Detailed Description

Static class TheGrigorchukGroupAlgorithms encapsulates algorithms for the original Grigorchuk group.

The class TheGrigorchukGroupAlgorithms is static, i.e., all member functions are static and there is no constructor defined. For introduction to the original Grigorchuk group see P. de la Harpe "Topics in Geometric Group Theory". For more on algorithmic properties see survey by R. Grigorchuk "Solved and Unsolved Problems Around One Group".

Definition at line 36 of file TheGrigorchukGroupAlgorithms.h.

## Constructor & Destructor Documentation

 TheGrigorchukGroupAlgorithms::TheGrigorchukGroupAlgorithms ( )

Default constructor is not instantiated to protect from creating the obects of this class.

## Member Function Documentation

 static triple< int , int , int > TheGrigorchukGroupAlgorithms::abelianImage ( const Word & w )  [static]

Compute the abelian image of an element.

 static bool TheGrigorchukGroupAlgorithms::conjugate ( const Word & w1, const Word & w2 )  [inline, static]

Determine if 2 words represent conjugate elements of the Grigorchuk group.

Definition at line 103 of file TheGrigorchukGroupAlgorithms.h.

References conjugate_Kcosets().

 static set< int > TheGrigorchukGroupAlgorithms::conjugate_Kcosets ( const Word & w1, const Word & w2 )  [static]

Compute the -set for a pair of words.

Referenced by conjugate().

 static Word TheGrigorchukGroupAlgorithms::cosetRepresentativeKSbgp ( int c )  [static]

Get a word representative of a right K-coset with number c.

 static int TheGrigorchukGroupAlgorithms::cosetRepresentativeKSbgp ( const Word & w )  [static]

Find a number of a right K-coset where .

 static pair< Word , list< Word > > TheGrigorchukGroupAlgorithms::decompositionBSbgp ( const Word & w )  [static]

Compute the decomposition of a word as an element of a subgroup .

The function returns a pair where is a right coset for and is a sequence of conjugators for comprising the decomposition for . The equality holds.

 static set< Word > TheGrigorchukGroupAlgorithms::findConjugator_Kcosets ( const Word & w1, const Word & w2 )  [static]

Determine if 2 words represent conjugate elements of the Grigorchuk group and find the actual conjugators, one for each K-coset.

 static int TheGrigorchukGroupAlgorithms::findOrder ( const Word & w )  [static]

Find the order of an element.

Compute the smallest positive number such that is trivial in the Grigorchuk group.

 static map< pair< int , int > , int > TheGrigorchukGroupAlgorithms::KCosetLiftTable ( )  [static]

For each pair of K-cosets that can be lifted up to it associates such a lift.

 static int TheGrigorchukGroupAlgorithms::liftPairKcosetsUP ( int x, int y )  [static]

Lift the pair of right K-cosets to if possible.

If then knowing cosets and it is possible to find a coset . This operation is defined not for all pairs .

 static set< int > TheGrigorchukGroupAlgorithms::liftPairsKcosetsUP ( const set< int > & K1, const set< int > & K2 )  [static]

For two sets of K-cosets find all K-lifts.

Function uses liftPairKcosetsUP() for each pair of cosets.

 static pair< Word , Word > TheGrigorchukGroupAlgorithms::liftToSTone ( const Word & w1, const Word & w2 )  [static]

Compute the preimage of along .

. The function returns a pair , where is such that and is a preimage of .

 static void TheGrigorchukGroupAlgorithms::push_back ( Word & w, int g )  [static]

Multiply an element by a generator on the right and perform a reduction if possible.

 static void TheGrigorchukGroupAlgorithms::push_front ( Word & w, int g )  [static]

Multiply an element by a generator on the left and perform a reduction if possible.

 static Word TheGrigorchukGroupAlgorithms::randomWord ( int len )  [static]

Generate a random reduced word.

 static Word TheGrigorchukGroupAlgorithms::reduce ( const Word & w )  [static]

Reduce a word.

See VIII.B(12) of de la Harpe.

 static pair< Word , Word > TheGrigorchukGroupAlgorithms::split ( const Word & w )  [static]

Split an element of .

Make sure ! The output is a pair of words , acts on the left subtree, and acts on the right subtree.

 static bool TheGrigorchukGroupAlgorithms::trivial ( const Word & w )  [static]

Solve the Identity Problem for a non-reduced word.

Check if a word over the original alphabet represents the identity. See VIII.E(47) of de la Harpe.

 static bool TheGrigorchukGroupAlgorithms::trivial_reduced ( const Word & w )  [static]

Solve the Identity Problem for a reduced word.

Check if a word over the original alphabet represents the identity. See VIII.E(47) of de la Harpe.

The documentation for this class was generated from the following file:

Generated on Mon Sep 26 18:43:51 2011 for CRyptography And Groups (CRAG) by  1.6.1