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 usingadd_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
ifword
is accepted by the Schutzenberger graph. This means that the paths starting at the first node0
labelled by the representative andword
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, andFalse
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.
-