Presentation helpers

This page contains the documentation for various helper functions for manipulating presentations.

Types

In what follows, we use the following pseudo-types:

Letter for str | int

Word for str | list[int]

Recall that, once a presentation has been constructed, the type of its letters and words are fixed.

Contents

`add_identity_rules`(…)	Add rules for an identity element.
`add_inverse_rules`(…)	Add rules for inverses.
`add_rule`(…)	Check and add a rule to the presentation.
`add_rules`(…)	Add the rules of q to p.
`add_zero_rules`(…)	Add rules for a zero element.
`are_rules_sorted`(…)	Check the rules are sorted relative to shortlex.
`change_alphabet`(…)	Change or re-order the alphabet.
`contains_rule`(…)	Check if a presentation contains a rule.
`first_unused_letter`(…)	Return the first letter not in the alphabet of a presentation.
`greedy_reduce_length`(…)	Greedily reduce the length of the presentation using `longest_subword_reducing_length`.
`greedy_reduce_length_and_number_of_gens`(…)	Greedily reduce the length and number of generators of the presentation.
`is_strongly_compressible`(…)	Return true if the \(1\)-relation presentation can be strongly compressed.
`length`(…)	Return the sum of the lengths of the rules.
`longest_rule`(…)	Return the index of the left-hand side of the longest rule.
`longest_rule_length`(…)	Return the maximum length of a rule in the presentation.
`longest_subword_reducing_length`(…)	Return the longest common subword of the rules.
`make_semigroup`(…)	Convert a monoid presentation to a semigroup presentation.
`normalize_alphabet`(…)	Normalize the alphabet to \(\{0, \ldots, n - 1\}\).
`reduce_complements`(…)	If there are rules \(u = v\) and \(v = w\) where \(\|w\| < \|v\|\), then replace \(u = v\) by \(u = w\).
`reduce_to_2_generators`(…)	Reduce the number of generators in a one relation presentation to 2.
`remove_duplicate_rules`(…)	Remove duplicate rules.
`remove_redundant_generators`(…)	Remove any trivially redundant generators.
`remove_trivial_rules`(…)	Remove rules consisting of identical words.
`replace_subword`(…)	Replace non-overlapping instances of a subword by another word.
`replace_word`(…)	Replace instances of a word on either side of a rule by another word.
`replace_word_with_new_generator`(…)	Replace non-overlapping instances of a word with a new generator.
`reverse`(…)	Reverse every rule.
`shortest_rule`(…)	Return the index of the left-hand side of the shortest rule.
`shortest_rule_length`(…)	Return the minimum length of a rule in the presentation.
`sort_each_rule`(…)	Overloaded function.
`sort_rules`(…)	Sort all of the rules by shortlex.
`strongly_compress`(…)	Strongly compress a one relation presentation.
`throw_if_bad_inverses`(…)	Validate if vals act as semigroup inverses in p.
`to_gap_string`(…)	Return the code that would create p in GAP.

Full API

The full API for Presentation helper functions is given below.

presentation.add_identity_rules(p: Presentation, e: Letter) → None

Add rules for an identity element.

Adds rules of the form \(ae = ea = a\) for every letter \(a\) in the alphabet of p, and where \(e\) is the second parameter.

Parameters:

p (Presentation) – the presentation to add rules to.
e (Letter) – the identity element.

Raises:

LibsemigroupsError – if e is not a letter in p.alphabet().

Complexity:

Linear in the number of rules.

presentation.add_inverse_rules(p: Presentation, vals: Word, e: Letter = UNDEFINED) → None

Add rules for inverses.

The letter a with index i in vals is the inverse of the letter in alphabet() with index i. The rules added are \(a_ib_i = e\) where the alphabet is \(\{a_1, \ldots, a_n\}\) ; the 2nd parameter vals is \(\{b_1, \ldots, b_n\}\) ; and \(e\) is the 3rd parameter.

Parameters:

p (Presentation) – the presentation to add rules to.
vals (Word) – the inverses.
e (Letter) – the identity element (defaults to UNDEFINED, meaning use the empty word).

Raises:

LibsemigroupsError – if the length of vals is not equal to alphabet().size().
LibsemigroupsError – if the letters in vals are not exactly those in alphabet() (perhaps in a different order).
LibsemigroupsError – if \((a_i ^ {-1}) ^ {-1} = a_i\) does not hold for some \(i\).
LibsemigroupsError – if \(e ^ {-1} = e\) does not hold.

Complexity:

\(O(n)\) where \(n\) is p.alphabet().size().

presentation.add_rule(p: Presentation, lhop: Word, rhop: Word) → None

Check and add a rule to the presentation.

Adds the rule with left-hand side lhop and right-hand side rhop to the rules, after checking that lhop and rhop consist entirely of letters in the alphabet of p.

Parameters:

p (Presentation) – the presentation.
lhop (Word) – the left-hand side of the rule.
rhop (Word) – the right-hand side of the rule.

Raises:

LibsemigroupsError – if lhop or rhop contains any letters not belonging to p.alphabet().

presentation.add_rules(p: Presentation, q: Presentation) → None

Add the rules of q to p.

Before it is added, each rule is validated to check it contains only letters of the alphabet of p. If the \(n`th rule causes this function to throw, the first :math:`n-1\) rules will still be added to p.

Parameters:

p (Presentation) – the presentation to add rules to.
q (Presentation) – the presentation to add words from.

Raises:

LibsemigroupsError – if any rule contains any letters not belonging to p.alphabet().

presentation.add_zero_rules(p: Presentation, z: Letter) → None

Add rules for a zero element.

Adds rules of the form \(az = za = z\) for every letter \(a\) in the alphabet of p, and where \(z\) is the second parameter.

Parameters:

p (Presentation) – the presentation to add rules to.
z (Letter) – the zero element.

Raises:

LibsemigroupsError – if z is not a letter in p.alphabet().

Complexity:

Linear in the number of rules.

presentation.are_rules_sorted(p: Presentation) → bool

Check the rules are sorted relative to shortlex.

Check if the rules \(u_1 = v_1, \ldots, u_n = v_n\) satisfy \(u_1v_1 < \cdots < u_nv_n\) where \(<\) is shortlex order.

Parameters:: p (Presentation) – the presentation to check.
Returns:: whether the rules are sorted.
Return type:: bool
Raises:: LibsemigroupsError – if p.rules.size() is odd.