PC Namespace Reference

Classes
class	Node
class	Marking
class	PowerCircuit
class	PowerCircuitCompMatrix
class	PowerCircuitGraph
struct	Row
struct	Col
class	SignMatrix
Typedefs
typedef char	Sign
Functions
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)
Variables
const Sign	ZERO = 0
const Sign	PLUS = 1
const Sign	MINUS = 2
const Row	UNDEFINED_ROW
const Col	UNDEFINED_COL

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.

Authors:: 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.