SchutzenbergerGraph¶

This module contains the single class SchutzenbergerGraph 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 inverse monoid.

class step_hen.schutzenbergergraph.SchutzenbergerGraph(presn: step_hen.presentation.InverseMonoidPresentation, rep: str)¶

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

Generators are represented by lower case letters and their inverses by upper case letters.

The alphabet is set using the method set_alphabet(), and relations can be added using add_relation().

__init__(presn: step_hen.presentation.InverseMonoidPresentation, rep: str)¶

Construct from a monoid presentation and a representative.

Parameters

presn – the inverse monoid presentation.
rep – the representative.

accepts(word: str) → bool¶

Returns True if word is accepted by the Schutzenberger graph. This means that the paths starting at the first node 0 labelled by the representative and word are both defined and end at the same node.

Two words in the free monoid are equal, in the finitely presented inverse monoid used to construct the Schutzenberger graph, if and only if their respective SchutzenbergerGraph objects both accept the other word.

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 \(\mathscr{R}\)-class of the representative defined at construction is finite. Even if the \(\mathscr{R}\)-class is finite, there is no bound on the run time of this method.

equal_to(word: str) → None¶

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.