WordGraph

This module contains the single class WordGraph which implements a version of Stephen’s procedure which can be used to check whether two words in the free monoid represent the same element of a finitely presented monoid.

class step_hen.wordgraph.WordGraph(presn: step_hen.presentation.MonoidPresentation, rep: str)

This class implements Stephen’s procedure for (possibly) checking whether an arbitrary word in the free monoid represents the same element of a finitely presented monoid as a fixed word.

The finite monoid presentation and fixed word are set at construction.

__init__(presn: step_hen.presentation.MonoidPresentation, rep: str)

Construct from a monoid presentation and a representative.

Parameters

• presn – the monoid presentation.

• rep – the representative.

equal_to(word: str) → bool

Returns True if the argument is equal to the word used to construct this instance, and False if it does not.

Parameters

word – the word.

Returns

a bool.

Warning

The procedure implemented by method may never terminate. In particular, it terminates if and only if the subgraph of the right Cayley graph of the finitely presented monoid induced by those vertices reachable from empty word and from which the representative is reachable is finite. Even if the induced subgraph is finite, there is no bound on the run time of this method.

last_node_on_path(root: int, word: Union[List[int], int]) → Tuple[int, int]

Returns the last node on the path starting at root labelled by a prefix of word.

Parameters

• root – the root node.

• word – the word.

Returns

A tuple consisting of the last node on the path and the corresponding index in word.

number_of_nodes() → int

Returns the number of nodes in the graph.

Parameters

None

Returns

An int.

path(node: int, word: List[int]) → int

Returns the target node on the path starting at root labelled by word if such a node exists and None otherwise.

Parameters

• root – the root node.

• word – the word.

Returns

An int.