PC Namespace Reference


class  Node
class  Marking
class  PowerCircuit
class  PowerCircuitCompMatrix
class  PowerCircuitGraph
struct  Row
struct  Col
class  SignMatrix


typedef char Sign


void addSigns (const Sign &op1, const Sign &op2, Sign &result, Sign &carry)
int compareSigns (const Sign &op1, const Sign &op2)
int signToInt (const Sign &s)
Sign negateSign (const Sign &s)
std::string signToString (const Sign &s)


const Sign ZERO = 0
const Sign PLUS = 1
const Sign MINUS = 2

Detailed Description

This package implements power circuits in two different ways. The first one uses compact representation of markings as defined in [1]. The tree containing all markings is stored not as a graph but as a matrix to improve access time. This implementation is asymptotically optimal.

The other implementation (PowerCircuitGraph) stores the graph by adjacency lists and resembles the less technical approach chosen in [2]. Markings, too, are stored as lists. This implementation does not make use of compact representations. Thus, it is not theoretically optimal, but usually faster for typical inputs as it uses a lot of overhead.

Both power-circuit-classes are derived from the abstract class PowerCircuit and can be used interchangably.

To perform calculations with power circuits, create an instance of one of the above classes. The PowerCircuit class provides methods to create markings, perform reduction, insert edges into the graph (connect), and other tasks.

Markings work like references to the respective internal representations. Thus the assignment operator does not create a deep copy of a marking. However all arithmetic operations create new markings, so you can keep the old ones. It is also not necessary (and not possible) to delete markings (in the PowerCircuitGraph class once there is no marking pointing onto an internal marking, its memory is automatically deallocated). Just make sure that you create markings only for the time you really need them.

To get an idea of how to use power circuits, you might want to take a look at the examples included in this package, where power circuits are used to solve the word problem in certain groups.

In order to use the draw method you need graphviz installed on your computer (download from http://www.graphviz.org/). This method creates a postscript file with a graphical depiction of the graph.

The documentation is created with doxygen (see http://www.stack.nl/~dimitri/doxygen/index.html). To create the documentation in html and latex format use "doxygen". You can change the settings for the documentation in the file "Doxyfile". If "Doxyfile" does not exist, use "doxygen -g" to create it.

Juern Laun
Armin Weiss

A lot of the theoretical background of power circuits is due to Sasha Ushakov. We thank him for his helpful advice, and also for the invitation to th Stevens Institute where parts of this implementation were developed.

[1] V. Diekert, J. Laun, A. Ushakov. Efficient algorithms for highly compressed data: The Word Problem in Higman's Group is in P. Preprint, 2011. http://arxiv.org/abs/1103.1232

[2] V. Diekert, J. Laun, A. Ushakov. Efficient algorithms for highly compressed data: The Word Problem in Higman's Group is in P. Conference version, to appear, 2011.

Typedef Documentation

typedef char PC::Sign

Type for storing signs, i.e., members of the set {-1,0,+1}.

Definition at line 19 of file Sign.h.

Function Documentation

void PC::addSigns ( const Sign &  op1,
const Sign &  op2,
Sign &  result,
Sign &  carry 
int PC::compareSigns ( const Sign &  op1,
const Sign &  op2 
Sign PC::negateSign ( const Sign &  s  ) 
int PC::signToInt ( const Sign &  s  ) 
std::string PC::signToString ( const Sign &  s  ) 

Variable Documentation

const Sign PC::MINUS = 2

Definition at line 22 of file Sign.h.

Referenced by PC::SignMatrix< RowHdr, ColHdr, INTERNAL_TYPE >::printMatrix().

const Sign PC::PLUS = 1

Definition at line 21 of file Sign.h.

Referenced by PC::SignMatrix< RowHdr, ColHdr, INTERNAL_TYPE >::printMatrix().

Definition at line 27 of file SignMatrix.h.

Definition at line 26 of file SignMatrix.h.

const Sign PC::ZERO = 0

Definition at line 20 of file Sign.h.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

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