Charles V. Schaefer, Jr. School of Engineering and Science
 
 
SES Home » Science Departments » Algebraic Cryptography Center » Software

Software

The CRAG Software Library FAQ

// Copyright (C) 2006 Alexander Ushakov
// Contents: Example for Subgroups of Free Groups.
//
// Principal Authors: Alexander Ushakov
//
// Revision History:
//


#include "Word.h"
#include "SubgroupFG.h"


int main( )
{
  int N = 5;
  int K = 6;
  int L = 7;

  // Create a random vector of K freely reduced words each of length L over the alphabet {x_1,...,x_N}
  vector< Word > generators;
  for( int i=0 ; i
// How do I create a subgroup of a free group?
  SubgroupFG sbgp( N , generators );


 
// How do I oupput a subgroup of a free group?
  cout << "SBGP = " << endl << sbgp << endl;
  

 
// How do I check whether two subgroups coincide?
  // Create another random subgroup with the same parameters
  vector< Word > generators2;
  for( int i=0 ; i
// How do I find intersection of two subgroups?
  SubgroupFG sbgp3 = sbgp*sbgp2;
  

 
// How do I find a set of Nielsen Generators for a subgroup?
  vector< Word > niels_gens = sbgp.getNielsenGenerators( );

  
 
// How do I get a FSA corresponing to a subgroup?
  IntLabeledGraph FSA = sbgp.getFSA( );

  
 
// How do I check whether a word belongs to a subgroup?
  Word w = Word::randomWord( N , 15 );        // generate random word
  if( sbgp.doesBelong( w ) ) {                // check if it belongs to a subgroup
    cout << "A word belongs to a subgroup" << endl;
  } else {
    cout << "A word does not belong to a subgroup" << endl;
  }

 
// If a word belongs to a subgroup how do I find actual product of initial generators giving the word?
  if( sbgp.doesBelong( w ) ) {
    Word decomposition = sbgp.express( w );
    // output the decomposition
    Word::const_iterator w_it=decomposition.begin( );
    for( int c=0 ; w_it!=decomposition.end( ) ; ++w_it, ++c )
      cout << ( c>0 ? "  *  " : "" ) << ( *w_it>0 ? generators[*w_it-1] : -generators[-*w_it-1] );
    cout << endl;
  }


 
// How do I compute the index of a subgroup in a free group?
  int index = sbgp.getIndex( );


 
// How do I compute the rank of a subgroup?
  int rank = sbgp.getRank( );




  return 0;
}