StraightLineProgramWord Class Reference

class StraightLineProgramWord. More...

#include <StraightLineProgramWord.h>

List of all members.

Classes

struct  Assertion
 Structure used in function equal() only. More...
struct  Production
 A production for a rule of a composition system. More...

Public Member Functions

 StraightLineProgramWord ()
 Default constructor.
 StraightLineProgramWord (int init, int gens)
 Create a composition system producing a 1-generator word 'init'.
template<class ConstMapIterator >
 StraightLineProgramWord (int init, ConstMapIterator B, ConstMapIterator E)
 Construct a composition system for a generator init acted on by a sequence of mappings.
StraightLineProgramWord & operator= (const StraightLineProgramWord &SLP)
 Assignement operator.
int operator[] (LongInteger i) const
 Index operator. Obtain a generator at the ith position in the word.
StraightLineProgramWord operator- () const
 Compute a composition system which produces the inverse of the current word.
StraightLineProgramWord operator* (const StraightLineProgramWord &SLP) const
 Compute an SLP which produces a product of words produced by *this and SLP (as semigroup elements).
bool equal (int n1, const StraightLineProgramWord &SLP, int n2) const
 Check if words produced by $n_1$ in *this and $n_2$ in SLP are the same (as elements of semigroup).
int terminalSegment (int n, LongInteger length)
 Add a vertex $n'$ into SLP (if required) which represents the word $w$ which the terminal segment of the word represented by $n$ of required length.
int initialSegment (int n, LongInteger length)
 Add a vertex $n'$ into SLP (if required) which represents the word $w$ which the initial segment of the word represented by $n$ of required length.
int truncateVertexLeft (int n, LongInteger length)
 Add a vertex $n'$ into SLP (if required) which represents the word $w_n$ truncated on the left.
int truncateVertexRight (int n, LongInteger length)
 Add a vertex $n'$ into SLP (if required) which represents the word $w_n$ truncated on the left.
LongInteger leftGCDLength (const StraightLineProgramWord &CS) const
 Compute the length of the longest common initial segment of 2 words given by SLPs (as elements of semigroup).
Word getWord () const
 Get a word represented (produced) by the SLP.
Word getWord (int N) const
 Get a word represented (produced) by (non-)terminal symbol.
LongInteger length () const
 Compute the length of the word produced by the SLP.
void reduce ()
 Reduce the SLP.
void simplify ()
 Simplify the structure of SLP.

Private Member Functions

void order_vertices (int n, list< int > &order, set< int > &closure) const
 Order the descendants of $n$.
void order_vertices (int n, list< int > &order) const
LongInteger length_rule (int n) const
 Compute the length of the word corresponding to a rule.
int height_rule (int n) const
 Compute the height of the rule.
bool assertionType (const Assertion &A, const StraightLineProgramWord &SLP) const
 Determine the type of the assertion.
void extendTerminals (int nt)
 Extend the set of non-terminals. The word produced by the result is the same as the original.
void reduce_rule (int n)
 Reduce a subgraph of the SLP reachable from the vertex n.
LongInteger leftGCDLength (int n1, const StraightLineProgramWord &CS, int n2) const
 Compute the length of the longest common initial segment of 2 words given by composition systems.
set< Assertion > splitAssertion (const Assertion &A, bool firstTerm, const StraightLineProgramWord &SLP) const
void update_lengths ()
 Update the lengths of all rules in the system.
void update_length (int n)
 Recursively update the length of the rule.
void update_heights ()
 Update the heights of all rules in the system.
void update_height (int n)
 Recursively update the height of the rule.
int getGenerator (int n, LongInteger pos) const
 Get a generator at ith position of the word $w_n$.
LongInteger cancellationLength (int n1, int n2) const
 Find the amount of cancellation in a product $w_{n_1} w_{n_2}$.
StraightLineProgramWord applyMapping (const Map &M) const
 For a composition system $C$ and a mapping $\alpha$ compute a composition system representing $w_C^\alpha$.
int max_rule_number () const
 Get the maximal number of the rule in SLP.

Static Private Member Functions

static void invertProductionPair (int &A, int &B)
 Function inverts a production pair (A,B).
static pair< map< int,
Production >, vector< int > > 		map_rules (const Map &M)
 Construct the composition system rules for the map M.

Private Attributes

int theRoot
 The number of the root non-terminal. Theroot==0 if the system is empty (default constructor).
int theTerminals
 The number of terminals in the system.
map< int, Production > theRules
 The production rules of the system.

Friends

ostream & operator<< (ostream &os, const StraightLineProgramWord &CS)

Detailed Description

class StraightLineProgramWord.

A straight line program is basically a program computing a single word. We used "Polynomial-time Word problems" by Saul Schleimer when implementing this class.

In this implementation the class StraightLineProgramWord serves 1 purpose - it is a special container class for words. In other words it is just another representation for words, used mainly to efficiently solve the Word problem for the automorphism group of a free group.

Notice that we do not reduce SLP when constructing, i.e., initially a word represented by SLP is not reduced and length() is not the same as the length of getWord(). You need to use reduce() for that.

Another thing to remember... I do not assume that for all rules $x_i \rightarrow x_j x_k$ $i > j,k$. Though it is assumed that $x_j \ne 1$. In a situation when $x_j=1,~ x_k=1$ $x_i$ must be removed from the system.

After all is done need to check that all those assumptions are really satisfied.

Definition at line 52 of file StraightLineProgramWord.h.

Constructor & Destructor Documentation

StraightLineProgramWord::StraightLineProgramWord (  )  [inline]

Default constructor.

Definition at line 140 of file StraightLineProgramWord.h.

StraightLineProgramWord::StraightLineProgramWord ( int  init,
int  gens 
)

Create a composition system producing a 1-generator word 'init'.

template<class ConstMapIterator >
StraightLineProgramWord::StraightLineProgramWord ( int  init,
ConstMapIterator  B,
ConstMapIterator  E 
) [inline]

Construct a composition system for a generator init acted on by a sequence of mappings.

Here if $M_1,\ldots,M_n$ is a sequence of mappings then the action of a sequence is a sequence of actions where $M_1$ is the first mapping to apply, and so on up to $M_n$.

Definition at line 154 of file StraightLineProgramWord.h.

References applyMapping(), theRoot, theRules, and theTerminals.

Member Function Documentation

StraightLineProgramWord StraightLineProgramWord::applyMapping ( const Map &  M  )  const [private]

For a composition system $C$ and a mapping $\alpha$ compute a composition system representing $w_C^\alpha$.

The result is computed in a very straightforward way. There is no check that $\alpha$ is applicable. In case when the domain alphabet of $\alpha$ is strictly smaller than the number of terminals the output is an empty composition sequence. In case when the domain alphabet of $\alpha$ is strictly greater than the number of terminals the result is a correct composition sequence.

Referenced by StraightLineProgramWord().

bool StraightLineProgramWord::assertionType ( const Assertion &  A,
const StraightLineProgramWord &  SLP 
) const [private]

Determine the type of the assertion.

The function determines the type of the assertion. The output==true if A is an overlap assertion. The output==false if A is an subword assertion.

LongInteger StraightLineProgramWord::cancellationLength ( int  n1,
int  n2 
) const [private]

Find the amount of cancellation in a product $w_{n_1} w_{n_2}$.

bool StraightLineProgramWord::equal ( int  n1,
const StraightLineProgramWord &  SLP,
int  n2 
) const

Check if words produced by $n_1$ in *this and $n_2$ in SLP are the same (as elements of semigroup).

void StraightLineProgramWord::extendTerminals ( int  nt  )  [private]

Extend the set of non-terminals. The word produced by the result is the same as the original.

int StraightLineProgramWord::getGenerator ( int  n,
LongInteger  pos 
) const [private]

Get a generator at ith position of the word $w_n$.

Referenced by operator[]().

Word StraightLineProgramWord::getWord ( int  N  )  const

Get a word represented (produced) by (non-)terminal symbol.

The current implementation is the most straightforward approach (not efficient). Notice that $N$ can be negative.

Word StraightLineProgramWord::getWord (  )  const [inline]

Get a word represented (produced) by the SLP.

Be careful!!! Relatively small SLPs can represent huge words.

Definition at line 244 of file StraightLineProgramWord.h.

References getWord(), and theRoot.

Referenced by getWord().

int StraightLineProgramWord::height_rule ( int  n  )  const [inline, private]

Compute the height of the rule.

Definition at line 303 of file StraightLineProgramWord.h.

References theRules, and theTerminals.

int StraightLineProgramWord::initialSegment ( int  n,
LongInteger  length 
) [inline]

Add a vertex $n'$ into SLP (if required) which represents the word $w$ which the initial segment of the word represented by $n$ of required length.

Definition at line 213 of file StraightLineProgramWord.h.

References length_rule(), and truncateVertexRight().

static void StraightLineProgramWord::invertProductionPair ( int &  A,
int &  B 
) [static, private]

Function inverts a production pair (A,B).

LongInteger StraightLineProgramWord::leftGCDLength ( int  n1,
const StraightLineProgramWord &  CS,
int  n2 
) const [private]

Compute the length of the longest common initial segment of 2 words given by composition systems.

LongInteger StraightLineProgramWord::leftGCDLength ( const StraightLineProgramWord &  CS  )  const [inline]

Compute the length of the longest common initial segment of 2 words given by SLPs (as elements of semigroup).

Definition at line 235 of file StraightLineProgramWord.h.

References theRoot.

LongInteger StraightLineProgramWord::length (  )  const [inline]

Compute the length of the word produced by the SLP.

Definition at line 256 of file StraightLineProgramWord.h.

References length_rule(), and theRoot.

LongInteger StraightLineProgramWord::length_rule ( int  n  )  const [inline, private]

Compute the length of the word corresponding to a rule.

Definition at line 293 of file StraightLineProgramWord.h.

References theRules, and theTerminals.

Referenced by initialSegment(), length(), and terminalSegment().

static pair< map< int , Production > , vector< int > > StraightLineProgramWord::map_rules ( const Map &  M  )  [static, private]

Construct the composition system rules for the map M.

Function prepares a block of rules for the given map. The range terminals have the lowest numbers $1,\ldots,t$. The domain non-terminals are given in the vector.

int StraightLineProgramWord::max_rule_number (  )  const [private]

Get the maximal number of the rule in SLP.

StraightLineProgramWord StraightLineProgramWord::operator* ( const StraightLineProgramWord &  SLP  )  const

Compute an SLP which produces a product of words produced by *this and SLP (as semigroup elements).

StraightLineProgramWord StraightLineProgramWord::operator- (  )  const

Compute a composition system which produces the inverse of the current word.

StraightLineProgramWord& StraightLineProgramWord::operator= ( const StraightLineProgramWord &  SLP  )  [inline]

Assignement operator.

Definition at line 173 of file StraightLineProgramWord.h.

References theRoot, theRules, and theTerminals.

int StraightLineProgramWord::operator[] ( LongInteger  i  )  const [inline]

Index operator. Obtain a generator at the ith position in the word.

Definition at line 181 of file StraightLineProgramWord.h.

References getGenerator(), and theRoot.

void StraightLineProgramWord::order_vertices ( int  n,
list< int > &  order 
) const [inline, private]

Definition at line 286 of file StraightLineProgramWord.h.

References order_vertices().

void StraightLineProgramWord::order_vertices ( int  n,
list< int > &  order,
set< int > &  closure 
) const [private]

Order the descendants of $n$.

Operation returns 2 structures: order - contains the ordered set of descendants and closure which contains the same vertices ordered as integers. It is assumed that order and closure are initially empty.

Referenced by order_vertices().

void StraightLineProgramWord::reduce (  )  [inline]

Reduce the SLP.

Definition at line 260 of file StraightLineProgramWord.h.

References reduce_rule(), and theRoot.

void StraightLineProgramWord::reduce_rule ( int  n  )  [private]

Reduce a subgraph of the SLP reachable from the vertex n.

Referenced by reduce().

void StraightLineProgramWord::simplify (  ) 

Simplify the structure of SLP.

Update vertices of out_degree 1 and remove all vertices that can not be reached from the root.

set< Assertion > StraightLineProgramWord::splitAssertion ( const Assertion &  A,
bool  firstTerm,
const StraightLineProgramWord &  SLP 
) const [private]
int StraightLineProgramWord::terminalSegment ( int  n,
LongInteger  length 
) [inline]

Add a vertex $n'$ into SLP (if required) which represents the word $w$ which the terminal segment of the word represented by $n$ of required length.

Definition at line 207 of file StraightLineProgramWord.h.

References length_rule(), and truncateVertexLeft().

int StraightLineProgramWord::truncateVertexLeft ( int  n,
LongInteger  length 
)

Add a vertex $n'$ into SLP (if required) which represents the word $w_n$ truncated on the left.

If $w_n = u \circ v$, $length = |u|$, and $t$ is the output of this function then $w_t = v$. The vertex $n$ can be negative. Foolproof.

Referenced by terminalSegment().

int StraightLineProgramWord::truncateVertexRight ( int  n,
LongInteger  length 
)

Add a vertex $n'$ into SLP (if required) which represents the word $w_n$ truncated on the left.

If $w_n = u \circ v$, $length = |v|$, and $t$ is the output of this function then $w_t = u$. The vertex $n$ can be negative. Foolproof.

Referenced by initialSegment().

void StraightLineProgramWord::update_height ( int  n  )  [private]

Recursively update the height of the rule.

void StraightLineProgramWord::update_heights (  )  [private]

Update the heights of all rules in the system.

void StraightLineProgramWord::update_length ( int  n  )  [private]

Recursively update the length of the rule.

void StraightLineProgramWord::update_lengths (  )  [private]

Update the lengths of all rules in the system.

Friends And Related Function Documentation

ostream& operator<< ( ostream &  os,
const StraightLineProgramWord &  CS 
) [friend]

Member Data Documentation

int StraightLineProgramWord::theRoot [private]

The number of the root non-terminal. Theroot==0 if the system is empty (default constructor).

The root is always non-negative!!!

Definition at line 407 of file StraightLineProgramWord.h.

Referenced by getWord(), leftGCDLength(), length(), operator=(), operator[](), reduce(), and StraightLineProgramWord().

map< int , Production > StraightLineProgramWord::theRules [private]

The production rules of the system.

Definition at line 415 of file StraightLineProgramWord.h.

Referenced by height_rule(), length_rule(), operator=(), and StraightLineProgramWord().

int StraightLineProgramWord::theTerminals [private]

The number of terminals in the system.

Definition at line 411 of file StraightLineProgramWord.h.

Referenced by height_rule(), length_rule(), operator=(), and StraightLineProgramWord().

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Generated on Mon Sep 26 18:43:50 2011 for CRyptography And Groups (CRAG) by  doxygen 1.6.1